数据科学家需要知道的5种图算法 _图算法

作者：Rahul Agarwal
编译：ronghuaiyang

导读

因为图分析是数据科学家的未来。

作为数据科学家，我们对pandas、SQL或任何其他关系数据库非常熟悉。
我们习惯于将用户的属性以列的形式显示在行中。但现实世界真的是这样吗？
在一个互联的世界里，用户不能被视为独立的实体。它们之间有一定的关系，我们在建立机器学习模型的时候，有时也会考虑这些关系。
现在，虽然在关系数据库中，我们不能在不同的行(用户)之间使用这样的关系，但是在图形数据库中，这样做非常简单。
在本文中，我将讨论一些你应该知道的最重要的图算法，以及如何使用Python实现它们。
1. 连通组件

文章插图
一个包含3个连通组件的图
我们都知道聚类是如何工作的。
你可以用外行人的术语来理解连通组件，它是一种硬聚类算法，可以在相关/连接的数据中找到聚类/岛屿
举个具体的例子：假设你有连接世界上任何两个城市的道路的数据。你需要找出世界上所有的大陆以及它们包含哪些城市
你将如何实现这一点？来想想吧。
我们使用的连通组件算法是基于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() 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'}正如你所看到的，我们能够在数据中找到不同的部分。只需要使用边和顶点。这个算法可以在不同的数据上运行，以满足我上面提到的任何用例。