原文鏈接： https://mp.weixin.qq.com/mp/profile_ext?action=home\x26amp;__biz=MzI0ODcxODk5OA==\x26amp;scene=124#wechat_redirect
作者 |?Rahul Agarwal
譯者 |?Monanfei
編輯 | Jane
出品 | AI科技大本營(yíng)（ID：rgznai100）
作為數(shù)據(jù)科學(xué)家，我們已經(jīng)對(duì) Pandas 或 SQL 等其他關(guān)系數(shù)據(jù)庫(kù)非常熟悉了。我們習(xí)慣于將行中的用戶視為列。但現(xiàn)實(shí)世界的表現(xiàn)真的如此嗎？
?
在互聯(lián)世界中，用戶不能被視為獨(dú)立實(shí)體。他們之間具有一定的關(guān)系，在構(gòu)建機(jī)器學(xué)習(xí)模型時(shí)，有時(shí)也希望包含這樣的關(guān)系。
?
在關(guān)系型數(shù)據(jù)庫(kù)中，我們無(wú)法在不同的行（用戶）之間使用這種關(guān)系，但在圖形數(shù)據(jù)庫(kù)中，這樣做是相當(dāng)簡(jiǎn)單的。
在這篇文章中將為大家介紹一些重要的圖算法，以及Python 的代碼實(shí)現(xiàn)。
1、連通分量
?
具有三個(gè)連通分量的圖
?
將上圖中的連通分量算法近似看作一種硬聚類算法，該算法旨在尋找相關(guān)數(shù)據(jù)的簇類。舉一個(gè)具體的例子：假設(shè)擁有連接世界上任意城市的路網(wǎng)數(shù)據(jù)，我們需要找出世界上所有的大陸，以及它們所包含的城市。我們?cè)撊绾螌?shí)現(xiàn)這一目標(biāo)呢？
?
基于BFS / DFS的連通分量算法能夠達(dá)成這一目的，接下來(lái)，我們將用 Networkx 實(shí)現(xiàn)這一算法。
?
代碼
使用 Python 中的 Networkx 模塊來(lái)創(chuàng)建和分析圖數(shù)據(jù)庫(kù)。如下面的示意圖所示，圖中包含了各個(gè)城市和它們之間的距離信息。
?
示意圖
?
首先創(chuàng)建邊的列表，列表中每個(gè)元素包含兩個(gè)城市的名稱，以及它們之間的距離。
?
edgelist
= [[
'Mannheim'
,
'Frankfurt'
,
85
], [
'Mannheim'
,
'Karlsruhe'
,
80
], [
'Erfurt'
,
'Wurzburg'
,
186
], [
'Munchen'
,
'Numberg'
,
167
], [
'Munchen'
,
'Augsburg'
,
84
], [
'Munchen'
,
'Kassel'
,
502
], [
'Numberg'
,
'Stuttgart'
,
183
], [
'Numberg'
,
'Wurzburg'
,
103
], [
'Numberg'
,
'Munchen'
,
167
], [
'Stuttgart'
,
'Numberg'
,
183
], [
'Augsburg'
,
'Munchen'
,
84
], [
'Augsburg'
,
'Karlsruhe'
,
250
], [
'Kassel'
,
'Munchen'
,
502
], [
'Kassel'
,
'Frankfurt'
,
173
], [
'Frankfurt'
,
'Mannheim'
,
85
], [
'Frankfurt'
,
'Wurzburg'
,
217
], [
'Frankfurt'
,
'Kassel'
,
173
], [
'Wurzburg'
,
'Numberg'
,
103
], [
'Wurzburg'
,
'Erfurt'
,
186
], [
'Wurzburg'
,
'Frankfurt'
,
217
], [
'Karlsruhe'
,
'Mannheim'
,
80
], [
'Karlsruhe'
,
'Augsburg'
,
250
],[
"Mumbai"
,
"Delhi"
,
400
],[
"Delhi"
,
"Kolkata"
,
500
],[
"Kolkata"
,
"Bangalore"
,
600
],[
"TX"
,
"NY"
,
1200
],[
"ALB"
,
"NY"
,
800
]]
?
然后，使用 Networkx 創(chuàng)建圖：
g = nx.Graph()
for
edge
in
edgelist:
g.add_edge(edge[
0
],edge[
1
], weight = edge[
2
])
?
現(xiàn)在，我們想從這張圖中找出不同的大陸及其包含的城市。我們可以使用使用連通分量算法來(lái)執(zhí)行此操作：
?
for
i, x
in
enumerate(nx.connected_components(g)):
print
(
"cc"
+str(i)+
":"
,x)
------------------------------------------------------------
cc0: {
'Frankfurt'
,
'Kassel'
,
'Munchen'
,
'Numberg'
,
'Erfurt'
,
'Stuttgart'
,
'Karlsruhe'
,
'Wurzburg'
,
'Mannheim'
,
'Augsburg'
}
cc1: {
'Kolkata'
,
'Bangalore'
,
'Mumbai'
,
'Delhi'
}
cc2: {
'ALB'
,
'NY'
,
'TX'
}
從結(jié)果中可以看出，只需使用邊緣和頂點(diǎn)，我們就能在數(shù)據(jù)中找到不同的連通分量。?該算法可以在不同的數(shù)據(jù)上運(yùn)行，以滿足前文提到的兩種其他運(yùn)用。
?
應(yīng)用
?
-
零售：很多客戶使用大量賬戶，可以利用連通分量算法尋找數(shù)據(jù)集中的不同簇類。假設(shè)使用相同信用卡的客戶 ID 存在連邊（edges），或者將該條件替換為相同的住址，或者相同的電話等。一旦我們有了這些連接的邊，就可以使用連通分量算法來(lái)對(duì)客戶 ID 進(jìn)行聚類，并對(duì)每個(gè)簇類分配一個(gè)家庭 ID。然后，通過(guò)使用這些家庭 ID，我們可以根據(jù)家庭需求提供個(gè)性化建議。此外，通過(guò)創(chuàng)建基于家庭的分組功能，我們還能夠提高分類算法的性能。
?
-
財(cái)務(wù)：我們可以利用這些家庭 ID 來(lái)識(shí)別金融欺詐。如果某個(gè)賬戶曾經(jīng)有過(guò)欺詐行為，那么它的關(guān)聯(lián)帳戶很可能發(fā)生欺詐行為。
?
2、最短路徑
?
繼續(xù)第一節(jié)中的例子，我們擁有了德國(guó)的城市群及其相互距離的圖表。為了計(jì)算從法蘭克福前往慕尼黑的最短路徑，我們需要用到 Dijkstra 算法。Dijkstra 是這樣描述他的算法的：
?
從鹿特丹到格羅寧根的最短途徑是什么？或者換句話說(shuō)：從特定城市到特定城市的最短路徑是什么？這便是最短路徑算法，而我只用了二十分鐘就完成了該算法的設(shè)計(jì)。?一天早上，我和未婚妻在阿姆斯特丹購(gòu)物，我們逛累了，便在咖啡館的露臺(tái)上喝了一杯咖啡。而我，就想著我能夠做到這一點(diǎn)，于是我就設(shè)計(jì)了這個(gè)最短路徑算法。正如我所說(shuō)，這是一個(gè)二十分鐘的發(fā)明。事實(shí)上，它發(fā)表于1959年，也就是三年后。它之所以如此美妙，其中一個(gè)原因在于我沒(méi)有用鉛筆和紙張就設(shè)計(jì)了它。后來(lái)我才知道，沒(méi)有鉛筆和紙的設(shè)計(jì)的一個(gè)優(yōu)點(diǎn)就是，你幾乎被迫避免所有可避免的復(fù)雜性。最終，這個(gè)算法讓我感到非常驚訝，而且也成為了我名聲的基石之一。
——Edsger Dijkstra于2001年接受ACM通訊公司 Philip L. Frana 的采訪時(shí)的回答
?
代碼
print
(nx.shortest_path(g,
'Stuttgart'
,
'Frankfurt'
,weight=
'weight'
))
print
(nx.shortest_path_length(g,
'Stuttgart'
,
'Frankfurt'
,weight=
'weight'
))
--------------------------------------------------------
[
'Stuttgart'
,
'Numberg'
,
'Wurzburg'
,
'Frankfurt'
]
503
使用以下命令可以找到所有對(duì)之間的最短路徑：
?
for
x
in
nx.all_pairs_dijkstra_path(g,weight=
'weight'
):
print
(x)
--------------------------------------------------------
(
'Mannheim'
, {
'Mannheim'
: [
'Mannheim'
],
'Frankfurt'
: [
'Mannheim'
,
'Frankfurt'
],
'Karlsruhe'
: [
'Mannheim'
,
'Karlsruhe'
],
'Augsburg'
: [
'Mannheim'
,
'Karlsruhe'
,
'Augsburg'
],
'Kassel'
: [
'Mannheim'
,
'Frankfurt'
,
'Kassel'
],
'Wurzburg'
: [
'Mannheim'
,
'Frankfurt'
,
'Wurzburg'
],
'Munchen'
: [
'Mannheim'
,
'Karlsruhe'
,
'Augsburg'
,
'Munchen'
],
'Erfurt'
: [
'Mannheim'
,
'Frankfurt'
,
'Wurzburg'
,
'Erfurt'
],
'Numberg'
: [
'Mannheim'
,
'Frankfurt'
,
'Wurzburg'
,
'Numberg'
],
'Stuttgart'
: [
'Mannheim'
,
'Frankfurt'
,
'Wurzburg'
,
'Numberg'
,
'Stuttgart'
]})
(
'Frankfurt'
, {
'Frankfurt'
: [
'Frankfurt'
],
'Mannheim'
: [
'Frankfurt'
,
'Mannheim'
],
'Kassel'
: [
'Frankfurt'
,
'Kassel'
],
'Wurzburg'
: [
'Frankfurt'
,
'Wurzburg'
],
'Karlsruhe'
: [
'Frankfurt'
,
'Mannheim'
,
'Karlsruhe'
],
'Augsburg'
: [
'Frankfurt'
,
'Mannheim'
,
'Karlsruhe'
,
'Augsburg'
],
'Munchen'
: [
'Frankfurt'
,
'Wurzburg'
,
'Numberg'
,
'Munchen'
],
'Erfurt'
: [
'Frankfurt'
,
'Wurzburg'
,
'Erfurt'
],
'Numberg'
: [
'Frankfurt'
,
'Wurzburg'
,
'Numberg'
],
'Stuttgart'
: [
'Frankfurt'
,
'Wurzburg'
,
'Numberg'
,
'Stuttgart'
]})
....
應(yīng)用
-
Dijkstra 算法的變體在 Google 地圖中廣泛使用，用于計(jì)算最短的路線。
-
想象身處在沃爾瑪商店，我們知道了各個(gè)過(guò)道之間的距離，我們希望為從過(guò)道 A 到過(guò)道 D 的客戶提供最短路徑。
-
如下圖所示，當(dāng)我們知道了領(lǐng)英中用戶的一級(jí)連接、二級(jí)連接時(shí)，如何得知幕后的信息呢？Dijkstra 算法可以幫到我們。
?
?
3、最小生成樹(shù)
?
假設(shè)我們?cè)谒芄こ坦净蚧ヂ?lián)網(wǎng)光纖公司工作，我們需要使用最少的電線（或者管道）連接圖表中的所有城市。我們?nèi)绾巫龅竭@一點(diǎn)？
?
無(wú)向圖和它的最小生成樹(shù)
?
代碼
#
nx.minimum_spanning_tree
(
g
)
returns
a
instance
of
type
graph
nx.draw_networkx
(
nx.minimum_spanning_tree
(
g
))
使用最小生成樹(shù)算法鋪設(shè)電線
?
應(yīng)用
-
最小生成樹(shù)在網(wǎng)絡(luò)設(shè)計(jì)中有著最直接的應(yīng)用，包括計(jì)算機(jī)網(wǎng)絡(luò)，電信網(wǎng)絡(luò)，運(yùn)輸網(wǎng)絡(luò)，供水網(wǎng)絡(luò)和電網(wǎng)。（最小生成樹(shù)最初就是為此發(fā)明的）
-
最小生成樹(shù)可用于求解旅行商問(wèn)題的近似解
-
聚類——首先構(gòu)造最小生成樹(shù)，然后使用類間距離和類內(nèi)距離來(lái)設(shè)定閾值，從而破壞最小生成樹(shù)中的某些連邊，最終完成聚類的目的
-
圖像分割——首先在圖形上構(gòu)建最小生成樹(shù)，其中像素是節(jié)點(diǎn)，像素之間的距離基于某種相似性度量（例如顏色，強(qiáng)度等），然后進(jìn)行圖的分割。
?
4、網(wǎng)頁(yè)排序（Pagerank）
?
Pagerank 是為谷歌提供長(zhǎng)期支持的頁(yè)面排序算法。根據(jù)輸入和輸出鏈接的數(shù)量和質(zhì)量，該算法對(duì)每個(gè)頁(yè)面進(jìn)行打分。
?
代碼
在本節(jié)中，我們將使用 Facebook 數(shù)據(jù)。首先，利用 Facebook 用戶之間的連接，我們使用以下方法創(chuàng)建圖：
# reading the dataset
fb
= nx.read_edgelist(
'../input/facebook-combined.txt'
, create_using = nx.Graph(), nodetype = int)
將圖進(jìn)行可視化：
pos = nx.spring_layout(fb)
import warnings
warnings.filterwarnings(
'ignore'
)
plt.style.
use
(
'fivethirtyeight'
)
plt.rcParams[
'figure.figsize'
] = (
20
,
15
)
plt.axis(
'off'
)
nx.draw_networkx(fb, pos, with_labels =
False
, node_size =
35
)
plt.show()
?
現(xiàn)在，我們想要找到具有高影響力的用戶。直觀上來(lái)講，Pagerank 會(huì)給擁有很多朋友的用戶提供更高的分?jǐn)?shù)，而這些用戶的朋友反過(guò)來(lái)會(huì)擁有很多朋友。
pageranks
=
nx.pagerank(fb)
print(pageranks)
------------------------------------------------------
:
0.006289602618466542,
1
:
0.00023590202311540972,
2
:
0.00020310565091694562,
3
:
0.00022552359869430617,
4
:
0.00023849264701222462,
........}
?
使用如下代碼，我們可以獲取排序后 PageRank 值，或者最具有影響力的用戶：
import
operator
sorted_pagerank = sorted(pagerank.items(), key=
operator
.itemgetter(
1
),
reverse
=
True
)
print
(sorted_pagerank)
------------------------------------------------------
[(
3437
,
0.007614586844749603
), (
107
,
0.006936420955866114
), (
1684
,
0.0063671621383068295
), (
0
,
0.006289602618466542
), (
1912
,
0.0038769716008844974
), (
348
,
0.0023480969727805783
), (
686
,
0.0022193592598000193
), (
3980
,
0.002170323579009993
), (
414
,
0.0018002990470702262
), (
698
,
0.0013171153138368807
), (
483
,
0.0012974283300616082
), (
3830
,
0.0011844348977671688
), (
376
,
0.0009014073664792464
), (
2047
,
0.000841029154597401
), (
56
,
0.0008039024292749443
), (
25
,
0.000800412660519768
), (
828
,
0.0007886905420662135
), (
322
,
0.0007867992190291396
),......]
?
將含有最具影響力用戶的子圖進(jìn)行可視化：
first_degree_connected_nodes = list(fb.neighbors(
3437
))
second_degree_connected_nodes = []
for
x
in
first_degree_connected_nodes:
second_degree_connected_nodes+=list(fb.neighbors(x))
second_degree_connected_nodes.
remove
(
3437
)
second_degree_connected_nodes = list(
set
(second_degree_connected_nodes))
subgraph_3437 = nx.subgraph(fb,first_degree_connected_nodes+second_degree_connected_nodes)
pos = nx.spring_layout(subgraph_3437)
node_color = [
'yellow'
if
v ==
3437
else
'red'
for
v
in
subgraph_3437]
node_size = [
1000
if
v ==
3437
else
35
for
v
in
subgraph_3437]
plt.style.use(
'fivethirtyeight'
)
plt.rcParams[
'figure.figsize'
] = (
20
,
15
)
plt.axis(
'off'
)
nx.draw_networkx(subgraph_3437, pos, with_labels = False, node_color=node_color,node_size=node_size )
plt.show()
黃色的節(jié)點(diǎn)代表最具影響力的用戶
?
應(yīng)用
Pagerank 可以估算任何網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性。
?
-
已被用于根據(jù)引文尋找最具影響力的論文
-
已被谷歌用于網(wǎng)頁(yè)排名
-
它可以對(duì)推文進(jìn)行排名，其中，用戶和推文作為網(wǎng)絡(luò)的節(jié)點(diǎn)。如果用戶 A 跟隨用戶 B，則在用戶之間創(chuàng)建連邊；如果用戶推文或者轉(zhuǎn)發(fā)推文，則在用戶和推文之間建立連邊。
-
用于推薦系統(tǒng)
?
5、中心性度量
一些中心性度量的指標(biāo)可以作為機(jī)器學(xué)習(xí)模型的特征，我們主要介紹其中的兩個(gè)指標(biāo)，其余的指標(biāo)可以參考這個(gè)鏈接。
?
https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html#current-flow-closeness
?
-
介數(shù)中心性： 擁有最多朋友的用戶很重要，而起到橋梁作用、將一個(gè)領(lǐng)域和另一個(gè)領(lǐng)域進(jìn)行連接的用戶也很重要，因?yàn)檫@樣可以讓更多的用戶看到不同領(lǐng)域的內(nèi)容。介數(shù)中心性衡量了特定節(jié)點(diǎn)出現(xiàn)在兩個(gè)其他節(jié)點(diǎn)之間最短路徑集的次數(shù)。
?
-
度中心性： 即節(jié)點(diǎn)的連接數(shù)。
?
代碼
使用下面的代碼可以計(jì)算子圖的介數(shù)中心性：
pos = nx.spring_layout(subgraph_3437)
betweennessCentrality = nx.betweenness_centrality(subgraph_3437,normalized=True, endpoints=True)
node_size = [v * 10000 for v in betweennessCentrality.values()]
plt.figure(figsize=(20,20))
nx.draw_networkx(subgraph_3437, pos=pos, with_labels=False,
node_size=node_size )
plt.axis('off')
?
如上圖所示，節(jié)點(diǎn)的尺寸大小和介數(shù)中心性的大小成正比。具有較高介數(shù)中心性的節(jié)點(diǎn)被認(rèn)為是信息的傳遞者，移除任意高介數(shù)中心性的節(jié)點(diǎn)將會(huì)撕裂網(wǎng)絡(luò)，將完整的圖打碎成幾個(gè)互不連通的子圖。
?
應(yīng)用
中心性度量的指標(biāo)可以作為機(jī)器學(xué)習(xí)模型的特征。
?
總結(jié)
在這篇文章中，我們介紹了了一些最有影響力的圖算法。隨著社交數(shù)據(jù)的出現(xiàn)，圖網(wǎng)絡(luò)分析可以幫助我們改進(jìn)模型和創(chuàng)造價(jià)值，甚至更多地了解這個(gè)世界。最后，貼上本文代碼地址。
?
代碼地址：
https://www.kaggle.com/mlwhiz/top-graph-algorithms
原文鏈接：
https://towardsdatascience.com/data-scientists-the-five-graph-algorithms-that-you-should-know-30f454fa5513
?
(*本文為AI科技大本營(yíng)編譯文章，
轉(zhuǎn)載
請(qǐng)聯(lián)系微信
?
1092722531
)
推薦閱讀
-
谷歌NIPS論文Transformer模型解讀：只要Attention就夠了
-
阿里云彈性計(jì)算負(fù)責(zé)人蔣林泉：億級(jí)場(chǎng)景驅(qū)動(dòng)的技術(shù)自研之路
-
開(kāi)源sk-dist，超參數(shù)調(diào)優(yōu)僅需3.4秒，sk-learn訓(xùn)練速度提升100倍
-
你在北邊的西二旗被水淹沒(méi)，我在東邊的八通線不知所措
-
為什么說(shuō)邊緣計(jì)算的發(fā)展比5G更重要？
-
C/C++ 最易受攻擊、70% 漏洞無(wú)效，揭秘全球開(kāi)源組件安全現(xiàn)狀
-
首批共享單車死于 2019
-
公鑰加密、加密Hash散列、Merkle樹(shù)……區(qū)塊鏈的密碼學(xué)你知多少？
你點(diǎn)的每個(gè)“在看”，我都認(rèn)真當(dāng)成了喜歡
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
