社會網絡分析——三、圖論與圖學習

中間被很多人轉了，我是從機器之心公衆号（almosthuman2014）看到的，最初來源應該是 Maël Fabien 大佬的部落格，緻謝

https://github.com/maelfabien/Machine_Learning_Tutorials

• 目錄：
  • 第一部分：圖介紹
    • 圖是什麼？
    • 如何存儲圖？
    • 圖的類型和性質
    • Python 示例
  • 第二部分：圖算法
    • Pathfinding（尋路）
    • Community detection（社群檢測）
    • Centrality（中心性）
• 背景：
  • 圖（graph）近來正逐漸變成機器學習的一大核心領域，比如你可以通過預測潛在的連接配接來了解社交網絡的結構、檢測欺詐、了解汽車租賃服務的消費者行為或進行實時推薦。
• 涉及到的python包：
  • networkx 是一個用于複雜網絡的結構、動态和功能的建立、操作和研究的 Python 軟體包，選擇networkx 2.0 版本。

import numpy as np
import random
import networkx as nx
from IPython.display import Image
import matplotlib.pyplot as plt
           

1.1 圖是什麼？

• 概念：圖是互連節點的集合。
• 作用：社交網絡、網頁、生物網絡…
• 我們可以在圖上執行怎樣的分析？
  • 研究拓撲結構和連接配接性、群體檢測、識别中心節點、預測缺失的節點、預測缺失的邊…

（1）空手道圖為例的圖建構：

# Load the graph
G_karate = nx.karate_club_graph()
# Find key-values for the graph
pos = nx.spring_layout(G_karate)
# Plot the graph
nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)
           

「空手道」圖：Wayne W. Zachary 在 1970 到 1972 年這三年中研究的一個空手道俱樂部的社交網絡。該網絡包含了這個空手道俱樂部的 34 個成員，成員對之間的連接配接表示他們在俱樂部之外也有聯系。在研究期間，管理者 JohnA 與教練 Mr.Hi（化名）之間出現了沖突，導緻俱樂部一分為二。一半成員圍繞 Mr.Hi 形成了一個新的俱樂部，另一半則找了一個新教練或放棄了空手道。基于收集到的資料，除了其中一個成員，Zachary 正确配置設定了所有成員在分裂之後所進入的分組。

（2）圖的基本表示方法

圖 G=(V, E) 由下列要素構成：

• 一組節點（也稱為 verticle）：V=1,…,n
• 一組邊： E⊆V×V
  • 邊 (i,j) ∈ E 連接配接了節點 i 和 j
  • 相鄰節點：i 和 j 被稱為相鄰節點（neighbor）
  • 節點度：節點的度（degree）是指相鄰節點的數量

    

（3）圖中常見的概念

• 完備圖：如果一個圖的所有節點都有 n-1 個相鄰節點，則該圖是完備的（complete），也就是說所有節點都具備所有可能的連接配接方式。
• 路徑與路徑長度：從 i 到 j 的路徑（path）是指從 i 到達 j 的邊的序列，該路徑的長度（length）等于所經過的邊的數量。
• 圖直徑：圖的直徑（diameter）是指連接配接任意兩個節點的所有最短路徑中最長路徑的長度。
• 測地路徑：測地路徑（geodesic path）是指兩個節點之間的最短路徑。
• 圖連通與連通分量：如果所有節點都可通過某個路徑連接配接到彼此，則它們構成一個連通分量（connected component）。如果一個圖僅有一個連通分量，則該圖是連通的（connected）。
  • 有兩個不同連通分量的圖：

    

• 有向圖，出度與入度：如果一個圖的邊是有順序的配對，則該圖是有向的（directed）。i 的入度（in-degree）是指向 i 的邊的數量，出度（out-degree）是遠離 i 的邊的數量。
• 有環圖與無環圖：如果可以回到一個給定節點，則該圖是有環的（cyclic）。相對地，如果至少有一個節點無法回到，則該圖就是無環的（acyclic）。
• 權重圖：圖可以被權重（weighted），即在節點或關系上施權重重。
• 稀疏與密集：如果一個圖的邊數量相比于節點數量較小，則該圖是稀疏的（sparse）。相對地，如果節點之間的邊非常多，則該圖是密集的（dense）。

（4）總結：

• Neo4J 的關于圖算法的書給出了清晰明了的總結：

（5）python示例：

n=34
G_karate.degree() # 傳回該圖的每個節點的度（相鄰節點的數量）的清單
''' 結果
DegreeView({0: 16, 1: 9, 2: 10, 3: 6, 4: 3, 5: 4, 6: 4, 7: 4, 8: 5, 9: 2, 10: 3, 11: 1, 12: 2, 13: 5, 14: 2, 15: 2, 16: 2, 17: 2, 18: 2, 19: 3, 20: 2, 21: 2, 22: 2, 23: 5, 24: 3, 25: 3, 26: 2, 27: 4, 28: 3, 29: 4, 30: 4, 31: 6, 32: 12, 33: 17})
'''

# Isolate the sequence of degrees 隔離度
degree_sequence = list(G_karate.degree())

# 計算邊的數量，但也計算度序列的度量
nb_nodes = n
nb_arr = len(G_karate.edges())
avg_degree = np.mean(np.array(degree_sequence)[:,1])
med_degree = np.median(np.array(degree_sequence)[:,1])
max_degree = max(np.array(degree_sequence)[:,1])
min_degree = np.min(np.array(degree_sequence)[:,1])

# 列印所有資訊：
print("Number of nodes : " + str(nb_nodes))
print("Number of edges : " + str(nb_arr))
print("Maximum degree : " + str(max_degree))
print("Minimum degree : " + str(min_degree))
print("Average degree : " + str(avg_degree))
print("Median degree : " + str(med_degree))

''' 結論：
Number of nodes : 34
Number of edges : 78
Maximum degree : 17
Minimum degree : 1
Average degree : 4.588235294117647  # 平均而言，該圖中的每個人都連接配接了 4.6 個人
Median degree : 3.0
'''

# 繪出這些度的直方圖
# 度的直方圖相當重要，可用于确定我們看到的圖的種類
degree_freq = np.array(nx.degree_histogram(G_karate)).astype('float')
plt.figure(figsize=(12, 8))
plt.stem(degree_freq)
plt.ylabel("Frequence")
plt.xlabel("Degre")
plt.show()
           

1.2 如何存儲圖？

存儲圖的方式有三種，最好的表示方式取決于用法和可用的記憶體，以及你想用它做什麼：

• 邊集數組：存儲有邊連接配接的每一對節點的 ID。
• 鄰接矩陣：通常是在記憶體中加載的方式，對于圖中的每一個可能的配對，如果兩個節點有邊相連，則設為 1。如果該圖是無向圖，則 A 是對稱的：

  • 

• 鄰接清單：
  • 如

    1:[2,3,4]

    表示與節點1相連的邊有2、3、4。

圖可能包含一些擴充：

• 權重的邊
• 節點/邊上加标簽
• 加上與節點/邊相關的特征向量

1.3 圖的類型

兩種主要的圖類型：

• Erdos-Rényi
• Barabasi-Albert

（1）Erdos-Rényi 模型

• 定義
  • 在 Erdos-Rényi 模型中，我們建構一個帶有 n 個節點的随機圖模型。這個圖是通過以機率 p 獨立地在節點 (i,j) 對之間畫邊來生成的。是以，我們有兩個參數：節點數量 n 和機率 p。

  • 

• python生成 Erdos-Rényi 圖的内置函數

# Generate the graph
n = 50
p = 0.2
G_erdos = nx.erdos_renyi_graph(n,p, seed =100)
# Plot the graph
plt.figure(figsize=(12,8))
nx.draw(G_erdos, node_size=10)
           

• 度分布
  • 令 pk 為随機選取的節點的度為 k 的機率。由于圖建構所使用的随機方式，這種圖的度的分布是二項式的
    • 公式： p k = ( n − 1 k ) p k ( 1 − p ) n − 1 − k p_k=\begin{pmatrix}n-1\\k\end{pmatrix}p^k(1-p)^{n-1-k} pk​=(n−1k​)pk(1−p)n−1−k）
  • 每個節點的度數量的分布應該非常接近于均值，觀察到高數量節點的機率呈指數下降。

degree_freq = np.array(nx.degree_histogram(G_erdos)).astype('float')
plt.figure(figsize=(12, 8))
plt.stem(degree_freq)
plt.ylabel("Frequence")
plt.xlabel("Degree")
plt.show()
           

• 描述性統計
  • 平均度：n×p（在 p=0.2 和 n=200 時，中心在 40 左右）
  • 度期望： (n−1)×p
  • 平均值附近的度最多

# Get the list of the degrees
degree_sequence_erdos = list(G_erdos.degree())

nb_nodes = n
nb_arr = len(G_erdos.edges())

avg_degree = np.mean(np.array(degree_sequence_erdos)[:,1])
med_degree = np.median(np.array(degree_sequence_erdos)[:,1])

max_degree = max(np.array(degree_sequence_erdos)[:,1])
min_degree = np.min(np.array(degree_sequence_erdos)[:,1])

esp_degree = (n-1)*p

print("Number of nodes : " + str(nb_nodes))
print("Number of edges : " + str(nb_arr))

print("Maximum degree : " + str(max_degree))
print("Minimum degree : " + str(min_degree))

print("Average degree : " + str(avg_degree))
print("Expected degree : " + str(esp_degree))
print("Median degree : " + str(med_degree))

'''結果：
Number of nodes : 200
Number of edges : 3949
Maximum degree : 56
Minimum degree : 25
Average degree : 39.49
Expected degree : 39.800000000000004
Median degree : 39.5
這裡的平均度和期望度非常接近，因為兩者之間隻有很小的因子
'''
           

（2）Barabasi-Albert 模型

• 定義
  • 在 Barabasi-Albert 模型中，我們建構一個有 n 個節點的随機圖模型，其有一個優先連接配接（preferential attachment）分量。這種圖可通過以下算法生成：
    • 步驟 1：以機率 p 執行步驟 2，否則執行步驟 3
    • 步驟 2：将一個新節點連接配接到随機均勻選取的已有節點
    • 步驟 3：以與 n 個已有節點成比例的機率将這個新節點連接配接到這 n 個已有節點
  • 這個圖的目标是模組化優先連接配接（preferential attachment），真實世界網絡中常會觀察到這一點。（注：優先連接配接是指根據各個個體或對象已有的量來配置設定某個量，這通常會進一步加大優勢個體的優勢。）
• python生成 Barabasi-Albert 圖的内置函數

# Generate the graph
n = 150
m = 3
G_barabasi = nx.barabasi_albert_graph(n,m)
# Plot the graph
plt.figure(figsize=(12,8))
nx.draw(G_barabasi, node_size=10)
           

• 度分布
  • 令 pk 為随機選取的節點的度為 k 的機率。則這個度分布遵循幂律
    • 公式： p k ∝ k − α p_k\propto k^{-\alpha} pk​∝k−α
  • 這個分布是重尾分布，其中有很多節點的度都很小，但也有相當數量的節點有較高的度。

# 據說這個分布是無标度的（scale-free），平均度不能提供資訊
degree_freq = np.array(nx.degree_histogram(G_barabasi)).astype('float')
plt.figure(figsize=(12, 8))
plt.stem(degree_freq)
plt.ylabel("Frequence")
plt.xlabel("Degree")
plt.show()
           

• 描述性統計
  • 如果 α≤2，平均度為一個常量，否則就會發散。
  • 最大度遵照以下順序： O ( n 1 α − 1 ) O(n^{\frac{1}{\alpha-1}}) O(nα−11​)

# Get the list of the degrees
degree_sequence_erdos = list(G_erdos.degree())

nb_nodes = n
nb_arr = len(G_erdos.edges())

avg_degree = np.mean(np.array(degree_sequence_erdos)[:,1])
med_degree = np.median(np.array(degree_sequence_erdos)[:,1])

max_degree = max(np.array(degree_sequence_erdos)[:,1])
min_degree = np.min(np.array(degree_sequence_erdos)[:,1])

esp_degree = (n-1)*p

print("Number of nodes : " + str(nb_nodes))
print("Number of edges : " + str(nb_arr))

print("Maximum degree : " + str(max_degree))
print("Minimum degree : " + str(min_degree))

print("Average degree : " + str(avg_degree))
print("Expected degree : " + str(esp_degree))
print("Median degree : " + str(med_degree))

''' 結果：
Number of nodes : 200
Number of edges : 3949
Maximum degree : 56
Minimum degree : 25
Average degree : 39.49
Expected degree : 39.800000000000004
Median degree : 39.5
'''
           

2.1 算法1：尋路和圖搜尋算法

Pathfinding（尋路）：根據可用性和品質等條件确定最優路徑。我們也将搜尋算法包含在這一類别中。這可用于确定最快路由或流量路由。

• 尋路算法：通過最小化跳（hop）的數量來尋找兩個節點之間的最短路徑。
• 搜尋算法：不是給出最短路徑，而是根據圖的相鄰情況或深度來探索圖，可用于資訊檢索。

（1）搜尋算法

• 圖搜尋算法的分類：
  • 寬度優先搜尋（BFS）：首先探索每個節點的相鄰節點，然後探索相鄰節點的相鄰節點。
  • 深度優先搜尋（DFS）：會嘗試盡可能地深入一條路徑，如有可能便通路新的相鄰節點。

  • 

（2）尋路算法1：最短路徑

• 定義：
  • 計算的是一對節點之間的最短的權重（如果圖有權重的話）路徑。
  • 可用于确定最優的駕駛方向或社交網絡上兩個人之間的分離程度。
• 計算方法：
  • 有SPFA，Dijsktra等，以 Dijkstra 算法為例
  • 1、未通路集建構：将圖中所有節點标記為未通路。建立一個所有未通路節點的集合，稱為未通路集。
  • 2、為每個節點配置設定暫定距離值：将我們的初始節點的該值設定為零，将其它所有節點的該值設定為無窮。将初始起始節點設定為目前節點。
  • 3、為每個節點枚舉計算新的暫定距離：對于目前節點，考察其所有未被通路過的相鄰節點并計算通過目前節點的暫定距離。比較新計算出的暫定距離與目前配置設定的值，配之以其中更小的值。
    • 舉例：如果目前節點 A 标記的距離為 6，将其與相鄰節點 B 連接配接的邊的長度為 2，則通過 A 到達 B 的距離為 6+2=8。如果 B 之前被标記的距離大于 8，則将其改為 8。否則，保持其目前的值。
  • 4、已通路标記：當我們考察完目前節點的所有未通路節點時，将目前節點标記為已通路，并将其移出未通路集。已通路節點不會再次進行檢查。
  • 5、是否結束詢問：如果目标節點已被标記為已通路（當規劃兩個特定節點之間的路由時）或未通路集中節點之間的最小暫定距離為無窮時（當規劃一次完整的周遊時；當初始節點與剩餘的未通路節點之間沒有連接配接時才會出現這種情況），那麼就停止操作。算法結束。
  • 6、新的疊代：否則，選擇标記有最小暫定距離的未通路節點，将其設定為新的「目前節點」，然後回到步驟 3。

更多最短路徑問題的介紹：https://en.wikipedia.org/wiki/Shortest_path_problem

# Returns shortest path between each node
nx.shortest_path(G_karate) # 傳回圖中每個節點之間的最小路徑的清單
'''結果
{0: {0: [0],
    1: [0, 1],
    2: [0, 2],
    ...
'''
           

• 最短路徑分類：
  • 單源最短路徑（Single Source Shortest Path/SSSP）：找到給定節點與圖中其它所有節點之間的最短路徑，這常用于 IP 網絡的路由協定。
  • 所有配對最短路徑（All Pairs Shortest Path / APSP）：找到所有節點對之間的最短路徑（比為每個節點對調用單源最短路徑算法更快）。該算法通常可用于确定交通網格的不同分區的流量負載。

# Returns shortest path length between each node
list(nx.all_pairs_shortest_path_length(G_karate))

'''結果
[(0,
    {0: 0,
    1: 1,
    2: 1,
    3: 1,
    4: 1,
    ...
'''
           

（3）尋路算法2：最小權重生成樹

• 最小權重生成樹（minimum spanning tree）：是圖（一個樹）的一個子圖，其用權重和最小的邊連接配接了圖中的所有節點，應該用于無向圖。

from networkx.algorithms import tree
mst = tree.minimum_spanning_edges(G_karate, algorithm='prim', data=False)
edgelist = list(mst)
sorted(edgelist)

'''
[(0, 1),
(0, 2),
(0, 3),
(0, 4),
(0, 5),
(0, 6),
'''
           

2.2 社群檢測

Community detection（社群檢測）：評估群體聚類的方式。這可用于劃分客戶或檢測欺詐等。

• 定義：社群檢測是根據給定的品質名額将節點劃分為多個分組。
• 作用：可用于識别社交社群、客戶行為或網頁主題。
• 概念：
  • 社群/社群：指一組相連節點的集合。目前還沒有廣泛公認的定義，隻是社群内的節點應該要密集地相連。

  • 

（1）Girvan Newman 算法

• 定義：
  • Girvan Newman 算法是一個用于發現社群的常用算法，其通過逐漸移除網絡内的邊來定義社群
  • 邊居間性（edge betweenness）：正比于穿過該邊的節點對之間最短路徑的數量的值
• 算法步驟：
  • 1 計算網絡中所有已有邊的居間性。
  • 2 移除居間性最高的邊。
  • 3 移除該邊後，重新計算所有邊的居間性。
  • 4 重複步驟 2 和 3，直到不再剩餘邊。
• 弊端：
  • 這個算法沒法擴充；如果要運作大規模的圖，耗時較大；

from networkx.algorithms import community
k = 1 # k=1 的意思是我們期望得到 2 個社群
comp = community.girvan_newman(G_karate)
for communities in itertools.islice(comp, k):
    print(tuple(sorted(c) for c in communities))

''' 得到一個屬于每個社群的節點的清單：
([0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21], [2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33])
'''
           

（2）Louvain 算法

• 子產品性（modularity）
  • 子產品性是一個度量，衡量的是分組被劃分為聚類的程度

  • 

• Louvain 算法：
  • 1 首先為每個節點配置設定一個社群
  • 2 建立一個帶有相鄰節點的新社群，以最大化子產品性
  • 3 建立一個新的權重圖，之前步驟的社群變成圖的新節點。
  • 4 交替執行步驟1 2，直到收斂

  • 

• 算法評估：Louvain 方法沒有理論上的保證，但實踐效果很好（https://python-louvain.readthedocs.io/en/latest/）

pip install python-louvain  # 安裝軟體包

# 基于 Louvain 方法，計算最佳的劃分方式
import community
partition = community.best_partition(G_karate)pos = nx.spring_layout(G_karate)
plt.figure(figsize=(8, 8))
plt.axis('off')
nx.draw_networkx_nodes(G_karate, pos, node_size=600, cmap=plt.cm.RdYlBu, node_color=list(partition.values()))
nx.draw_networkx_edges(G_karate, pos, alpha=0.3)
plt.show(G_karate)
           

（3）強互連與弱互連的組分算法

• 強互連的組分（Strongly Connected Components /SCC）算法
  • 能找到有向圖中的互連節點的分組，在同一個分組中，每個節點都必須從任意其它節點從兩個方向都到達。
• 弱互連的組分（Weakly Connected Components），也稱為并查集（Union Find）算法
  • 能找到有向圖中的互連節點的集合，在同一個集合中，每個節點都可從任意其它節點到達。
• 差別：
  • WCC：需要節點對之間在一個方向上存在一條路徑即可
  • SCC：需要節點對之間在兩個方向都存在路徑
• 用途：
  • 這通常用在圖分析過程的早期階段，能讓我們了解圖建構的方式（舉例：探索财務報表資料，了解誰擁有什麼公司的股份）

# 測試相連的有向圖：
nx.is_weakly_connected(G)
nx.is_strongly_connected(G)

# 測試無向圖：
nx.is_connected(G_karate)
           

networkx 文檔中有關連接配接性實作的問題：https://networkx.github.io/documentation/stable/reference/algorithms/component.html

（4）分層聚類

• 分層聚類（hierarchical clustering）：建構聚類的層次結構，用樹狀圖的形式表示聚類。

  • 

• 核心思想： 以不同的規模分析社群結構。
  • 構造：通常自下而上建構樹狀圖，從每個節點一個聚類開始，然後合并兩個「最近」的節點
  • 衡量聚類是否相近：相似度距離，令 d(i,j) 為 i 和 j 之間的最短路徑的長度。
    • Maximum linkage： D ( C 1 ， C 2 ) = min ⁡ i ∈ C 1 , j ∈ C 2 d ( i , j ) D(C_1，C_2)=\min_{i\in C_1,j\in C_2}{d(i,j)} D(C1​，C2​)=mini∈C1​,j∈C2​​d(i,j)
    • Average linkage： D ( C 1 ， C 2 ) = 1 ∣ C 1 ∣ ∣ C 2 ∣ ∑ i ∈ C 1 , j ∈ C 2 d ( i , j ) D(C_1，C_2)=\frac{1}{|C_1||C_2|}\sum_{i\in C_1,j\in C_2}{d(i,j)} D(C1​，C2​)=∣C1​∣∣C2​∣1​∑i∈C1​,j∈C2​​d(i,j)
    • Centroid linkage： D ( C 1 ， C 2 ) = d ( G 1 , G 2 ) D(C_1，C_2)=d(G_1,G_2) D(C1​，C2​)=d(G1​,G2​)，where G 1 G_1 G1​ and G 2 G_2 G2​ are the centers of G 1 G_1 G1​, G 2 G_2 G2​
  • 示意圖：

    • 

# 在應用分層聚類之前，定義每個節點之間的距離矩陣
pcc_longueurs=list(nx.all_pairs_shortest_path_length(G_karate))
distances=np.zeros((n,n)) # distances[i, j] is the length of the shortest path between i and j
for i in range(n):
	for j in range(n):
        distances[i, j] = pcc_longueurs[i][1][j]

# 使用 sklearn 的 AgglomerativeClustering 函數來确定分層聚類
from sklearn.cluster import AgglomerativeClusteringclustering = AgglomerativeClustering(n_clusters=2,linkage='average',affinity='precomputed').fit_predict(distances)

# 根據聚類結果，用不同顔色繪出所得到的圖：
nx.draw(G_karate,  node_color = clustering)
           

• 聚類系數：兩個節點傾向于聚類到一起的程度
  • 局部聚類系數：以節點 i 為中心的三角形的數量 與 以節點 i 為中心的三節點的數量 的比，衡量的是節點 i 與其相鄰節點接近完備圖（complete graph）的程度。
    • 公式： C i = T r i a n g l e s i T r i p l e s i C_i=\frac{Triangles_i}{Triples_i} Ci​=Triplesi​Trianglesi​​

    • 

  • 全局聚類系數：衡量的是圖中三角形（局部聚類）的密度
    • 公式： C C = 1 n ∑ i C i CC=\frac{1}{n}\sum_{i}C_i CC=n1​∑i​Ci​
  • 特殊圖中案例：
    • 對于 Erdos-Rényi 随機圖： E [ C l u s t e r i n g C o e f f i c i e n t ] = E [ C i ] = p E[Clustering Coefficient]=E[Ci]=p E[ClusteringCoefficient]=E[Ci]=p
    • 對于 Baràbasi-Albert 随機圖：全局聚類系數根據節點的數量遵循幂律，度為 k 的節點的平均聚類系數正比于 k 的倒數： C ( k ∝ k − 1 ) C(k \propto k^{-1}) C(k∝k−1)
      • 度較低的節點連接配接的是它們社群中的其它節點，度較高的節點連接配接的是其它社群的節點。

# 計算局部聚類系數，List of local clustering coefficients
list(nx.clustering(G_barabasi).values())

'''
0.13636363636363635,
0.2,
0.07602339181286549,
0.04843304843304843,
0.09,
0.055384615384615386,
0.07017543859649122,
'''
# 平均這些結果，得到該圖的全局聚類系數，Global clustering coefficient
np.mean(list(nx.clustering(G_barabasi).values()))

'''
0.0965577637155059
'''
           

3.3 中心度算法

Centrality（中心性）：确定網絡中節點的重要性。這可用于識别社交網絡中有影響力的人或識别網絡中潛在的攻擊目标。

• 中心度（Centrality）：衡量節點重要程度
• 遊走（walk）：可以多次經過同一個節點的路徑，根據所考慮的遊走類型和統計它們的方式，中心度度量也會各有不同。

（1）PageRank 算法

• PageRank 是根據所連接配接的相鄰節點，然後再根據它們各自的相鄰節點估計目前節點的重要性
  • 計算方法1：通過在相鄰節點上疊代地配置設定節點的秩（原本基于度）
  • 計算方法2：通過随機周遊圖并統計每次遊走期間到達每個節點的頻率

    

• 用途：
  • 谷歌的搜尋引擎的網頁權重評估
  • 也能夠用于檢測任何網絡中的高影響力節點，比如可用 在社交網絡上進行推薦。
• Neo4J 對 PageRank 算法的總結
  • PageRank 通常是在有向圖上計算，但也可通過将有向圖中的每條邊轉換成兩條邊而在無向圖上執行。
• 案例

nx.pagerank(G_karate, alpha=0.9)  # alpha 是阻尼參數（預設為 0.85）
''' 傳回一個排名清單：
{0: 0.09923208031303203,
 1: 0.0543403155825792,
 2: 0.05919704684187155,
 3: 0.036612460562853694,
 '''
           

（2）度中心度（Degree Centrality）

• 度中心度：終止于節點 i 的、長度為 1 的 遊走數量，這能夠衡量傳入和傳出關系，可用于識别社交網絡中最有影響力的人。
  • 公式： C ( X i ) = d i C(X_i)=d_i C(Xi​)=di​

c_degree = nx.degree_centrality(G_karate)
c_degree = list(c_degree.values())
           

（3）特征向量中心度（Eigenvector Centrality）

• 特征向量中心度：終止于節點 i 的、長度為無窮的 遊走數量，這能讓有很好連接配接相鄰節點的節點有更高的重要度。
  • 公式： C ( X i ) = 1 λ ∑ j A i j C ( X j ) C(X_i)=\frac{1}{\lambda}\sum_{j}A_{ij}C(X_j) C(Xi​)=λ1​∑j​Aij​C(Xj​)，where λ \lambda λ the largest eigenvalue of A A A

c_eigenvector = nx.eigenvector_centrality(G_karate)
c_eigenvector = list(c_eigenvector.values())
           

（4）接近度中心度（Closeness Centrality）

• 接近度中心度：反比于到其它節點的最短路徑長度的總和。檢測的是可以在圖中有效傳播資訊的節點，這可用于識别假新聞賬戶或恐怖分子，以便隔離能向圖中其它部分傳播資訊的個體。
  • 公式： C ( X i ) = 1 ∑ j ≠ i d ( i , j ) C(X_i)=\frac{1}{\sum_{j\ne i}d(i,j)} C(Xi​)=∑j​=i​d(i,j)1​

c_closeness = nx.closeness_centrality(G_karate)
c_closeness = list(c_closeness.values())
           

（5）中間中心度（Betweenness Centrality）

• 中間中心度：檢測的是節點在圖中的資訊流上所具有的影響量，可用于發現用作從圖的一部分到另一部分的橋的節點，比如用在電信網絡的資料包傳遞處理器或假新聞傳播分析中，衡量的是一個節點用作兩個節點之間的橋的次數。
  • 公式： C ( X i ) = ∑ j ≠ i , i ≠ k σ j k ( i ) σ j k C(X_i)=\sum_{j\ne i, i\ne k} \frac{\sigma_{jk}(i)}{\sigma_{jk}} C(Xi​)=∑j​=i,i​=k​σjk​σjk​(i)​
    • σ j k \sigma_{jk} σjk​：j 和 k 之間的最短路徑的數量
    • σ j k ( i ) \sigma_{jk}(i) σjk​(i)：j 和 k 之間的經過 i 的最短路徑的數量

  • 

c_betweenness = nx.betweenness_centrality(G_karate)
c_betweenness = list(c_betweenness.values())
           

（6）總結

# Plot the centrality of the nodes
plt.figure(figsize=(18, 12))# Degree Centrality
f, axarr = plt.subplots(2, 2, num=1)
plt.sca(axarr[0,0])
nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_degree, node_size=300, pos=pos, with_labels=True)
axarr[0,0].set_title('Degree Centrality', size=16)# Eigenvalue Centrality
plt.sca(axarr[0,1])
nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_eigenvector, node_size=300, pos=pos, with_labels=True)
axarr[0,1].set_title('Eigenvalue Centrality', size=16)# Proximity Centrality
plt.sca(axarr[1,0])
nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_closeness, node_size=300, pos=pos, with_labels=True)
axarr[1,0].set_title('Proximity Centrality', size=16)# Betweenness Centrality
plt.sca(axarr[1,1])
nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_betweenness, node_size=300, pos=pos, with_labels=True)
axarr[1,1].set_title('Betweenness Centrality', size=16)
           

• 不同的中心度度量關注的節點也不同。比如，居間性中心度得到的結果與其它方法的結果非常不同，因為它們衡量的不是同一個名額。

擴充閱讀：

• Neo4j 的圖算法全面指南，Mark Needham & Amy E. Hodler：https://go.neo4j.com/rs/710-RRC-335/images/Comprehensive-Guide-to-Graph-Algorithms-in-Neo4j-ebook-EN-US.pdf
• Networkx 文檔：https://networkx.github.io/documentation/stable/