本文總結(jié)之日CS224W Winter 2021只更新到了第四節(jié)，所以下文會(huì)參考2021年課程的PPT并結(jié)合2019年秋季課程進(jìn)行總結(jié)以求內(nèi)容完整
課程主頁：CS224W: Machine Learning with Graphs
視頻鏈接：【斯坦?！緾S224W：圖機(jī)器學(xué)習(xí)( 中英字幕 | 2019秋)
1 引言
初步了解一個(gè)人，我們通常會(huì)問其身高、年齡、體重等信息。那么，要了解一個(gè)圖Graph我們需要關(guān)注哪些信息呢？這就是本節(jié)討論的內(nèi)容。
2 圖的四大屬性
通常我們會(huì)從下面四個(gè)方面去初步理解一個(gè)圖：
-
度分布（Degree distribution）
-
路徑長(zhǎng)度（Path length）
-
聚類系數(shù)（Clustering coefficient）
-
連通分量（Connected components）
下面依此來看
2.1 度分布（Degree distribution）
定義：統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的度，然后計(jì)算不同的度數(shù)在所有節(jié)點(diǎn)中出現(xiàn)的頻率。從圖上看起來更直觀。
2.2 路徑長(zhǎng)度（Path length）
需要了解三個(gè)概念：路徑、距離、直徑
-
路徑:是一串彼此相連的節(jié)點(diǎn)組成的鏈。如:, 注：一個(gè)條路徑中的某點(diǎn)看可以出現(xiàn)多次！
-
-
距離（Distance）：兩點(diǎn)之間的最短路徑shortest path，稱為兩點(diǎn)之間的距離。注：
-
- 對(duì)于有向圖，一條路徑的邊一定要從左到右
- 若兩點(diǎn)之間不直接或間接相連則距離為無窮大.
如下圖中的
和
點(diǎn)之間距離
-
直徑:圖的中任意兩點(diǎn)之間距離的最大值，稱為圖的直徑。但直徑并不是很好用，考慮到一個(gè)
很扁的圖和很圓的圖可能具有形同的直徑。說白了就是容易受極端值影響。通常采用平均距離。- 計(jì)算時(shí)忽略不相連的兩點(diǎn)間距離，因?yàn)闊o窮大。
- 直徑也適用于刻畫圖的某個(gè)連通分量（connected components）的直徑。
平均距離Average path length：所有兩點(diǎn)之間距離加總，除以所有兩點(diǎn)的組合數(shù)。
2.3 聚類系數(shù)（Clustering coefficient）
- 定義：是用來描述一個(gè)圖中的某節(jié)點(diǎn)與其相連節(jié)點(diǎn)之間
聚集成團(tuán)的程度的一個(gè)系數(shù)。它只定義在無向圖上。計(jì)算方法如下：
實(shí)際上就是算節(jié)點(diǎn)i與鄰居構(gòu)成實(shí)際組成的三角形數(shù)除上最大可能三角形個(gè)數(shù)。翻譯成人話就是 我的朋友之間相互認(rèn)識(shí)情況。
-
平均聚類系數(shù)：所有節(jié)點(diǎn)的聚類系數(shù)取平均就得到。
2.4 連通分量（Connected components）
連通分量：圖中的一個(gè)子圖，子圖中任意兩點(diǎn)之間都存在路徑，子圖內(nèi)節(jié)點(diǎn)和子圖外的節(jié)點(diǎn)都沒有路徑。- 任何連通圖的連通分量只有一個(gè)，即是其自身。
- 非連通的無向圖有多個(gè)連通分量。
如何找到連通分量？
通過廣度搜索算法（BFS）：
- 隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為起點(diǎn)，進(jìn)行廣度優(yōu)先搜索；
- 將廣度優(yōu)先搜索經(jīng)過的節(jié)點(diǎn)進(jìn)行標(biāo)記；
- 如果所有的節(jié)點(diǎn)都進(jìn)行了標(biāo)記，則該圖是一個(gè)連通圖；
- 如果存在未標(biāo)記的節(jié)點(diǎn)，從未標(biāo)記的節(jié)點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為起點(diǎn)進(jìn)行廣度優(yōu)先搜索；重復(fù)第2步和第4步，直至所有節(jié)點(diǎn)都標(biāo)記完畢；最后得到的多個(gè)連通子圖中對(duì)的極大連通子圖就是該圖的連通分量。
3 MSN Messager網(wǎng)絡(luò)
老師通過MSN（類似QQ的聊天軟件）上一個(gè)月的對(duì)話活動(dòng)構(gòu)建的網(wǎng)絡(luò)，這本身是個(gè)Multigraph 包含180M的用戶（節(jié)點(diǎn)），兩類邊：是否好友、是否聊過天（可多次）。
通過簡(jiǎn)化，將用戶之間有過聊天簡(jiǎn)化成無向圖。共180M節(jié)點(diǎn)，1.3B邊。這個(gè)MSN網(wǎng)絡(luò)的4大屬性如下：
通過屬性說明了什么呢？
- 度分布，均值14.4，說明平均每個(gè)人和14.4個(gè)人聊天
- 聚類系數(shù)，均值0.11，平均每個(gè)人聊天過的朋友中，只有11%的朋友會(huì)彼此聊天。
- 連通分量，最大聯(lián)通分量覆蓋99%的節(jié)點(diǎn)，
強(qiáng)連通,絕大部分人都生活在一個(gè)大群體中。 - 路徑長(zhǎng)度，均值6.6，平均兩個(gè)人之間通過7個(gè)人就能聊上天;最大值30，意味任意兩個(gè)人能認(rèn)識(shí)最多通過30個(gè)人就能實(shí)現(xiàn)。
4 下文預(yù)告
得到圖的四個(gè)維度屬性后，怎么評(píng)價(jià)這個(gè)網(wǎng)絡(luò)呢？到底處在什么水平？
就好像評(píng)價(jià)看一個(gè)人是高還是矮，我們是拿自己或他人作為參照，得出結(jié)論。那么對(duì)于網(wǎng)絡(luò)我們也需要一個(gè)參照，這就是下面要談的隨機(jī)網(wǎng)絡(luò)模型
