导读

由于图剖析是数据科学家的未来。

作为数据科学家，咱们对pandas、SQL或任何其他联系数据库十分了解。

咱们习惯于将用户的特点以列的方式显现内行中。但实际国际真的是这样吗?

在一个互联的国际里，用户不能被视为独立的实体。它们之间有必定的联系，咱们在树立机器学习模型的时分，有时也会考虑这些联系。

现在，虽然在联系数据库中，咱们不能在不同的行(用户)之间运用这样的联系，可是在图形数据库中，这样做十分简略。

在本文中，我将评论一些你应该知道的最重要的图算法，以及怎么运用Python完成它们。

1. 连通组件

咱们都知道聚类是怎么作业的。

你能够用外行人的术语来了解连通组件，它是一种硬聚类算法，能够在相关/衔接的数据中找到聚类/岛屿

举个详细的比如：假定你有衔接国际上任何两个城市的路途的数据。你需求找出国际上一切的大陆以及它们包含哪些城市

你将怎么完成这一点?来想想吧。

咱们运用的连通组件算法是依据BFS/DFS的特殊情况。我不会在这里过多地评论它是怎么作业的，可是咱们将看到怎么运用Networkx编写和运转代码。

运用

从零售的视点来看：假定咱们有许多客户，运用许多账户。运用连通组件算法的一种办法是在数据会集找出显着不同的宗族。

咱们能够依据相同的信用卡运用情况、相同的地址或相同的移动电话号码等设定客户ID之间的边(路)。一旦咱们有了这些衔接，咱们就能够运转连通组件算法来创立独自的簇，然后咱们能够为其分配一个宗族ID。

然后，咱们能够运用这些宗族ID依据宗族需求供给个性化的引荐。咱们还能够运用这个宗族ID，经过创立依据宗族的分组特征来支撑咱们的分类算法。

从财政的视点来看：另一个用例是运用这些宗族ID捕获诈骗。假如一个账户在曩昔有过诈骗行为，相关账户很可能也简单进行诈骗。

可能性只受你自己想象力的约束。

代码

咱们将运用Python中的Networkx模块来创立和剖析图。

让咱们从一个示例图开端，咱们运用它来完成咱们的意图。包含城市和城市之间的间隔信息。

咱们首要创立一个带有间隔的边的列表，咱们把间隔作为边的权重：

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构建图：

g=nx.Graph()
foredgeinedgelist:
g.add_edge(edge[0],edge[1],weight=edge[2])

现在咱们想从这张图中找出不同的大陆及其包含的城市。

咱们现在能够运用连通组件算法做到这一点：

fori,xinenumerate(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'}

正如你所看到的，咱们能够在数据中找到不同的部分。只需求运用边和极点。这个算法能够在不同的数据上运转，以满意我上面说到的任何用例。

2. 最短途径

持续上面的比如，咱们得到了一个德国城市的图以及它们之间的间隔。

你想知道怎么从法兰克福(开始节点)到慕尼黑的最短间隔。

咱们用来处理这个问题的算法叫做Dijkstra。用Dijkstra自己的话来说：

• 从鹿特丹到[格罗宁根的最短道路是什么?一般来说，最短途径的算法是这样的，我花了大约20分钟来规划它。一天早上我在阿姆斯特丹和我的年青的未婚妻购物，累了，咱们坐在咖啡馆天台喝一杯咖啡，我就在想我能不能想出这个最短途径算法，然后我就想出来了。正如我所说，这是一个20分钟的创造。事实上，它是在1959年出书的。三年后，还能够读到，事实上，它适当不错。它如此美丽的原因之一是我不必铅笔和纸来规划它。后来我了解到，不必铅笔和纸规划的优点之一是，你简直不得不防止一切能够防止的复杂性。终究，令我大为惊奇的是，这个算法成了我成名的柱石之一。

- Edsger Dijkstra，在对Philip L. Frana的采访中

运用

Dijkstra算法的变体广泛运用于谷歌地图中，用于寻觅最短途径。

你在沃尔玛，你有不同的通道和一切通道之间的间隔。你想要供给从A通道到D通道到客户的最短途径。

你能够看到LinkedIn怎么显现1级和2级的衔接。暗地发生了什么?

代码

print(nx.shortest_path(g,'Stuttgart','Frankfurt',weight='weight'))
print(nx.shortest_path_length(g,'Stuttgart','Frankfurt',weight='weight'))
--------------------------------------------------------
['Stuttgart','Numberg','Wurzburg','Frankfurt']
503

你也能够找到一切的地址对之间的最短途径：

forxinnx.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']})
....

3. 最小生成树

现在咱们有另一个问题。咱们为一家水管铺设公司或互联网光纤公司作业。咱们需求用最少的电线/管道衔接图中一切的城市，咱们该怎么做?

运用

• 最小生成树直接运用于网络规划，包含计算机网络、电信网络、交通网络、供水网络和电网(它们开始是为这些网络而创造的)
• MST用于迫临旅行商问题
• 聚类 — 首要结构MST，然后运用簇间间隔和簇内间隔确认MST中某些边际的切割阈值。
• 图画切割 — 用于图画切割，咱们首要在一个图上结构一个MST，其间像素是节点，像素之间的间隔依据一些相似性衡量(色彩、强度等)。

代码

#nx.minimum_spanning_tree(g)returnsainstanceoftypegraph
nx.draw_networkx(nx.minimum_spanning_tree(g))

咱们的图的最小生成树

能够看到，上面便是咱们需求铺设的电线。

4. Pagerank

这便是长期以来支撑谷歌的页面排序算法。它依据输入和输出链接的数量和质量为页面分配一个分数。

运用

Pagerank能够用于任何咱们想要估量任何网络中节点重要性的当地。

• 它被用来寻觅最具影响力的论文运用引文。
• 被谷歌用来摆放页面
• 它能够用来把tweets-用户和以及tweets-tweets当成节点进行排序。假如用户A重视了用户B，那么创立用户之间的链接，假如用户tweet/retwets一条tweet，则创立用户和tweet之间的链接。
• 引荐引擎

代码

在这个操练中，咱们将运用Facebook数据。咱们有一个facebook用户之间的边/链接文件。咱们首要创立FB图，运用：

#readingthedataset
fb=nx.read_edgelist('../input/facebook-combined.txt',create_using=nx.Graph(),nodetype=int)

它是这样的：

pos=nx.spring_layout(fb)
importwarnings
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()

FaceBook用户图

现在咱们想要找到具有高影响力的用户。

直观地说，Pagerank算法会给有许多朋友的用户打高分，而这些朋友又有许多facebook上的朋友。

pageranks=nx.pagerank(fb)
print(pageranks)
------------------------------------------------------
{0:0.006289602618466542,
1:0.00023590202311540972,
2:0.00020310565091694562,
3:0.00022552359869430617,
4:0.00023849264701222462,
........}

咱们能够用PageRank得到最有影响力的用户排序：

importoperator
sorted_pagerank=sorted(pageranks.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),......]

以上id适用于最有影响力的用户。

咱们能够看到最具影响力用户的子图：

g=nx.Graph()
foredgeinedgelist:
g.add_edge(edge[0],edge[1],weight=edge[2])
0