網(wǎng)絡(luò)的4大關(guān)鍵屬性

• 度分布（Dgree distribution：p(k)）
• 路徑長度（Path length：h）
• 聚合系數(shù)（Clustering coefficient：C）
• 聯(lián)通模塊（Connected components：s）

以上4個屬性主要針對無向圖，如果以下筆記有特別針對有向圖時，會主動提出

度分布

= 度為k的節(jié)點數(shù)， = 總節(jié)點數(shù)

dgree distribution.PNG

對于有向圖我們分為出度和入度分布

路徑長度

距離：兩點間的最短路徑（如果兩點之間不連接，通常將距離定義為infinite）
直徑：圖中兩點的最大距離
平均路徑長度：針對無向圖和有向圖中的強連通圖（強連通圖代表任意兩點間存在路徑）

path length.PNG

聚合系數(shù)

clustering coefficient.PNG

代表節(jié)點i的鄰居間存在的邊的數(shù)量，代表節(jié)點i的鄰居間可能存在的再大的邊的數(shù)量，將這兩個量相除就得到了聚合系數(shù)

聯(lián)通模塊

connectivity.PNG

隨機圖模型

本課程主要介紹了模式（還有了課程沒有詳細介紹）：對于擁有n個節(jié)點的無向圖，每兩個點間存在邊的概率為p。對于給定的兩個參數(shù)n和p，相同的參數(shù)可能會產(chǎn)生不同的圖。

Gnp.PNG

那么Gnp模型的四種網(wǎng)絡(luò)屬性又是怎么樣的呢？先上結(jié)論。

• Degree distribution：
• Path length：
• Clustering coefficient：
• Connected components：暫略

度分布

Gnpdegree distribution.PNG

路徑長度

這里Jure引入了擴展系數(shù)來證明隨機網(wǎng)絡(luò)的路徑長度。直接給了結(jié)果，即一個有n個節(jié)點的網(wǎng)絡(luò)，如果有擴展系數(shù)為，則網(wǎng)絡(luò)的路徑長度的期望是：,這是一個和有關(guān)的值。
對于隨機網(wǎng)絡(luò)，路徑長度的期望就是。對于固定的，分母變成了常數(shù)，所以就是級別。模擬實驗的結(jié)果如下，也證明了這個結(jié)論。

Gnp_Clustering coeffcient.png

聚合系數(shù)

Gnp_Clustering coefficient.PNG

聯(lián)通模塊

connectivity.PNG

由上圖可知圖的聯(lián)通性會隨著p的改變而改變

exp.PNG

隨著p值越來越大，節(jié)點的平均度也越來越大，最終最大聯(lián)通塊中囊括了圖中大部分的節(jié)點。

sumary

將實際的圖與隨機圖進行了比較，并給出了為什么我們要使用隨即圖的原因。

sumary1.PNG

summary2.PNG

小世界圖模型

隨機網(wǎng)絡(luò)是很簡單的圖模型，可以作為一個基準(zhǔn)。但是更實際的模型有很多，其中小世界圖模型非常有名。其核心思想就是，雖然隨機網(wǎng)絡(luò)的平均路徑是比較短的，但聚合系數(shù)非常的低，這是由于隨機網(wǎng)絡(luò)假定的是大家都隨機的和世界上其他人交朋友。但真實的網(wǎng)絡(luò)的聚合系數(shù)都是很高的，節(jié)點的本地結(jié)構(gòu)化非常明顯。那么我們能否通過某種方式來產(chǎn)生這樣的圖——高聚合系數(shù)、低平均路徑長度(或者就是低圖直徑)。

litle world.PNG

一種構(gòu)造高聚合系數(shù)、低平均路徑長度圖的方式:

1. 先構(gòu)造一個左邊的圖

2. 對每一條邊，以概率p將該邊的一個端點改為另一個隨機節(jié)點

   
   
   rewoire.PNG

Kronecker網(wǎng)絡(luò)模型

Kroneck乘法：

knc1.PNG

隨機Kronecker模型構(gòu)造法：

1. 構(gòu)造一個X的概率矩陣
2. 使用Kronecker乘法次，生成矩陣
3. 中每個元素代表一個概率值，即兩個節(jié)點間生成邊的概率
4. 然后按照這個概率產(chǎn)生實際的鄰接矩陣，就生成了一個大圖

knc2.PNG

由于上面的方式要計算X次才能得出目標(biāo)矩陣，說是這樣速度太慢了，又說了一種快速的方式，不過沒怎么看懂，如果以后用到了再說吧。