大势所趋！数据科学家必知的5种图算法

全文共7889字，预计学习时长16分钟

在万物相连的世界里，用户并不是独立的个体，彼此之间都有某种联系。构建机器学习模型时，有时也会将这种联系放入模型中。

虽然关系数据库中无法在不同数行（用户）间使用这种关系，但在图数据库里，这样做非常简单。

本文将介绍一些数据科学家必知的重要的图算法，并阐释如何用Python来使用它们。

另外，强烈推荐先学习图理论基础。

圣地亚哥大学发布于Coursera上的大数据课程的图分析课：https://www.coursera.org/learn/big-data-graph-analytics?ranMID=40328&ranEAID=lVarvwc5BD0&ranSiteID=lVarvwc5BD0-uD3tAFL0mCUdzcfwDd6FTQ&siteID=lVarvwc5BD0-uD3tAFL0mCUdzcfwDd6FTQ&utm_content=2&utm_medium=partners&utm_source=linkshare&utm_campaign=lVarvwc5BD0

1. 连通分支

大家都知道聚类算法如何工作吧？

简单地说，就是将连通分支看作一种硬聚类算法，让它在相关/相连数据中找到聚类/岛。

举个具体的例子：假设有一份连接世界上任意两个城市的道路数据，而你需要借此找到世界上所有大洲和所包含的城市。

这要如何实现呢？开动脑筋吧。

此处使用的连通分支算法是基于BFS/DFS的特殊情况，此处不多赘述。以下会解释如何使用Networkx启动和运行代码。

应用

从零售的角度来看：假设有很多客户使用很多的帐户，连通分支算法可用于在数据集中找出不同的家庭。

根据相同的信用卡使用情况、相同的地址或相同的电话号码等，可以假定客户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()for edge in edgelist:g.add_edge(edge[0],edge[1], weight = edge[2])

现在要从这张图中找出不同的大陆及其城市。

可以这样/（按如下方式）使用连通分支算法：

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'}

如上所示，只需要使用联系和顶点就可以在数据中找到不同的组件。这个算法可以在不同的数据上运行来满足以上提到的任何案例。

2. 最短路径

上面已经得到德国城市以及各城市距离的图。

接着，要得出从法兰克福（起始节点）到慕尼黑的最短距离。

解决此问题的算法叫Dijkstra算法。用Dijkstra本人的话来说：

从鹿特丹到格罗宁根的捷径是什么？或者说，从任意一个城市到另一个城市。设计这个最短路径的算法，我只花了20分钟。一天早上，我和年轻的未婚妻在阿姆斯特丹购物。逛累了之后，我们坐在咖啡馆露台上喝了一杯咖啡，我就想能不能做到这一点，然后就设计了最短路径算法。就像之前所说，这是一个20分钟的发明。事实上，这本书在三年后的1959年出版，现在还能读到。它是本很好的书，因为我当时没有用铅笔和纸来设计。后来我发现，不用铅笔和纸设计的好处之一是，设计时必须要化繁为简。最终，我没想到，这个算法竟然成了我的成名作之一。

—— Edsger Dijkstra, 和Philip L. Frana的一段采访对话，美国计算机学会通讯，2001[3]

应用

· Dijkstra算法的演变版本被广泛应用于谷歌地图中用来寻找最短路径

· 假设你在沃尔玛工作，已知不同的通道和所有通道之间的距离，求出A通道到客户所在的D通道的最短路径。

· 领英上有很多一级联系和二级联系。这些联系背后都是如何运作的呢？

编码

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

还可以使用以下命令找到所有城市对之间的最短路径：

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

3. 最小生成树（MST）

现在另一个问题来了。假设你在水管铺设公司或互联网纤维公司工作，需要用最少的电线/管道连接图中的所有城市，这该怎么做呢?

应用

· MST被直接应用于网络设计中。其中包括电脑网络、电讯网络、运输网络、供水网络和电网（最初设计目的）

· MST还用于解决旅行商问题

· 聚类——首先建构MST，接着用簇间距离和簇内距离确定阈值，从而打破MST中的一些联系

· 图像分割——首先在图中构建MST，其中像素是节点，像素之间的距离基于一些相似性度量（颜色、强度等）

编码

# nx.minimum_spanning_tree(g) returns a instance of type graphnx.draw_networkx(nx.minimum_spanning_tree(g))

如图所示，上图中便是要铺设的电线。

4. 网页排名

上图便是谷歌一直以来的网页排名算法。它根据输入和输出连接的数量和质量为页面分配分数。

应用

网页排名可用于需要估算网络节点重要性的任何地方。

· 用于使用引文找到最有影响力的论文

· 在谷歌中用于网页排名

· 还可用来给推特排序——以用户和推特作为节点。如果用户A关注了用户B，就创建用户间的连接。如果用户发送或转发一条推特，则创建用户和推特之间的连接。

· 推荐引擎

编码

此练习会使用Facebook数据。这里有facebook用户之间的连接/链接文件。首先这样创建Facebook图形：

# reading the datasetfb = nx.read_edgelist('../input/facebook-combined.txt', create_using = nx.Graph(), nodetype = int)

它是这样运作的：

pos = nx.spring_layout(fb)import warningswarnings.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上的朋友。

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

这样可以得到排序后的网页排名算法或最有影响力的用户：

import operatorsorted_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),......]

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

这里可以看到最具影响力用户的子图：

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

5.中心性度量

中心度量有很多可以用来做机器学习模型的特性。以下将介绍其中的两种。这里可以看到一些其他的测量方法：https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html

中介中心性：朋友最多的用户很重要，连接两个地理位置的用户也很重要，因为它让用户可以看到来自不同地理位置的内容。中介中心性量化了一个特定节点在其他两个节点之间最短路径中出现的次数。

度中心性：即节点的连接数。

应用

中心性度量可以用作任何机器学习模型的特性。

编码

以下代码用于查找子图的中介中心性。

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