《Python數據挖掘》筆記（四） 網路分析

Python數據挖掘：概念、方法與實踐。Megan Squire著，姚軍譯，機械工業出版社，2017年。

筆記中有些內容直接引用原書。

=======================================================

這章將學到：

a. 網路理論的基礎知識，包括如何計量網路

b. 為什麼我們在網路中能夠找到的不同形狀很有趣

c. 如何將現實世界的數據組織為可以網路形式分析的結構

d. 如何用Python和NetworkX尋找和解讀現實世界數據中的這些模式

e. 如何比較網路的多個版本，以了解網路如何隨時間而變化

4.1 什麼是網路

網路指的是可以由節點和鏈接組成的圖表示的系統。節點是相互聯繫的事務，鏈接是節點之間的關係。所有節點和鏈接的集合稱為圖。

4.2 網路計量

4.2.1 網路的度數

節點的度數是與其相連的邊數。對於無向圖，節點的度是從其出發的所有邊數。對於有向圖，節點的入邊為入度，節點的出邊為出度。入度和出度相加，為節點的總度數。

4.2.2 網路直徑

兩個點之間的距離是連接它們所需要的最小跳數（最短路徑）。圖的直徑是圖中任意兩點的最長距離（最長最短路徑）。

4.2.3 網路中的通路、路徑和跡

圖中的通路指的是遍歷節點之間的鏈接。

圖中的跡指的是遍歷圖時對每條鏈接最多使用一次，但是節點可以使用多次。

圖中的路徑指的是節點和鏈接在遍歷中都不重複使用。

4.2.4 網路的成分

如果每個節點都可以從所有其他節點到達，則該圖稱為連接圖。如果圖具有多個非連通子圖，在這些子圖中一個節點到某些其他節點沒有路徑，我們稱該圖包含多個成分。

只包含一個節點的成分稱為孤立節點。這些節點的度數為0.

4.2.5 圖的中心性

a. 接近中心性：首先計算網路中每對節點之間的最短路徑距離；接著對每個節點，計算它與所有其他節點的距離總和；最後將該數值除以網路的可能最小距離（節點數量減1）。

b. 度中心性：度中心性只考慮網路總體大小的情況下，給定節點連接的節點數。其計算方法為其度數（邊數）除以網路中的總結點數。

c. 中介中心性

判別對圖的連通性起到關鍵作用的節點。中介性越高，對圖的順利運行越重要。計算方法：首先計算網路上每對節點之間的最短路徑，然後對每個節點計算有多少條網路最短路徑包含該節點但是不起止於該節點。最後將該數量除以節點配對總數，即：（節點數-1）*（節點數-2）/2。

d. 其他中心性測度

還有許多其他的方法，如PageRank演算法。NetworkX可以輕鬆計算複雜網路中數百個節點的各類中心性測度。

4.3 圖數據的表示

4.3.1. 鄰接矩陣

A B C

A 0 1 0

B 1 0 1

C 0 1 0

4.3.2. 邊表和鄰接表

邊表：

A,B

B,A

B,C

C,B

鄰接表：

A: (B)

B: (A, C)

C: (B)

這種方式可以用哈希表、Python中的字典結構或者JSON中的一組鍵值對形式實現。

4.3.3. 圖數據結構之間的差別

Python的NetworkX包可以用節點和邊的列表創建圖，不管我們想用鄰接矩陣、邊表還是鄰接表表示圖，都有內建的函數可以使用。但是在NetworkX內部，它採用Python的字典數據結構，以鄰接表形式存儲圖。

4.3.4. 將數據導入圖結構中

NetworkX支持10種以上的不同文件格式：包括鄰接表格式、邊表格式、GEXF和GraphML格式、GDF格式、Pickle格式、JSON格式、JSON節點和鏈接系列、JSON樹、Pajek格式。

4.4 真實項目

對RubyForge開發人員的社交網路進行分析。進行了以下操作：

生成網路文件

生成簡單網路指標

嘗試網路參數

分析子圖

分析子圖中的團和中心性

尋找一段時間內的變化

Github代碼

4.5 小結

BrianZhang：《Python數據挖掘》筆記（一）擴展你的數據挖掘工具箱zhuanlan.zhihu.comBrianZhang：《Python數據挖掘》筆記（二）關聯規則挖掘zhuanlan.zhihu.comBrianZhang：《Python數據挖掘》筆記（三）實體匹配zhuanlan.zhihu.comBrianZhang：《Python數據挖掘》筆記（五） 文本情緒分析zhuanlan.zhihu.comBrianZhang：《Python數據挖掘》筆記（六） 文本中的命名實體識別zhuanlan.zhihu.comBrianZhang：《Python數據挖掘》筆記（七） 自動化文本摘要zhuanlan.zhihu.comBrianZhang：《Python數據挖掘》筆記（八）文本中的主題建模zhuanlan.zhihu.comBrianZhang：《Python數據挖掘》筆記（九）挖掘數據異常zhuanlan.zhihu.com軟體開發之路zhuanlan.zhihu.com
推薦閱讀：