neo4j python 算法_图论与图学习（二）：图算法
選自towardsdatascience
作者：Ma?l Fabien機(jī)器之心編譯參與：熊貓圖(graph)近來正逐漸變成機(jī)器學(xué)習(xí)的一大核心領(lǐng)域，比如你可以通過預(yù)測潛在的連接來理解社交網(wǎng)絡(luò)的結(jié)構(gòu)、檢測欺詐、理解汽車租賃服務(wù)的消費(fèi)者行為或進(jìn)行實(shí)時(shí)推薦。近日，數(shù)據(jù)科學(xué)家 Ma?l Fabien 在其博客上發(fā)布了涉及圖論、圖算法和圖學(xué)習(xí)的系列文章《圖論與圖學(xué)習(xí)》。
本文是其中第二篇，介紹了圖算法。更多文章和對應(yīng)代碼可訪問：https://github.com/maelfabien/Machine_Learning_Tutorials本文涵蓋以下主題：主要的圖算法
示意圖和用例
Python 示例
import?random
import?networkx?as?nx
from?IPython.display?import?Image
import?matplotlib.pyplot?as?plt后文會使用 networkx 最新的 2.0 版本。networkx 是一個(gè)用于復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)、動(dòng)態(tài)和功能的創(chuàng)建、操作和研究的 Python 軟件包。我會盡量以實(shí)用為目標(biāo)，努力闡釋每個(gè)概念。前一篇文章介紹了圖的主要種類以及描述一個(gè)圖的基本特性。現(xiàn)在我們更加詳細(xì)地介紹圖分析/算法以及分析圖的不同方式。為了理解上下文，這里給出一些圖算法的用例：
實(shí)時(shí)欺詐檢測
實(shí)時(shí)推薦
精簡法規(guī)遵從性
復(fù)雜網(wǎng)絡(luò)的管理和監(jiān)控
身份和訪問管理
社交應(yīng)用/功能
…
Pathfinding(尋路)：根據(jù)可用性和質(zhì)量等條件確定最優(yōu)路徑。我們也將搜索算法包含在這一類別中。這可用于確定最快路由或流量路由。
Centrality(中心性)：確定網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性。這可用于識別社交網(wǎng)絡(luò)中有影響力的人或識別網(wǎng)絡(luò)中潛在的攻擊目標(biāo)。
Community detection(社群檢測)：評估群體聚類的方式。這可用于劃分客戶或檢測欺詐等。
尋路算法是通過最小化跳(hop)的數(shù)量來尋找兩個(gè)節(jié)點(diǎn)之間的最短路徑。
搜索算法不是給出最短路徑，而是根據(jù)圖的相鄰情況或深度來探索圖。這可用于信息檢索。
寬度優(yōu)先搜索(BFS)：首先探索每個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，然后探索相鄰節(jié)點(diǎn)的相鄰節(jié)點(diǎn)……
深度優(yōu)先搜索(DFS)：會嘗試盡可能地深入一條路徑，如有可能便訪問新的相鄰節(jié)點(diǎn)。
將圖中所有節(jié)點(diǎn)標(biāo)記為未訪問。創(chuàng)建一個(gè)所有未訪問節(jié)點(diǎn)的集合，稱為未訪問集。
為每個(gè)節(jié)點(diǎn)分配一個(gè)暫定的距離值：將我們的初始節(jié)點(diǎn)的該值設(shè)置為零，將其它所有節(jié)點(diǎn)的該值設(shè)置為無窮。將初始起始節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)。
對于當(dāng)前節(jié)點(diǎn)，考察其所有未被訪問過的相鄰節(jié)點(diǎn)并計(jì)算通過當(dāng)前節(jié)點(diǎn)的暫定距離。比較新計(jì)算出的暫定距離與當(dāng)前分配的值，配之以其中更小的值。舉個(gè)例子，如果當(dāng)前節(jié)點(diǎn) A 標(biāo)記的距離為 6，將其與相鄰節(jié)點(diǎn) B 連接的邊的長度為 2，則通過 A 到達(dá) B 的距離為 6+2=8。如果 B 之前被標(biāo)記的距離大于 8，則將其改為 8。否則，保持其當(dāng)前的值。
當(dāng)我們考察完當(dāng)前節(jié)點(diǎn)的所有未訪問節(jié)點(diǎn)時(shí)，將當(dāng)前節(jié)點(diǎn)標(biāo)記為已訪問，并將其移出未訪問集。已訪問節(jié)點(diǎn)不會再次進(jìn)行檢查。
如果目標(biāo)節(jié)點(diǎn)已被標(biāo)記為已訪問(當(dāng)規(guī)劃兩個(gè)特定節(jié)點(diǎn)之間的路由時(shí))或未訪問集中節(jié)點(diǎn)之間的最小暫定距離為無窮時(shí)(當(dāng)規(guī)劃一次完整的遍歷時(shí)；當(dāng)初始節(jié)點(diǎn)與剩余的未訪問節(jié)點(diǎn)之間沒有連接時(shí)才會出現(xiàn)這種情況)，那么就停止操作。算法結(jié)束。
否則，選擇標(biāo)記有最小暫定距離的未訪問節(jié)點(diǎn)，將其設(shè)置為新的「當(dāng)前節(jié)點(diǎn)」，然后回到步驟 3。
nx.shortest_path(G_karate)這會返回圖中每個(gè)節(jié)點(diǎn)之間的最小路徑的列表：{0:?{0:?[0],
????1:?[0,?1],
????2:?[0,?2],
????...b. 單源最短路徑單源最短路徑(Single Source Shortest Path/SSSP)是找到給定節(jié)點(diǎn)與圖中其它所有節(jié)點(diǎn)之間的最短路徑。這常用于 IP 網(wǎng)絡(luò)的路由協(xié)議。c. 所有配對最短路徑所有配對最短路徑(All Pairs Shortest Path / APSP)算法是找到所有節(jié)點(diǎn)對之間的最短路徑。盡管能夠提供相近的結(jié)果，但這比為每個(gè)節(jié)點(diǎn)對調(diào)用單源最短路徑算法更快。該算法通常可用于確定交通網(wǎng)格的不同分區(qū)的流量負(fù)載。#?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,
????...d. 最小權(quán)重生成樹最小權(quán)重生成樹(minimum spanning tree)是圖(一個(gè)樹)的一個(gè)子圖，其用權(quán)重和最小的邊連接了圖中的所有節(jié)點(diǎn)。最小生成樹應(yīng)該用于無向圖。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),
...二 社群檢測社群檢測是根據(jù)給定的質(zhì)量指標(biāo)將節(jié)點(diǎn)劃分為多個(gè)分組。這通常可用于識別社交社群、客戶行為或網(wǎng)頁主題。社區(qū)是指一組相連節(jié)點(diǎn)的集合。但是，目前關(guān)于社群還沒有廣泛公認(rèn)的定義，只是社群內(nèi)的節(jié)點(diǎn)應(yīng)該要密集地相連。社群Girvan Newman 算法是一個(gè)用于發(fā)現(xiàn)社群的常用算法。其通過逐步移除網(wǎng)絡(luò)內(nèi)的邊來定義社區(qū)。我們將居間性稱為「邊居間性(edge betweenness)」。這是一個(gè)正比于穿過該邊的節(jié)點(diǎn)對之間最短路徑的數(shù)量的值。該算法的步驟如下：
計(jì)算網(wǎng)絡(luò)中所有已有邊的居間性。
移除居間性最高的邊。
移除該邊后，重新計(jì)算所有邊的居間性。
重復(fù)步驟 2 和 3，直到不再剩余邊。
comp?=?community.girvan_newman(G_karate)for?communities?in?itertools.islice(comp,?k):
????print(tuple(sorted(c)?for?c?in?communities))這會得到一個(gè)屬于每個(gè)社群的節(jié)點(diǎn)的列表(k=1 的意思是我們期望得到 2 個(gè)社群)：([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])如上給出的那樣，這個(gè)方法實(shí)在沒法擴(kuò)展。由于這個(gè)原因，Louvain 等方法已被開發(fā)出來。但是，如果要運(yùn)行大規(guī)模的圖，這些方法需要很長的時(shí)間。3. Louvain 模塊性在定義 Louvain 方法之前，需要介紹一下模塊性(modularity)的概念。模塊性是一個(gè)度量，衡量的是分組被劃分為聚類的程度：模塊性Louvain 方法的偽代碼如下：
首先為每個(gè)節(jié)點(diǎn)分配一個(gè)社群
交替執(zhí)行接下來的兩個(gè)步驟，直到收斂
創(chuàng)建一個(gè)帶有相鄰節(jié)點(diǎn)的新社群，以最大化模塊性
創(chuàng)建一個(gè)新的加權(quán)的圖。之前步驟的社群變成圖的節(jié)點(diǎn)。
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)使用 Louvain 對空手道圖執(zhí)行的最佳劃分4. 強(qiáng)互連的組分強(qiáng)互連的組分(Strongly Connected Components /SCC)算法能找到有向圖中的互連節(jié)點(diǎn)的分組。注意，在同一個(gè)分組中，每個(gè)節(jié)點(diǎn)都必須從任意其它節(jié)點(diǎn)從兩個(gè)方向都到達(dá)。這通常用在圖分析過程的早期階段，能讓我們了解圖構(gòu)建的方式。舉個(gè)例子，這能讓我們探索財(cái)務(wù)報(bào)表數(shù)據(jù)，了解誰擁有什么公司的股份。5. 弱互連的組分(并查集)弱互連的組分(Weakly Connected Components)，也稱為并查集(Union Find)算法，能找到有向圖中的互連節(jié)點(diǎn)的集合，在同一個(gè)集合中，每個(gè)節(jié)點(diǎn)都可從任意其它節(jié)點(diǎn)到達(dá)。這只需要節(jié)點(diǎn)對之間在一個(gè)方向上存在一條路徑即可，而 SCC 則需要兩個(gè)方向都存在路徑。和 SCC 一樣，并查集通常用在分析的早期階段，以理解圖的結(jié)構(gòu)。并查集是一個(gè)預(yù)處理步驟，為了理解圖的結(jié)構(gòu)，在任何算法之前都是必需的。我們可以使用下面的方法測試相連的有向圖：nx.is_weakly_connected(G)
nx.is_strongly_connected(G)或使用下面的方法測試無向圖：nx.is_connected(G_karate)這會返回一個(gè)布爾值。一定要看看 networkx 文檔中有關(guān)連接性實(shí)現(xiàn)的問題：https://networkx.github.io/documentation/stable/reference/algorithms/component.html6. 分層聚類在分層聚類(hierarchical clustering)中，我們構(gòu)建聚類的層次結(jié)構(gòu)。我們用樹狀圖的形式表示聚類。樹狀圖其思想是以不同的規(guī)模分析社群結(jié)構(gòu)。我們通常自下而上構(gòu)建樹狀圖。我們從每個(gè)節(jié)點(diǎn)一個(gè)聚類開始，然后合并兩個(gè)「最近」的節(jié)點(diǎn)。但我們?nèi)绾魏饬烤垲愂欠裣嘟?#xff1f;我們使用相似度距離。令 d(i,j) 為 i 和 j 之間的最短路徑的長度。相似度距離要得到最大連接，在每個(gè)步驟，被最短距離分開的兩個(gè)聚類被組合到一起。相似度距離可用以下示意圖闡釋：連接方式回到我們的空手道示例。在應(yīng)用分層聚類之前，我們需要定義每個(gè)節(jié)點(diǎn)之間的距離矩陣。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]現(xiàn)在，我們將使用 sklearn 的 AgglomerativeClustering 函數(shù)來確定分層聚類。from?sklearn.cluster?import?AgglomerativeClusteringclustering?=?AgglomerativeClustering(n_clusters=2,linkage='average',affinity='precomputed').fit_predict(distances)最后，根據(jù)聚類結(jié)果，用不同顏色繪出所得到的圖：nx.draw(G_karate,??node_color?=?clustering)分層聚類7. 聚類系數(shù)聚類系數(shù)衡量的是兩個(gè)節(jié)點(diǎn)傾向于聚類到一起的程度。局部聚類系數(shù)是以節(jié)點(diǎn) i 為中心的三角形的數(shù)量與以節(jié)點(diǎn) i 為中心的三節(jié)點(diǎn)的數(shù)量的比。某種程度而言，這衡量的是節(jié)點(diǎn) i 與其相鄰節(jié)點(diǎn)接近完備圖(complete graph)的程度。聚類系數(shù)我通過以下圖演示了聚類系數(shù)的計(jì)算：聚類系數(shù)全局聚類系數(shù)衡量的是圖中三角形(局部聚類)的密度：全局聚類系數(shù)上面的圖的全局聚類系數(shù)為：對于 Erdos-Rényi 隨機(jī)圖，E[Clustering Coefficient]=E[Ci]=p，其中 p 是前一篇文章中定義的概率。對于 Baràbasi-Albert 隨機(jī)圖，全局聚類系數(shù)根據(jù)節(jié)點(diǎn)的數(shù)量遵循冪律。度為 k 的節(jié)點(diǎn)的平均聚類系數(shù)正比于 k 的倒數(shù)：度較低的節(jié)點(diǎn)連接的是它們社群中的其它節(jié)點(diǎn)。度較高的節(jié)點(diǎn)連接的是其它社群的節(jié)點(diǎn)。對于一個(gè)給定的圖，在 networkx 中，聚類系數(shù)很容易算出。首先，我們來計(jì)算局部聚類系數(shù)：#?List?of?local?clustering?coefficients
list(nx.clustering(G_barabasi).values())這會得到類似下面的結(jié)果：0.13636363636363635,
0.2,
0.07602339181286549,
0.04843304843304843,
0.09,
0.055384615384615386,
0.07017543859649122,
...然后平均這些結(jié)果，得到該圖的全局聚類稀疏：#?Global?clustering?coefficient
np.mean(list(nx.clustering(G_barabasi).values()))這會得到：0.0965577637155059三 中心度算法中心度(Centrality)衡量的是節(jié)點(diǎn)的重要程度。這并非一個(gè)明晰的定義，但如果我們想要確定重要的網(wǎng)頁、交通網(wǎng)絡(luò)中的瓶頸……，那這就會很有用。游走(walk)是可以多次經(jīng)過同一個(gè)節(jié)點(diǎn)的路徑。根據(jù)所考慮的游走類型和統(tǒng)計(jì)它們的方式，中心度度量也會各有不同。1. PageRank 算法PageRank 是根據(jù)所連接的相鄰節(jié)點(diǎn)，然后再根據(jù)它們各自的相鄰節(jié)點(diǎn)估計(jì)當(dāng)前節(jié)點(diǎn)的重要性。盡管是谷歌讓這種算法流行起來的，但這種方法能夠用于檢測任何網(wǎng)絡(luò)中的高影響力節(jié)點(diǎn)。比如可用在社交網(wǎng)絡(luò)上進(jìn)行推薦。PageRank 要么是通過在相鄰節(jié)點(diǎn)上迭代地分配節(jié)點(diǎn)的秩(原本是基于度)來計(jì)算，要么是通過隨機(jī)遍歷圖并統(tǒng)計(jì)每次游走期間到達(dá)每個(gè)節(jié)點(diǎn)的頻率來計(jì)算。Neo4J 對 PageRank 算法的總結(jié)PageRank 通常是在有向圖上計(jì)算，但也可通過將有向圖中的每條邊轉(zhuǎn)換成兩條邊而在無向圖上執(zhí)行。舉個(gè)例子，空手道圖的 PageRank 可以這樣獲得：nx.pagerank(G_karate,?alpha=0.9)其中 alpha 是阻尼參數(shù)(默認(rèn)為 0.85)。這應(yīng)該能返回一個(gè)排名列表：{0:?0.09923208031303203,
?1:?0.0543403155825792,
?2:?0.05919704684187155,
?3:?0.036612460562853694,
...2. 度中心度度中心度(Degree Centrality)統(tǒng)計(jì)的是終止于節(jié)點(diǎn) i 的長度為 1 的游走的數(shù)量。這能夠衡量傳入和傳出關(guān)系。這能通過 C(Xi)=di 給出。度中心度可用于識別社交網(wǎng)絡(luò)中最有影響力的人。c_degree?=?nx.degree_centrality(G_karate)
c_degree?=?list(c_degree.values())3. 特征向量中心度特征向量中心度(Eigenvector Centrality)是終止于節(jié)點(diǎn) i 的長度為無窮的游走的數(shù)量。這能讓有很好連接相鄰節(jié)點(diǎn)的節(jié)點(diǎn)有更高的重要度。特征向量中心度c_eigenvector?=?nx.eigenvector_centrality(G_karate)
c_eigenvector?=?list(c_eigenvector.values())4. 接近度中心度接近度中心度(Closeness Centrality)檢測的是可以在圖中有效傳播信息的節(jié)點(diǎn)。這可用于識別假新聞賬戶或恐怖分子，以便隔離能向圖中其它部分傳播信息的個(gè)體。接近度中心度反比于到其它節(jié)點(diǎn)的最短路徑長度的總和。c_closeness?=?nx.closeness_centrality(G_karate)
c_closeness?=?list(c_closeness.values())5. 居間性中心度居間性中心度(Betweenness Centrality)檢測的是節(jié)點(diǎn)在圖中的信息流上所具有的影響量。這通常可用于發(fā)現(xiàn)用作從圖的一部分到另一部分的橋的節(jié)點(diǎn)，比如用在電信網(wǎng)絡(luò)的數(shù)據(jù)包傳遞處理器或假新聞傳播分析中。其中：
σ_jk 是 j 和 k 之間的最短路徑的數(shù)量
σ_jk(i) 是 j 和 k 之間的經(jīng)過 i 的最短路徑的數(shù)量
c_betweenness?=?list(c_betweenness.values())Python 中實(shí)現(xiàn)依賴于 networkx 的內(nèi)置函數(shù)：#?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)不同的中心度度量可以觀察到，不同的中心度度量關(guān)注的節(jié)點(diǎn)也不同。比如，居間性中心度得到的結(jié)果與其它方法的結(jié)果非常不同，因?yàn)樗鼈兒饬康牟皇峭粋€(gè)指標(biāo)。四 總結(jié)現(xiàn)在我們已經(jīng)介紹了圖的基礎(chǔ)知識、圖的主要類型、不同的圖算法和它們使用 networkx 的 Python 實(shí)現(xiàn)。下一篇文章我們將介紹圖學(xué)習(xí)，這能提供預(yù)測圖中節(jié)點(diǎn)和邊的方法，從而處理缺失值或預(yù)測新的關(guān)系。擴(kuò)展閱讀：
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
本文為機(jī)器之心編譯，轉(zhuǎn)載請聯(lián)系本公眾號獲得授權(quán)。
?------------------------------------------------
加入機(jī)器之心(全職記者 / 實(shí)習(xí)生)：hr@jiqizhixin.com
投稿或?qū)で髨?bào)道：content@jiqizhixin.com
廣告 & 商務(wù)合作：bd@jiqizhixin.com
總結(jié)
以上是生活随笔為你收集整理的neo4j python 算法_图论与图学习（二）：图算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
