圖（graph）近來正逐漸變成機(jī)器學(xué)習(xí)的一大核心領(lǐng)域痴怨，比如你可以通過預(yù)測(cè)潛在的連接來理解社交網(wǎng)絡(luò)的結(jié)構(gòu)文判、檢測(cè)欺詐、理解汽車租賃服務(wù)的消費(fèi)者行為或進(jìn)行實(shí)時(shí)推薦橡庞。近日，數(shù)據(jù)科學(xué)家 Ma?l Fabien 在其博客上發(fā)布了涉及圖論印蔗、圖算法和圖學(xué)習(xí)的系列文章《圖論與圖學(xué)習(xí)》扒最。

本文是其中第二篇，介紹了圖算法华嘹。更多文章和對(duì)應(yīng)代碼可訪問：https://github.com/maelfabien/Machine_Learning_Tutorials

本文涵蓋以下主題：

• 主要的圖算法
• 示意圖和用例
• Python 示例

首先進(jìn)行一些準(zhǔn)備工作吧趣，打開 Jupyter Notebook，導(dǎo)入以下軟件包：

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

后文會(huì)使用 networkx 最新的 2.0 版本耙厚。networkx 是一個(gè)用于復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)强挫、動(dòng)態(tài)和功能的創(chuàng)建、操作和研究的 Python 軟件包薛躬。
前一篇文章介紹了圖的主要種類以及描述一個(gè)圖的基本特性「┎常現(xiàn)在我們更加詳細(xì)地介紹圖分析/算法以及分析圖的不同方式。為了理解上下文型宝，這里給出一些圖算法的用例：

• 實(shí)時(shí)欺詐檢測(cè)
• 實(shí)時(shí)推薦
• 精簡(jiǎn)法規(guī)遵從性
• 復(fù)雜網(wǎng)絡(luò)的管理和監(jiān)控
• 身份和訪問管理
• 社交應(yīng)用/功能
• …

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

• Pathfinding（尋路）：根據(jù)可用性和質(zhì)量等條件確定最優(yōu)路徑八匠。我們也將搜索算法包含在這一類別中。這可用于確定最快路由或流量路由趴酣。

• Centrality（中心性）：確定網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性梨树。這可用于識(shí)別社交網(wǎng)絡(luò)中有影響力的人或識(shí)別網(wǎng)絡(luò)中潛在的攻擊目標(biāo)。

• Community detection（社群檢測(cè)）：評(píng)估群體聚類的方式岖寞。這可用于劃分客戶或檢測(cè)欺詐等抡四。

我們將在第三篇文章中介紹圖中的機(jī)器學(xué)習(xí)和圖學(xué)習(xí)。

networkx 中的所有算法都可在這里找到：https://networkx.github.io/documentation/stable/reference/algorithms/index.html

我們只會(huì)介紹 networkx 中實(shí)現(xiàn)的最常見的基本算法慎璧。

一. 尋路和圖搜索算法

尋路算法是通過最小化跳（hop）的數(shù)量來尋找兩個(gè)節(jié)點(diǎn)之間的最短路徑床嫌。搜索算法不是給出最短路徑，而是根據(jù)圖的相鄰情況或深度來探索圖胸私。這可用于信息檢索厌处。

1. 搜索算法

圖搜索算法主要有兩種：

• 寬度優(yōu)先搜索（BFS）：首先探索每個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，然后探索相鄰節(jié)點(diǎn)的相鄰節(jié)點(diǎn)

• 深度優(yōu)先搜索（DFS）：會(huì)嘗試盡可能地深入一條路徑岁疼，如有可能便訪問新的相鄰節(jié)點(diǎn)阔涉。

  
  
  BFS和DFS

2. 尋路算法

a. 最短路徑

最短路徑計(jì)算的是一對(duì)節(jié)點(diǎn)之間的最短的加權(quán)（如果圖有加權(quán)的話）路徑缆娃。

這可用于確定最優(yōu)的駕駛方向或社交網(wǎng)絡(luò)上兩個(gè)人之間的分離程度。

計(jì)算圖中的最短路徑的方法有很多瑰排，包括 Dijkstra 算法贯要，這是 networkx 中的默認(rèn)算法。

根據(jù)維基百科椭住，該算法的偽代碼如下：

• 將圖中所有節(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)些举。

• 對(duì)于當(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 連接的邊的長(zhǎng)度為 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)不會(huì)再次進(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í)才會(huì)出現(xiàn)這種情況）辕坝，那么就停止操作窍奋。算法結(jié)束。

• 否則酱畅，選擇標(biāo)記有最小暫定距離的未訪問節(jié)點(diǎn)琳袄，將其設(shè)置為新的「當(dāng)前節(jié)點(diǎn)」，然后回到步驟 3纺酸。

更多有關(guān)最短路徑問題的介紹請(qǐng)參閱：https://en.wikipedia.org/wiki/Shortest_path_problem

維基百科上 Dijkstra 算法示意圖

該算法的 Python 實(shí)現(xiàn)簡(jiǎn)單直接：

# Returns shortest path between each node
nx.shortest_path(G_karate)

這會(huì)返回圖中每個(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. 所有配對(duì)最短路徑

所有配對(duì)最短路徑（All Pairs Shortest Path / APSP）算法是找到所有節(jié)點(diǎn)對(duì)之間的最短路徑餐蔬。

盡管能夠提供相近的結(jié)果碎紊，但這比為每個(gè)節(jié)點(diǎn)對(duì)調(diào)用單源最短路徑算法更快佑附。該算法通常可用于確定交通網(wǎng)格的不同分區(qū)的流量負(fù)載仗考。

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

這會(huì)返回：

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

這會(huì)返回：

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

二. 社群檢測(cè)

社群檢測(cè)是根據(jù)給定的質(zhì)量指標(biāo)將節(jié)點(diǎn)劃分為多個(gè)分組权均。
這通常可用于識(shí)別社交社群锅锨、客戶行為或網(wǎng)頁主題螺句。社區(qū)是指一組相連節(jié)點(diǎn)的集合。但是橡类，目前關(guān)于社群還沒有廣泛公認(rèn)的定義，只是社群內(nèi)的節(jié)點(diǎn)應(yīng)該要密集地相連芽唇。

社群

1. Girvan Newman 算法

Girvan Newman 算法是一個(gè)用于發(fā)現(xiàn)社群的常用算法顾画。其通過逐步移除網(wǎng)絡(luò)內(nèi)的邊來定義社區(qū)。我們將居間性稱為「邊居間性（edge betweenness）」匆笤。這是一個(gè)正比于穿過該邊的節(jié)點(diǎn)對(duì)之間最短路徑的數(shù)量的值研侣。

該算法的步驟如下：

• 計(jì)算網(wǎng)絡(luò)中所有已有邊的居間性。
• 移除居間性最高的邊炮捧。
• 移除該邊后庶诡，重新計(jì)算所有邊的居間性。
• 重復(fù)步驟 2 和 3咆课，直到不再剩余邊末誓。

你可以通過 Python 使用以下代碼實(shí)現(xiàn)它：

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

這會(huì)得到一個(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ī)模的圖晴玖，這些方法需要很長(zhǎng)的時(shí)間。

2. 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)莲祸。

這個(gè)現(xiàn)在可能看起來有些讓人迷惑琅催。事實(shí)上居凶，我們現(xiàn)在唯一做的事情是將最近的節(jié)點(diǎn)劃分為分組，以便我們優(yōu)化模塊性指標(biāo)藤抡。

image

Louvain 方法
注意侠碧，Louvain 方法沒有理論上的保證，但實(shí)踐效果很好缠黍。Louvain 方法是 networkx 的一個(gè)子項(xiàng)目弄兜，參閱：https://python-louvain.readthedocs.io/en/latest/

首先，安裝軟件包：

pip install python-louvain

然后瓷式，計(jì)算最佳的劃分方式（基于 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)

使用 Louvain 對(duì)空手道圖執(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)對(duì)之間在一個(gè)方向上存在一條路徑即可期虾，而 SCC 則需要兩個(gè)方向都存在路徑原朝。和 SCC 一樣，并查集通常用在分析的早期階段镶苞，以理解圖的結(jié)構(gòu)竿拆。

并查集是一個(gè)預(yù)處理步驟，為了理解圖的結(jié)構(gòu)宾尚，在任何算法之前都是必需的丙笋。

我們可以使用下面的方法測(cè)試相連的有向圖：

nx.is_weakly_connected(G)
nx.is_strongly_connected(G)

或使用下面的方法測(cè)試無向圖：

nx.is_connected(G_karate)

這會(huì)返回一個(gè)布爾值。

一定要看看 networkx 文檔中有關(guān)連接性實(shí)現(xiàn)的問題：https://networkx.github.io/documentation/stable/reference/algorithms/component.html

6.分層聚類

在分層聚類（hierarchical clustering）中煌贴，我們構(gòu)建聚類的層次結(jié)構(gòu)御板。我們用樹狀圖的形式表示聚類。

樹狀圖

其思想是以不同的規(guī)模分析社群結(jié)構(gòu)牛郑。我們通常自下而上構(gòu)建樹狀圖怠肋。我們從每個(gè)節(jié)點(diǎn)一個(gè)聚類開始，然后合并兩個(gè)「最近」的節(jié)點(diǎn)淹朋。
但我們?nèi)绾魏饬烤垲愂欠裣嘟伢细鳎课覀兪褂孟嗨贫染嚯x钉答。令 d(i,j) 為 i 和 j 之間的最短路徑的長(zhǎng)度。

相似度距離

要得到最大連接杈抢，在每個(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 AgglomerativeClustering
clustering = 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ù)

全局<mark data-type="concepts" data-id="de069734-8912-43fb-b365-3b014165bc4d" class="tooltipstered" style="box-sizing: border-box; line-height: 2; padding: 0.2em; background-color: transparent; color: inherit; cursor: pointer; border-bottom: 1px solid rgb(235, 40, 53);">聚類</mark>系數(shù)

上面的圖的全局聚類系數(shù)為：

image

對(duì)于 Erdos-Rényi 隨機(jī)圖，E[Clustering Coefficient]=E[Ci]=p朦乏，其中 p 是前一篇文章中定義的概率。
對(duì)于 Baràbasi-Albert 隨機(jī)圖氧骤，全局聚類系數(shù)根據(jù)節(jié)點(diǎn)的數(shù)量遵循冪律呻疹。度為 k 的節(jié)點(diǎn)的平均聚類系數(shù)正比于 k 的倒數(shù)：

image

度較低的節(jié)點(diǎn)連接的是它們社群中的其它節(jié)點(diǎn)。度較高的節(jié)點(diǎn)連接的是其它社群的節(jié)點(diǎn)筹陵。

對(duì)于一個(gè)給定的圖刽锤，在 networkx 中，聚類系數(shù)很容易算出朦佩。首先并思，我們來計(jì)算局部聚類系數(shù)：

# List of local clustering coefficients
list(nx.clustering(G_barabasi).values())

這會(huì)得到類似下面的結(jié)果：

0.13636363636363635,
0.2,
0.07602339181286549,
0.04843304843304843,
0.09,
0.055384615384615386,
0.07017543859649122,
...

然后平均這些結(jié)果，得到該圖的全局聚類系數(shù)：

# Global clustering coefficient
np.mean(list(nx.clustering(G_barabasi).values()))

這會(huì)得到：

0.0965577637155059

三. 中心度算法

中心度（Centrality）衡量的是節(jié)點(diǎn)的重要程度语稠。這并非一個(gè)明晰的定義宋彼，但如果我們想要確定重要的網(wǎng)頁、交通網(wǎng)絡(luò)中的瓶頸……仙畦，那這就會(huì)很有用输涕。

游走（walk）是可以多次經(jīng)過同一個(gè)節(jié)點(diǎn)的路徑。根據(jù)所考慮的游走類型和統(tǒng)計(jì)它們的方式慨畸，中心度度量也會(huì)各有不同莱坎。

1. PageRank 算法

PageRank 是根據(jù)所連接的相鄰節(jié)點(diǎn)，然后再根據(jù)它們各自的相鄰節(jié)點(diǎn)估計(jì)當(dāng)前節(jié)點(diǎn)的重要性寸士。
盡管是谷歌讓這種算法流行起來的檐什，但這種方法能夠用于檢測(cè)任何網(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 對(duì) 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 的長(zhǎng)度為 1 的游走的數(shù)量搭综。

這能夠衡量傳入和傳出關(guān)系垢箕。這能通過 C(Xi)=di 給出。度中心度可用于識(shí)別社交網(wǎng)絡(luò)中最有影響力的人兑巾。

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

3. 特征向量中心度

特征向量中心度（Eigenvector Centrality）是終止于節(jié)點(diǎn) i 的長(zhǎng)度為無窮的游走的數(shù)量条获。

這能讓有很好連接相鄰節(jié)點(diǎn)的節(jié)點(diǎn)有更高的重要度。

image

特征向量中心度

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

4. 接近度中心度

接近度中心度（Closeness Centrality）檢測(cè)的是可以在圖中有效傳播信息的節(jié)點(diǎn)蒋歌。

這可用于識(shí)別假新聞賬戶或恐怖分子帅掘，以便隔離能向圖中其它部分傳播信息的個(gè)體。

image

接近度中心度反比于到其它節(jié)點(diǎn)的最短路徑長(zhǎng)度的總和堂油。

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

5. 居間性中心度

居間性中心度（Betweenness Centrality）檢測(cè)的是節(jié)點(diǎn)在圖中的信息流上所具有的影響量修档。

這通常可用于發(fā)現(xiàn)用作從圖的一部分到另一部分的橋的節(jié)點(diǎn)府框，比如用在電信網(wǎng)絡(luò)的數(shù)據(jù)包傳遞處理器或假新聞傳播分析中吱窝。

image

其中：

• σ_jk 是 j 和 k 之間的最短路徑的數(shù)量

• σ_jk(i) 是 j 和 k 之間的經(jīng)過 i 的最短路徑的數(shù)量

居間性中心度衡量的是一個(gè)節(jié)點(diǎn)用作兩個(gè)節(jié)點(diǎn)之間的橋的次數(shù)，比如：

中心度度量

c_betweenness = nx.betweenness_centrality(G_karate)
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ǔ)知識(shí)、圖的主要類型盹牧、不同的圖算法和它們使用 networkx 的 Python 實(shí)現(xiàn)俩垃。

下一篇文章我們將介紹圖學(xué)習(xí)，這能提供預(yù)測(cè)圖中節(jié)點(diǎn)和邊的方法汰寓，從而處理缺失值或預(yù)測(cè)新的關(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