数据科学的 5 个图算法

图分析是未来！

我们已经非常熟悉 Pandas 或 SQL 或任何其他关系数据库，这导致：我们习惯于在数据表的“记录行”中查看分析我们的产品用户，并将他们的属性作为列。但现实世界真的是这样吗？
在互联世界中，用户不能被视为独立实体。它们彼此之间有一定的关系，我们有时希望在构建我们的机器学习模型时包含这种关系。
现在在关系数据库中，我们不能在不同的行（用户）之间使用这种关系，在图graph数据库中这样做是相当简单的。
 
在这篇文章中，将讨论一些你应该知道的最重要的图形算法，以及如何使用 Python 实现它们。

1. 连通分量

您可以用非常外行的术语将连接组件视为一种硬聚类算法，它可以在相关/连接的数据中找到聚类/孤岛。
举一个具体的例子：假设您有关于连接世界上任意两个城市的道路的数据。你需要找出世界上所有的大陆以及它们包含的城市。

如何实现这一目标？
我们用来执行此操作的连通分量算法基于BFS/DFS的特例。

应用
从零售的角度来看：比方说，我们有很多客户使用大量帐户。我们可以使用连通分量算法的一种方法是在我们的数据集中找出不同的家族。
我们可以根据相同的信用卡使用情况、相同的地址或相同的手机号码等假设 CustomerID 之间的边缘（道路）。一旦我们有了这些连接，我们就可以在相同的连接上运行连接的组件算法来创建单独的集群，我们然后可以分配一个家庭ID。
然后，我们可以使用这些家庭 ID，根据家庭需求提供个性化推荐。我们还可以使用这个家庭 ID 通过创建基于家庭的分组特征来为我们的分类算法提供动力。
从财务角度来看：另一个用例是使用这些家庭 ID 来捕获欺诈行为。如果一个帐户过去曾进行过欺诈，则关联帐户很可能也容易被欺诈。
可能性仅受您自己的想象力限制。

代码点击标题见原文

2.最短路径
如何找出从法兰克福（起始节点）到慕尼黑最短距离？
我们用于此问题的算法称为Dijkstra。

应用

• 谷歌地图广泛使用 Dijkstra 算法的变体来寻找最短路线。
• 你在沃尔玛商店。你有不同的过道和所有过道之间的距离。您希望为客户提供从通道 A 到通道 D 的最短路径。
• 您已经看到 LinkedIn 如何显示 1 度连接、2 度连接。

3.最小生成树
如果我们在水管铺设公司或互联网光纤公司工作。我们需要使用最少量的电线/管道连接图中的所有城市。我们如何做到这一点？

应用

• 最小生成树在网络设计中有直接应用，包括计算机网络、电信网络、交通网络、供水网络和电网（它们最初是为此而发明的）
• MST 用于逼近旅行商问题
• 聚类——首先构造 MST，然后使用簇间距离和簇内距离确定打破 MST 中某些边缘的阈值。
• 图像分割——它用于图像分割，我们首先在图上构建一个 MST，其中像素是节点，像素之间的距离基于一些相似性度量（颜色、强度等）

4.网页排名
这是长期以来为谷歌提供支持的页面排序算法。它根据传入和传出链接的数量和质量为页面分配分数。
应用
Pagerank 可以用于我们想要估计任何网络中节点重要性的任何地方。

• 它已被用于使用引文查找最有影响力的论文。
• 已被谷歌用于对页面进行排名
• 它可用于对推文进行排名——用户和推文作为节点。如果用户 A 关注用户 B，则在用户之间创建链接；如果用户发布/转推推文，则在用户和推文之间创建链接。
• 推荐引擎

代码点击标题

5.中心度量
有很多中心度量，你可以将其作为机器学习模型的特征。我将谈论其中的两个。你可以在这里看看其他的措施。

中心度（Betweenness Centrality）。不仅拥有最多朋友的用户是重要的，将一个地理区域连接到另一个地理区域的用户也很重要，因为这可以让用户看到来自不同地理区域的内容。间隙中心度量化了一个特定节点在两个其他节点之间的最短选择路径中的次数。

程度中心性：它只是一个节点的连接数。

应用

• 中心度量可以作为任何机器学习模型的一个特征。

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

结语
在这篇文章中，我谈到了一些最有影响力的图算法，这些算法改变了我们的生活方式。

随着这么多社会数据的出现，网络分析对改善我们的模型和产生价值有很大帮助。

甚至对世界有更多的了解。

外面有很多图算法，但这些是我最喜欢的。如果你喜欢的话，可以更详细地研究一下这些算法。在这篇文章中，我只是想让大家对这个领域有必要的了解。

如果你觉得我离开了你最喜欢的算法，请在评论中告诉我。

这里是 Kaggle Kernel 的全部代码。