作为数据科学家，我们对Pandas或SQL或任何其他关系型数据库已经相当熟悉了。
我们习惯于在行中看到我们的用户，他们的属性是列。但现实世界真的是这样的吗？在一个互联的世界里，用户不能被视为独立的实体。他们之间有一定的关系，我们有时希望在建立机器学习模型时包括这种关系。
在关系型数据库中，我们不能使用不同行（用户）之间的这种关系，而在图数据库中，要做到这一点是相当简单的。
在这篇文章中，我将谈论一些你应该知道的最重要的图算法，以及如何使用Python实现它们。另外，这里有一个由UCSanDiego在Coursera上开设的大数据图分析课程，我强烈建议你学习图论的基础知识。
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],
地名英中对照：
['卡塞尔', '法兰克福', 173], ['法兰克福', '曼海姆', 85],['法兰克福', '伍兹堡', 217], ['法兰克福', '卡塞尔', 173], ['伍兹堡', '数格', 103], ['伍兹堡', '埃尔福', 186], ['伍兹堡', '法兰克福', 217], ['卡尔斯鲁厄', '曼海姆', 80], ['卡尔斯鲁厄', '奥格斯堡', 250], ["孟买", "德里",400], ["德里", "加尔各答",500], ["加尔各答", "班加罗尔",600], ["德州", "纽约",1200], "ALB", "纽约", 800] ]
让我们用Networkx创建一个图。
g = nx.Graph()
for edge in edgelist:
g.add_edge(edge[0],edge[1], weight = edge[2])
现在我们想从这个图中找出不同的大陆和它们的城市之间的连接。我们可以使用连接节点的算法来完成这个任务，具体方法如下。
从鹿特丹到格罗宁根的最短路径是什么，一般来说：从指定城市到指定城市。这是最短路径的算法，我在大约二十分钟内设计出来的。一天早上，我和我的年轻未婚妻在阿姆斯特丹购物，累了，我们坐在咖啡馆的露台上喝咖啡，我就在想，我是否能做到这一点，然后我就设计了最短路径的算法。
正如我所说，这是一个20分钟的发明。事实上，它是在59年发表的，三年之后。该出版物仍然可读，事实上，它是相当不错的。它如此漂亮的原因之一是我没有用纸笔设计它。我后来了解到，不用纸笔设计的一个好处是，你几乎被迫避免所有可避免的复杂问题。最终，这个算法让我大吃一惊，成为我成名的基石之一。
Dijkstra算法的变种被广泛用于谷歌地图中，以寻找最短的路线。
你在一家沃尔玛商店里。你有不同的走道和所有走道之间的距离。你想为顾客提供从A通道到D通道的
2 最短路径
你已经看到了LinkedIn是如何显示一级关系，二级关系的。幕后的情况是怎样的呢？
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 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'}
You can also find Shortest paths between all pairs using:
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', 'Kassel'], 'Wurzburg': ['法兰克福', '乌尔兹堡'], '卡尔斯鲁厄': ['法兰克福', '曼海姆', '卡尔斯鲁厄'], '奥格斯堡': ['法兰克福', '曼海姆', '卡尔斯鲁厄', '奥格斯堡'], '门兴': ['法兰克福', '乌尔兹堡', 'Numberg', 'Munchen'], 'Erfurt': ['法兰克福', '伍兹堡', '埃尔富特'], 'Numberg': ['法兰克福', '乌尔兹堡', 'Numberg'], '斯图加特': ['法兰克福', '乌尔兹堡', 'Numberg', '斯图加特']})
3. 最小生成树
现在我们有另一个问题。我们为一家水管铺设公司或互联网光纤公司工作。我们需要用最少的电线/管道连接我们所拥有的图中的所有城市。我们如何做到这一点呢？
最小生成树在网络设计中有着直接的应用，包括计算机网络、电信网络、交通网络、供水网络和电网（它们最早是被发明出来的）。
MST用于逼近旅行推销员问题
聚类--首先构建MST，然后利用群间距离和群内距离确定打破MST中某些边的阈值。
图像分割--它被用于图像分割，我们首先在一个图形上构建一个MST，其中像素是节点，像素之间的距离是基于一些相似性测量（颜色，强度等）。
nx.minimum_spanning_tree(g) 返回一个图形类型的实例
nx.draw_networkx(nx.minimum_spanning_tree(g))
正如你所看到的，上面是我们要铺设的线。
这是长期以来支持谷歌的页面排序算法。它根据传入和传出链接的数量和质量为页面分配分数。
Pagerank
可以用在我们想估计任何网络中节点重要性的任何地方。
它已被用于利用引文来寻找最有影响力的论文。
已被谷歌用来对网页进行排名
它可以被用来对推文进行排名--用户和推文是节点。如果用户A关注了用户B，就在用户之间建立链接；如果用户发了推文/转发了推文，就在用户和推文之间建立链接。
推荐引擎
在这个练习中，我们将使用Facebook的数据。我们有一个Facebook用户之间的边/链接的文件。我们首先使用创建FB图。
读取数据集
# reading the dataset
fb = nx.read_edgelist('../input/facebook-combined.txt', create_using = nx.Graph(), nodetype = int)
This is how it looks:
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()
现在，我们想找到那些有影响力的用户。直观地说，Pagerank算法会给一个有很多朋友的用户一个更高的分数，而这些朋友又有很多FB好友。
pageranks = nx.pagerank(fb)
print(pageranks)
{0: 0.006289602618466542,
1: 0.00023590202311540972,
2: 0.00020310565091694562,
3: 0.00022552359869430617,
4: 0.00023849264701222462,
........}
我们可以用以下方法获得排序的PageRank或最有影响力的用户。
import operator
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是最有影响力的用户。
我们可以看到最具影响力的用户的子图。
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. 中心度量
有很多中心度量，你可以将其作为机器学习模型的特征。我将谈论其中的两个。你可以在这里看一下其他的测量方法。
中心度（Betweenness Centrality）。不仅拥有最多朋友的用户是重要的，将一个地理区域连接到另一个地理区域的用户也很重要，因为这可以让用户看到不同地理区域的内容。间隙中心性量化了一个特定节点在两个其他节点之间的最短选择路径中的次数。
程度中心性。它只是一个节点的连接数。
中心度可以作为任何机器学习模型的一个特征。
下面是查找子图的Betweenness Centrality的代码。
pos = nx.spring_layout(subgraph_3437)
betweenness_Centrality = nx.betweenness_centrality(subgraph_3437,normalized=True, endpoints=True)
node_size = [v * 10000 for v in betweenness_Centrality.values()]
plt.figure(figsize=(20,20))
nx.draw_networkx(subgraph_3437, pos=pos, with_labels=False,
node_size=node_size )
plt.axis('off')
在这里，你可以看到节点的大小是由它们的间隙中心度值决定的。它们可以被认为是信息传递者。打破任何一个具有高介数中心性的节点，都会将图分成许多部分。
总结
在这篇文章中，我谈到了一些最有影响力的图算法，这些算法改变了我们的生活方式。
随着这么多社会数据的出现，网络分析可以对改善我们的模型和产生价值有很大帮助。
甚至对世界有更多的了解。
外面有很多图算法，但这些是我最喜欢的。如果你喜欢的话，可以更详细地研究一下这些算法。在这篇文章中，我只是想让大家对这个领域有必要的了解。
如果你觉得我离开了你最喜欢的算法，请在评论中告诉我。
如果你想阅读更多关于图算法的内容，这里有一个由UCSanDiego在Coursera上开设的图分析大数据课程，我强烈建议你学习图理论的基础知识。
谢谢你的阅读。我将在未来写更多适合初学者的文章。请在Medium上关注我，或者订阅我的博客，以便了解这些信息。像往常一样，我欢迎反馈和建设性的批评，你可以通过Twitter @mlwhiz联系我。
这里是Kaggle Kernel的全部代码。
