NetworkX 網路分析入門

NetworkX 提供了豐富的工具和演算法，方便我們處理和分析各種網路結構。從簡單的無向網路到複雜的有向加權網路，NetworkX 都能有效地建模和分析。理解網路型別、邊權重和節點屬性是進行網路分析的基礎。透過使用 NetworkX，我們可以深入研究網路的拓撲結構、節點之間的關係，以及網路的動態行為。這對於理解和分析各種複雜系統至關重要，例如社交網路、交通網路、生物網路等等。

網路是什麼？第一章

網路型別與 NetworkX 簡介

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

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

網路型別

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

有向網路

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

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

加權網路

回到無向網路的情況，有時並非所有邊都是相等的。例如，在代表城市供水系統的網路中，邊可以代表一系列將水從一個地方運輸到另一個地方的管道。其中一些管道可能比其他管道具有更大的容量。當邊可以具有不同的強度時，網路被稱為加權網路，而強度則由一個稱為權重的數字來量化。

有向和無向網路都可以是加權的。加權網路的一個例子如下圖所示。在視覺化網路時，邊權重通常透過改變邊的厚度或透明度來表示。邊權重可以用於表示許多不同型別的屬性。最常見的屬性將在下一節中描述。

理解邊

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

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

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

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

網路科學入門：認識網路

網路科學是一門研究不同事物之間關係的學科。這些關係可以是社交網路中的朋友關係、交通網路中的道路連線，或是生物網路中的蛋白質互動作用。網路科學透過將這些關係建模為節點（nodes）之間的邊（edges），來量化和研究各種複雜的關係。

空間網路與邊的權重

在空間網路中，邊可以用來表示節點之間的距離或接近程度。當使用邊的權重來表示距離時，可以透過將路徑上的所有邊權重相加來計算整個行程的距離。然而，使用距離作為邊權重有時會令人混淆，因為較大的數字代表較弱的連線，而不存在的邊實際上是具有無限權重的邊。有時，使用接近程度的度量（如距離的倒數）可能更直觀，儘管這可能會使處理跨多條邊的路徑變得複雜。

import networkx as nx

# 建立一個無向無權圖
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')])

# 繪製網路視覺化圖
import matplotlib.pyplot as plt
plt.figure(figsize=(7.5, 7.5))
nx.draw_networkx(G)
plt.show()

內容解密：

• import networkx as nx：匯入NetworkX函式庫並將其別名設為nx，以便後續使用。
• G = nx.Graph()：建立一個無向無權圖物件G，代表一個無向網路。
• G.add_node('A') 和 G.add_nodes_from(['B', 'C'])：分別新增單個節點和多個節點到圖中。
• G.add_edge('A', 'B') 和 G.add_edges_from([('B', 'C'), ('A', 'C')])：新增邊到圖中，可以一次新增一條或多條。
• nx.draw_networkx(G)：使用NetworkX的繪圖功能將圖G視覺化。

使用NetworkX建立和視覺化網路

NetworkX是一個用於建立和操作複雜網路的Python函式庫。透過使用NetworkX，可以輕鬆地建立不同型別的網路並進行視覺化。

# 新增新的邊和節點
G.add_edges_from([('B', 'D'), ('C', 'E')])

# 重新繪製網路視覺化圖
nx.draw_networkx(G)
plt.show()

內容解密：

• G.add_edges_from([('B', 'D'), ('C', 'E')])：透過新增新的邊來新增新的節點D和E，因為這些節點在新增邊時自動被加入圖中。
• nx.draw_networkx(G)：再次繪製更新後的圖，包括新的節點和邊。

設定隨機種子以確保視覺化的一致性

由於NetworkX的視覺化有時使用隨機演算法，因此可以透過設定隨機種子來確保每次生成的視覺化結果相同。

import random
from numpy import random as nprand

seed = hash("Network Science in Python") % 2**32
nprand.seed(seed)
random.seed(seed)

內容解密：

• 設定隨機種子以確保NetworkX視覺化的一致性，避免每次執行時產生不同的結果。

參考資料

• Cohen, R., & Ruths, D. (2013). Classifying political orientation on Twitter: It’s not easy!. In Seventh International AAAI Conference on Weblogs and Social Media.
• Euler, L. (1953). Leonhard Euler and the Königsberg bridges. Scientific American, 189(1).
• Jernigan, C., & Mistree, B. F. (2009). Gaydar: Facebook friendships expose sexual orientation. First Monday, 14(10).
• Moreno, J. L., & Jennings, H. H. (1934). Who Shall Survive? Nervous and Mental Disease.
• Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab.
• 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處理網路資料

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

本章涵蓋以下主題

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

Graph類別 - 無向網路

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

建立與視覺化空手道俱樂部網路

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()建立以下視覺化：

與節點和邊緣互動

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

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

檢查特定節點是否存在是另一種簡單的互動方式。在Zachary的論文中，ID為0的節點被標識為俱樂部教練，Mr. Hi（一個化名）。可以使用Python的in運算元或Graph類別的has_node()方法輕鬆確認Mr. Hi的節點是否是網路的一部分，如下所示：

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

檢查節點鄰居

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

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

新增屬性到節點和邊緣

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

圖表翻譯：

此圖表顯示了Zachary空手道俱樂部的網路結構，節點代表俱樂部成員，邊緣代表成員之間的友誼。

為節點和邊緣新增屬性

在NetworkX中，可以為節點和邊緣新增屬性以儲存額外的資訊。這可以透過直接存取節點或邊緣的屬性字典來實作。例如：

G.nodes[mr_hi]['name'] = 'Mr. Hi'
G.edges[(mr_hi, member_id)]['weight'] = 1.0

節點屬性的使用範例

# 為Mr. Hi新增屬性
G.nodes[mr_hi]['role'] = 'instructor'
print(G.nodes[mr_hi])
# {'name': 'Mr. Hi', 'role': 'instructor'}

#### 內容解密：

上述程式碼演示瞭如何為特定的節點新增自定義屬性。首先，我們存取特定節點的屬性字典，然後直接在其中新增鍵值對。這種方法允許我們根據需要儲存任意數量的額外資訊。

圖表視覺化與分析

透過使用NetworkX提供的豐富功能，我們可以對複雜的網路資料進行深入的分析和視覺化。無論是社交網路、交通網路還是其他型別的複雜系統，NetworkX都提供了強大的工具來幫助我們理解和分析這些系統。

使用Plantuml表示網路結構

@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

圖表翻譯： 此圖表展示了一個簡單的社交網路結構，其中Mr. Hi與多名成員有直接聯絡，而這些成員之間也可能存在聯絡。

使用NetworkX處理網路結構 Chapter 2

在NetworkX中，Graph類別允許為節點新增任意數量的屬性。對於一個圖G，每個節點的屬性都儲存在G.nodes[v]這個字典中，其中v是節點的ID。以空手道俱樂部為例，當俱樂部分裂成兩個獨立的俱樂部後，可以為每個節點新增一個屬性，以描述相應成員在原始俱樂部解散後加入了哪個分裂的俱樂部。每個成員i加入的俱樂部由以下列表中的第i個元素給出：

member_club = [
0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
0, 0, 0, 0, 1, 1, 0, 0, 1, 0,
1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1]

內容解密：

這段程式碼定義了一個列表member_club，用於儲存每個成員加入的俱樂部編號。接下來，可以透過迭代所有節點ID並根據member_club中的值設定節點屬性，將此資訊新增到圖G中。

for node_id in G.nodes:
    G.nodes[node_id]["club"] = member_club[node_id]

內容解密：

這段程式碼遍歷圖G中的所有節點，並為每個節點新增一個名為"club"的屬性，其值來自member_club列表中對應的索引。

此外，在新增新節點時也可以自動新增屬性，方法是透過在節點ID之後傳遞關鍵字引數給add_node()：

G.add_node(11, club=0)

內容解密：

這行程式碼新增了一個ID為11的節點，並設定其"club"屬性為0。

現在，所有節點的"club"屬性都已設定好，可以檢查個別節點的屬性值：

G.nodes[mr_hi]
{'club': 0}
G.nodes[john_a]
{'club': 1}

內容解密：

這兩行程式碼分別檢查了節點mr_hi和john_a的屬性，顯示他們分別屬於不同的俱樂部。

為了視覺化這些不同的俱樂部，可以根據節點的"club"屬性為其分配不同的顏色。建立一個節點顏色列表，然後將其傳遞給draw_networkx()函式：

node_colors = [
    '#1f78b4' if G.nodes[v]["club"] == 0
    else '#33a02c' for v in G]
nx.draw_networkx(G, karate_pos, label=True, node_color=node_colors)

內容解密：

這段程式碼根據節點的"club"屬性建立了一個顏色列表，並將其傳遞給draw_networkx()函式，以不同顏色繪製屬於不同俱樂部的節點。

為邊新增屬性

為邊新增屬性與為節點新增屬性類別似。在圖G中，邊的屬性儲存在G.edges[v, w]這個字典中，其中v和w是邊的端點節點ID。由於Graph類別代表無向網路，因此也可以透過G.edges[w, v]存取這些屬性。

在空手道俱樂部網路中，一些邊連線了加入相同分裂俱樂部的成員，而其他邊則連線了來自不同分裂俱樂部的成員。可以透過迭代所有邊並檢查邊端點是否具有相同的"club"屬性，將此資訊儲存在圖G中，使用邊屬性來表示。

for v, w in G.edges:
    if G.nodes[v]["club"] == G.nodes[w]["club"]:
        G.edges[v, w]["internal"] = True
    else:
        G.edges[v, w]["internal"] = False

內容解密：

這段程式碼遍歷圖G中的所有邊，並根據邊端點的"club"屬性是否相同，設定邊的"internal"屬性為True或False。

接下來，可以將內部和外部邊分別以不同的線條樣式繪製出來：

internal = [e for e in G.edges if G.edges[e]["internal"]]
external = [e for e in G.edges if ~G.edges[e]["internal"]]
nx.draw_networkx_nodes(G, karate_pos, node_color=node_colors)
nx.draw_networkx_labels(G, karate_pos)
nx.draw_networkx_edges(G, karate_pos, edgelist=internal)
nx.draw_networkx_edges(G, karate_pos, edgelist=external, style="dashed")

內容解密：

這段程式碼首先區分內部和外部邊，然後分別繪製節點、標籤、內部邊和外部邊，其中外部邊以虛線表示。

新增邊權重

除了無權重的邊之外，Graph類別也支援帶權重的邊。邊權重在連線具有不同強度時非常有用，例如兩個朋友之間的互動頻率、管道輸送流體的容量或兩個城市之間的直飛航班數量。

在空手道俱樂部網路中，可以計算出每條邊的緊密度（tie strength），它隨著兩個節點共同鄰居的數量增加而增加。這可以透過以下程式碼計算：

def tie_strength(G, v, w):
    v_neighbors = set(G.neighbors(v))
    w_neighbors = set(G.neighbors(w))
    return 1 + len(v_neighbors & w_neighbors)

for v, w in G.edges:
    G.edges[v, w]["weight"] = tie_strength(G, v, w)
edge_weights = [G.edges[v, w]["weight"] for v, w in G.edges]

內容解密：

這段程式碼定義了一個函式tie_strength()來計算兩個節點之間的緊密度，然後遍歷所有邊，計算每條邊的緊密度並將其作為權重儲存在圖G中。最後，將所有邊的權重儲存在一個列表中。