長文|三大主題全方位梳理圖論與圖學習中的基本概念:圖搜索,最短路徑,聚類係數,中心度等

最近發現關注深度學習與圖網絡的很多同學都是剛入門圖學習，今天特意把之前收藏的一份關於圖論與圖學習基本概念(二)的博文分享給大家，如果你是剛入門，這是一篇必讀的博文了，希望能給你帶來一些啟發，建議用電腦打開，可以敲一下文中的代碼，理解其中具體概念的含義。圖（graph）近來正逐漸變成機器學習的一大核心領域，比如你可以通過預測潛在的連接來理解社交網絡的結構、檢測欺詐、理解汽車租賃服務的消費者行為或進行實時推薦。近日，數據科學家 Maël Fabien 在其博客上發布了涉及圖論、圖算法和圖學習的系列文章《圖論與圖學習》。本文是其中第二篇，介紹了圖算法前面一篇。更多文章和對應代碼可訪問：https://github.com/maelfabien/Machine_Learning_Tutorials首先進行一些準備工作，打開 Jupyter Notebook，導入以下軟體包：

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

後文會使用 networkx 最新的 2.0 版本。networkx 是一個用於複雜網絡的結構、動態和功能的創建、操作和研究的 Python 軟體包。前一篇文章介紹了圖的主要種類以及描述一個圖的基本特性。現在我們更加詳細地介紹圖分析/算法以及分析圖的不同方式。

實時欺詐檢測

實時推薦

精簡法規遵從性

複雜網絡的管理和監控

身份和訪問管理

社交應用/功能

…

目前大多數框架（比如 Python 的 networkx 或 Neo4J）支持的圖算法類別主要有三個：

Pathfinding（尋路）：根據可用性和質量等條件確定最優路徑。我們也將搜索算法包含在這一類別中。這可用於確定最快路由或流量路由。

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

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

networkx 中的所有算法都可在這裡找到：https://networkx.github.io/documentation/stable/reference/algorithms/index.html我們只會介紹 networkx 中實現的最常見的基本算法。最短路徑計算的是一對節點之間的最短的加權（如果圖有加權的話）路徑。這可用於確定最優的駕駛方向或社交網絡上兩個人之間的分離程度。計算圖中的最短路徑的方法有很多，包括 Dijkstra 算法，這是 networkx 中的默認算法。

將圖中所有節點標記為未訪問。創建一個所有未訪問節點的集合，稱為未訪問集。

為每個節點分配一個暫定的距離值：將我們的初始節點的該值設置為零，將其它所有節點的該值設置為無窮。將初始起始節點設置為當前節點。

對於當前節點，考察其所有未被訪問過的相鄰節點並計算通過當前節點的暫定距離。比較新計算出的暫定距離與當前分配的值，配之以其中更小的值。舉個例子，如果當前節點 A 標記的距離為 6，將其與相鄰節點 B 連接的邊的長度為 2，則通過 A 到達 B 的距離為 6+2=8。如果 B 之前被標記的距離大於 8，則將其改為 8。否則，保持其當前的值。

當我們考察完當前節點的所有未訪問節點時，將當前節點標記為已訪問，並將其移出未訪問集。已訪問節點不會再次進行檢查。

如果目標節點已被標記為已訪問（當規劃兩個特定節點之間的路由時）或未訪問集中節點之間的最小暫定距離為無窮時（當規劃一次完整的遍歷時；當初始節點與剩餘的未訪問節點之間沒有連接時才會出現這種情況），那麼就停止操作。算法結束。

否則，選擇標記有最小暫定距離的未訪問節點，將其設置為新的「當前節點」，然後回到步驟 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）是找到給定節點與圖中其它所有節點之間的最短路徑。所有配對最短路徑（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,
    ...

最小權重生成樹（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),
...

社群檢測是根據給定的質量指標將節點劃分為多個分組。社區是指一組相連節點的集合。但是，目前關於社群還沒有廣泛公認的定義，只是社群內的節點應該要密集地相連。Girvan Newman 算法是一個用於發現社群的常用算法。其通過逐步移除網絡內的邊來定義社區。我們將居間性稱為「邊居間性（edge betweenness）」。這是一個正比於穿過該邊的節點對之間最短路徑的數量的值。

計算網絡中所有已有邊的居間性。

移除居間性最高的邊。

移除該邊後，重新計算所有邊的居間性。

重複步驟 2 和 3，直到不再剩餘邊。

from networkx.algorithms import communityk = 1
comp = community.girvan_newman(G_karate)for communities in itertools.islice(comp, k):
    print(tuple(sorted(c) for c in communities))

這會得到一個屬於每個社群的節點的列表（k=1 的意思是我們期望得到 2 個社群）：

([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])

如上給出的那樣，這個方法實在沒法擴展。由於這個原因，Louvain 等方法已被開發出來。但是，如果要運行大規模的圖，這些方法需要很長的時間。在定義 Louvain 方法之前，需要介紹一下模塊性（modularity）的概念。模塊性是一個度量，衡量的是分組被劃分為聚類的程度：這個現在可能看起來有些讓人迷惑。事實上，我們現在唯一做的事情是將最近的節點劃分為分組，以便我們優化模塊性指標。注意，Louvain 方法沒有理論上的保證，但實踐效果很好。Louvain 方法是 networkx 的一個子項目，參閱：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)

強互連的組分（Strongly Connected Components /SCC）算法能找到有向圖中的互連節點的分組。注意，在同一個分組中，每個節點都必須從任意其它節點從兩個方向都到達。這通常用在圖分析過程的早期階段，能讓我們了解圖構建的方式。舉個例子，這能讓我們探索財務報表數據，了解誰擁有什麼公司的股份。弱互連的組分（Weakly Connected Components），也稱為併查集（Union Find）算法，能找到有向圖中的互連節點的集合，在同一個集合中，每個節點都可從任意其它節點到達。這只需要節點對之間在一個方向上存在一條路徑即可，而 SCC 則需要兩個方向都存在路徑。和 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在分層聚類（hierarchical clustering）中，我們構建聚類的層次結構。我們用樹狀圖的形式表示聚類。其思想是以不同的規模分析社群結構。我們通常自下而上構建樹狀圖。我們從每個節點一個聚類開始，然後合併兩個「最近」的節點。但我們如何衡量聚類是否相近呢？我們使用相似度距離。令 d(i,j) 為 i 和 j 之間的最短路徑的長度。要得到最大連接，在每個步驟，被最短距離分開的兩個聚類被組合到一起。相似度距離可用以下示意圖闡釋：回到我們的空手道示例。在應用分層聚類之前，我們需要定義每個節點之間的距離矩陣。

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）的程度。全局聚類係數衡量的是圖中三角形（局部聚類）的密度：對於 Erdos-Rényi 隨機圖，E[Clustering Coefficient]=E[Ci]=p，其中 p 是前一篇文章中定義的概率。對於 Baràbasi-Albert 隨機圖，全局聚類係數根據節點的數量遵循冪律。度為 k 的節點的平均聚類係數正比於 k 的倒數：度較低的節點連接的是它們社群中的其它節點。度較高的節點連接的是其它社群的節點。對於一個給定的圖，在 networkx 中，聚類係數很容易算出。首先，我們來計算局部聚類係數：

# 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()))

中心度（Centrality）衡量的是節點的重要程度。這並非一個明晰的定義，但如果我們想要確定重要的網頁、交通網絡中的瓶頸……，那這就會很有用。遊走（walk）是可以多次經過同一個節點的路徑。根據所考慮的遊走類型和統計它們的方式，中心度度量也會各有不同。
PageRank 是根據所連接的相鄰節點，然後再根據它們各自的相鄰節點估計當前節點的重要性。儘管是谷歌讓這種算法流行起來的，但這種方法能夠用於檢測任何網絡中的高影響力節點。比如可用在社交網絡上進行推薦。PageRank 要麼是通過在相鄰節點上迭代地分配節點的秩（原本是基於度）來計算，要麼是通過隨機遍歷圖並統計每次遊走期間到達每個節點的頻率來計算。PageRank 通常是在有向圖上計算，但也可通過將有向圖中的每條邊轉換成兩條邊而在無向圖上執行。舉個例子，空手道圖的 PageRank 可以這樣獲得：

nx.pagerank(G_karate, alpha=0.9)

其中 alpha 是阻尼參數（默認為 0.85）。這應該能返回一個排名列表：

{0: 0.09923208031303203,
 1: 0.0543403155825792,
 2: 0.05919704684187155,
 3: 0.036612460562853694,
...

度中心度（Degree Centrality）統計的是終止於節點 i 的長度為 1 的遊走的數量。這能夠衡量傳入和傳出關係。這能通過 C(Xi)=di 給出。度中心度可用於識別社交網絡中最有影響力的人。

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

特徵向量中心度（Eigenvector Centrality）是終止於節點 i 的長度為無窮的遊走的數量。

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

接近度中心度（Closeness Centrality）檢測的是可以在圖中有效傳播信息的節點。這可用於識別假新聞帳戶或恐怖分子，以便隔離能向圖中其它部分傳播信息的個體。接近度中心度反比於到其它節點的最短路徑長度的總和。

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

居間性中心度（Betweenness Centrality）檢測的是節點在圖中的信息流上所具有的影響量。這通常可用於發現用作從圖的一部分到另一部分的橋的節點，比如用在電信網絡的數據包傳遞處理器或假新聞傳播分析中。居間性中心度衡量的是一個節點用作兩個節點之間的橋的次數，比如：

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

Python 中實現依賴於 networkx 的內置函數：

# 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)

可以觀察到，不同的中心度度量關注的節點也不同。比如，居間性中心度得到的結果與其它方法的結果非常不同，因為它們衡量的不是同一個指標。現在我們已經介紹了圖的基礎知識、圖的主要類型、不同的圖算法和它們使用 networkx 的 Python 實現。下一篇文章我們將介紹圖學習，這能提供預測圖中節點和邊的方法，從而處理缺失值或預測新的關係。

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/

原文連結：https://towardsdatascience.com/graph-algorithms-part-2-dce0b2734a1d