NetworkX 網路分析入門

NetworkX 提供了豐富的工具和演算法，方便我們處理和分析各種網路結構。從簡單的無向圖到複雜的有向加權圖，NetworkX 都能輕鬆應對。利用 Python 的靈活性，我們可以結合 NetworkX 進行資料分析、視覺化和演算法設計，深入探索網路的特性和規律。理解網路的節點、邊、權重和屬性等概念，是進行網路分析的基礎。透過 NetworkX，我們可以將這些概念轉化為程式碼，並運用其內建的演算法和視覺化工具，更有效地理解和應用網路科學的知識。

網路是什麼？第一章

NetworkX 是一個免費且開放原始碼的軟體（FOSS）。這意味著其原始碼可供閱讀、修改和重新分發（在特定條件下）。原始碼可在 https://github.com/networkx/networkx 取得。除了原作者和專案維護者之外，NetworkX 還由數十名貢獻者共同編寫。如果你有新的功能想法或改進軟體的方法，你可以自己編寫並將其貢獻回社群。

對 FOSS 專案的貢獻

在向 FOSS 專案貢獻時，閱讀貢獻者是一種良好的禮儀。這些幫助專案貢獻者有效地協作，避免衝突的變更，並確保軟體的可靠性。

網路型別

本章介紹的網路僅具備基本要素。這些網路被稱為簡單網路，因為它們很簡單。在 NetworkX 中，簡單網路由 Graph 類別表示，將在第 2 章「在 NetworkX 中使用網路」中詳細描述。

有向網路

有時，在網路中新增一些細節會有幫助。目前為止，我們所看到的邊都沒有方向；它們只是兩個節點之間的連線，因此被稱為對稱或無向的。想像一個代表道路系統（邊）和交叉路口（節點）的網路。無向邊的網路是一個好的表示，直到你遇到單行道。無向邊表示你可以同樣輕鬆地朝任一方向行駛，而實際上，逆著交通流駕駛可能與順著交通流駕駛有著非常不同的體驗。

當方向很重要時，網路被稱為有向網路。在有向網路中，每條邊都有一個源節點和一個目標節點。通常，邊代表某種流動，例如交通，從源到目標。但是，如果不是所有的連線都是單向的怎麼辦？很簡單！雙向連線是透過組合兩個朝相反方向的有向邊來實作的。在有向網路中，邊被繪製成指向目標的箭頭，如下圖所示。在 NetworkX 中，有向網路由 DiGraph 類別表示，也在第 2 章「在 NetworkX 中使用網路」中描述。

加權網路

回到無向網路的情況，有時並非所有的邊都是一樣的。例如，在代表城市供水系統的網路中，邊可以代表一系列將水從一個地方運輸到另一個地方的管道。其中一些管道可能比其他的具有更大的容量。當邊可以具有不同的強度時，網路被稱為加權網路，而強度由一個稱為權重的數字來量化。有向和無向網路都可以是加權的。下面是一個加權網路的例子。在視覺化網路時，邊權重通常透過改變邊的粗細或透明度來表示。邊權重可以用來代表許多不同型別的屬性。最常見的屬性在下一節中描述。

理解邊

邊代表了構成網路的連線和關係。邊及其權重可以根據網路所代表的內容具有不同的解釋。一些常見的解釋包括：

• 友誼：在社交網路中，邊通常代表友誼或其他人際關係。邊權重代表友誼的強度，例如一起度過的時間、交換的訊息或共同興趣的數量。

• 流動：流動網路描述了某物（人、資訊、流體等）從一個地方移動到另一個地方。邊權重可能代表容量——兩個節點之間可以運輸的最大數量——或者實際上已經透過連線運輸的數量。

• 相似性：在相似性網路中，連線更抽象，而不是字面上的。邊權重對應於兩個節點之間的相似程度，通常以零表示完全不相似，一表示完全相同。例如，不同人之間的某種相似性可以透過取他們最喜歡的前 10 個線上貓影片並使用出現在兩個人中的影片比例來計算。在這種情況下，邊權重與兩個人是否有任何關係無關。兩個從未見過面的人之間完全有可能存在一條權重非常高的邊！

import networkx as nx
import matplotlib.pyplot as plt

# 建立一個簡單的有向圖
G = nx.DiGraph()
G.add_edge('A', 'B')
G.add_edge('B', 'C')
G.add_edge('C', 'A')

# 繪製圖表
nx.draw(G, with_labels=True)
plt.show()

內容解密：

這段程式碼首先匯入了必要的函式庫：networkx 用於建立和操作複雜網路，matplotlib.pyplot 用於繪製圖表。然後，它建立了一個有向圖 G，並新增了三條有向邊 'A' -> 'B'、'B' -> 'C' 和 'C' -> 'A'。最後，它使用 nx.draw 函式繪製圖表，並顯示節點標籤。

# 建立一個加權無向圖
G_weighted = nx.Graph()
G_weighted.add_edge('A', 'B', weight=3)
G_weighted.add_edge('B', 'C', weight=2)
G_weighted.add_edge('C', 'A', weight=1)

# 繪製加權圖表
pos = nx.spring_layout(G_weighted)
nx.draw(G_weighted, pos, with_labels=True)
labels = nx.get_edge_attributes(G_weighted, 'weight')
nx.draw_networkx_edge_labels(G_weighted, pos, edge_labels=labels)
plt.show()

內容解密：

這段程式碼建立了一個加權無向圖 G_weighted，並新增了三條帶有權重的邊。然後，它使用 nx.spring_layout 計算節點的位置，使用 nx.draw 繪製圖表，並使用 nx.draw_networkx_edge_labels 在圖表上標註邊的權重。這樣可以視覺化地展示加權網路中的權重資訊。

網路的多樣性與應用

不同的網路型別，如有向網路和加權網路，為我們提供了豐富的工具來建模和分析複雜系統。從社交網路中的人際關係到交通網路中的流動模式，這些工具能夠幫助我們更好地理解和最佳化這些系統。

網路科學入門：認識網路

網路科學是一門跨學科的研究領域，探討各種關係和連結的結構與特性。在本章中，我們將介紹網路的基本概念，並使用 NetworkX 函式庫在 Python 中建立和視覺化網路。

空間網路與邊權重

在空間網路中，邊可以用來表示節點之間的距離或接近程度。當使用邊權重來表示距離時，可以透過將路徑上的所有邊權重相加來計算整個行程的距離。然而，使用邊權重來表示距離有時可能會造成混淆，因為較大的數字代表較弱的連線，而不存在的邊實際上是具有無限權重的邊。

網路的多樣性

網路科學的應用非常廣泛，從社交網路到交通網路，都有著不同的特性和結構。無論何時，只要一組事物之間存在某種關係或連線，就可以使用網路來捕捉這些連線的結構。

使用 NetworkX 建立和視覺化網路

現在，讓我們使用 NetworkX 建立和視覺化一個小型網路。首先，我們需要匯入 NetworkX 函式庫，並建立一個 Graph 物件，代表一個無向網路。

import networkx as nx
import matplotlib.pyplot as plt

# 建立一個無向網路
G = nx.Graph()

# 新增節點
G.add_node('A')
G.add_nodes_from(['B', 'C'])

# 新增邊
G.add_edge('A', 'B')
G.add_edges_from([('B', 'C'), ('A', 'C')])

# 視覺化網路
plt.figure(figsize=(7.5, 7.5))
nx.draw_networkx(G)
plt.show()

內容解密：

1. import networkx as nx：匯入 NetworkX 函式庫，並將其別名設為 nx。
2. G = nx.Graph()：建立一個無向網路物件 G。
3. G.add_node('A') 和 G.add_nodes_from(['B', 'C'])：新增節點到網路中。
4. G.add_edge('A', 'B') 和 G.add_edges_from([('B', 'C'), ('A', 'C')])：新增邊到網路中。
5. nx.draw_networkx(G)：視覺化網路。

網路視覺化的自定義

NetworkX 提供了多種視覺化函式，可以自定義視覺化樣式。我們可以使用 plt.rcParams.update({'figure.figsize': (7.5, 7.5)}) 設定預設的圖形大小。

新增節點和邊的捷徑

如果嘗試新增一條邊，參照一個不存在的節點 ID，NetworkX 會自動新增該節點。因此，在實際操作中，我們不需要直接呼叫 add_node()。

G.add_edges_from([('B', 'D'), ('C', 'E')])
nx.draw_networkx(G)

內容解密：

1. G.add_edges_from([('B', 'D'), ('C', 'E')])：新增邊和節點到網路中。
2. nx.draw_networkx(G)：視覺化更新後的網路。

參考資料

1. Cohen, R., & Ruths, D. (2013). Classifying political orientation on Twitter: It’s not easy!. In Seventh International AAAI Conference on Weblogs and Social Media.
2. Euler, L. (1953). Leonhard Euler and the Königsberg bridges. Scientific American, 189(1).
3. Jernigan, C., & Mistree, B. F. (2009). Gaydar: Facebook friendships expose sexual orientation. First Monday, 14(10).
4. Moreno, J. L., & Jennings, H. H. (1934). Who Shall Survive? Nervous and Mental Disease.
5. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab.
6. Zhang, Y., & Pennacchiotti, M. (2013, May). Predicting purchase behaviors from social media. In Proceedings of the 22nd international conference on World Wide Web. ACM.

此圖示顯示了使用 NetworkX 建立和視覺化的小型網路結構，以下是詳細解說：

@startuml
skinparam backgroundColor #FEFEFE
skinparam componentStyle rectangle

title NetworkX 網路分析入門

package "圖論網路分析" {
    package "節點層" {
        component [節點 A] as nodeA
        component [節點 B] as nodeB
        component [節點 C] as nodeC
        component [節點 D] as nodeD
    }

    package "中心性指標" {
        component [度中心性
Degree Centrality] as degree
        component [特徵向量中心性
Eigenvector Centrality] as eigen
        component [介數中心性
Betweenness Centrality] as between
        component [接近中心性
Closeness Centrality] as close
    }
}

nodeA -- nodeB
nodeA -- nodeC
nodeB -- nodeD
nodeC -- nodeD

nodeA --> degree : 計算連接數
nodeA --> eigen : 計算影響力
nodeB --> between : 計算橋接度
nodeC --> close : 計算距離

note right of degree
  直接連接數量
  衡量局部影響力
end note

note right of eigen
  考慮鄰居重要性
  衡量全局影響力
end note

@enduml

此圖示說明：

1. 節點 A 與節點 B 和 C 相連。
2. 節點 B 與節點 C 和 D 相連。
3. 節點 C 與節點 E 相連。
4. 該圖示呈現了一個簡單的無向網路結構。

使用NetworkX處理網路資料

NetworkX的基本功能包含在多個Python類別中，這些類別代表了不同型別的網路。特別是，本章節將討論Graph、DiGraph、MultiGraph和MultiDiGraph。這些類別可以用來表示、分析和視覺化大多數的網路。在本章中，您將學習如何使用這些類別來處理現實世界的網路資料。後續章節的程式碼範例將假設您已經匯入了networkx套件。

本章涵蓋的主題

• Graph類別：瞭解無向網路的屬性以及如何使用NetworkX的Graph類別來表示它們。
• 屬性：如何將資料與節點和邊緣關聯起來。
• 邊緣權重：學習如何量化連線強度，並用該資訊註解邊緣。
• DiGraph類別：瞭解有向網路的屬性以及如何使用NetworkX的DiGraph類別來表示它們。
• MultiGraph和MultiDiGraph類別：學習具有平行邊緣的網路。

Graph類別 – 無向網路

在NetworkX中，Graph類別用於表示無向網路並分析其結構。前一章節展示瞭如何透過新增節點和邊緣從頭開始建立一個網路。本文將使用NetworkX中現成的網路之一：Zachary的空手道俱樂部（Zachary, 1977）。

Zachary的空手道俱樂部網路

這個網路代表了在1970年至1972年間研究的一個空手道俱樂部成員（節點）之間的友誼（邊緣）。這個特定的空手道俱樂部長期以來一直是社會學家和網路科學家感興趣的物件，因為它最終在教練和俱樂部主席之間的意見不合後分裂成兩個不同的俱樂部（這可能解釋了為什麼沒有關於衝突解決俱樂部的著名研究）。在原研究中，Zachary使用網路結構以接近完美的準確度預測哪些成員將加入哪個俱樂部！具體來說，他使用了第7章中討論的最小割演算法，《在之間 – 社群》。

G = nx.karate_club_graph()
karate_pos = nx.spring_layout(G, k=0.3)
nx.draw_networkx(G, karate_pos)

上述程式碼將空手道俱樂部網路儲存在G中。然後，使用spring_layout()預先計算視覺化佈局並儲存在karate_pos中，這將允許我們在本章中重複使用該佈局。不同的佈局方法在第11章《視覺化》中詳細討論，但現在，您只需要知道spring_layout()嘗試將節點放在更接近的位置，如果它們透過邊緣連線。最後，呼叫draw_networkx()建立以下視覺化：

Zachary空手道俱樂部網路視覺化

Graph類別提供了許多與節點和邊緣互動的方式。可以使用其nodes和edges屬性存取Graph類別中的節點和邊緣。這些屬性是可迭代的，可以用於遍歷節點和邊緣，或轉換為節點ID和邊緣的列表，如下所示：

list(G.nodes)
# [0, 1, 2, ...]
list(G.edges)
# [(0, 1), (0, 2), (0, 3), ...]

檢查節點是否存在

檢查特定節點是否存在於網路中的另一種簡單方法是使用Python的in運算子或Graph類別的has_node()方法，如下所示：

mr_hi = 0
mr_hi in G
# True
G.has_node(mr_hi)
# True

檢查邊緣是否存在

您可以使用Python的in運算子或Graph類別的has_edge()方法測試給定的邊緣是否存在。如果您只想知道Mr. Hi是否與特定的俱樂部成員（例如節點ID 1）是朋友，可以使用以下程式碼：

member_id = 1
(mr_hi, member_id) in G.edges
# True
G.has_edge(mr_hi, member_id)
# True

取得節點的鄰居

每個連線到Mr. Hi節點的邊緣代表他的友誼之一。這些邊緣另一端的節點代表他的朋友。通常，透過邊緣連線到特定節點的節點集稱為該節點的鄰居，可以使用Graph類別的neighbors()方法找到。 neighbors()方法傳回一個迭代器，這對於大多數用途來說很方便，但如果您只想檢視鄰居，可以使用list()建構函式：

list(G.neighbors(mr_hi))
# [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 17, 19, 21, 31]

新增屬性到節點和邊緣

在前一章中，我們說網路完全由節點數量和哪些節點相連定義。現在我們知道，有時網路節點和邊緣會被註解上額外的資訊。在Graph類別中，每個節點和邊緣都可以有一組屬性來儲存這些額外的資訊。屬性可以簡單地成為儲存與節點和邊緣相關資訊的方便場所，也可以被視覺化和網路演算法使用。

程式碼解析

G = nx.karate_club_graph()

• 這行程式碼建立了一個Zachary空手道俱樂部網路的例項，並將其儲存在變數G中。

karate_pos = nx.spring_layout(G, k=0.3)

• 這行程式碼使用spring佈局演算法計算網路G的佈局，並將結果儲存在karate_pos中，用於後續的視覺化。

nx.draw_networkx(G, karate_pos)

• 這行程式碼根據預先計算好的佈局karate_pos繪製網路G。

list(G.nodes)
list(G.edges)

• 這兩行程式碼分別輸出網路G中的所有節點和邊緣。

mr_hi in G
G.has_node(mr_hi)

• 這兩行程式碼檢查節點mr_hi是否存在於網路G中。

(mr_hi, member_id) in G.edges
G.has_edge(mr_hi, member_id)

• 這兩行程式碼檢查Mr. Hi和特定的俱樂部成員之間是否存在邊緣，即他們是否是朋友。

list(G.neighbors(mr_hi))

• 這行程式碼輸出Mr. Hi的所有鄰居，即他的朋友。