选自Medium
作者：Rahul Agarwal
机器之心编译
参加：高璇、杜伟
作为数据科学家，咱们现已对 Pandas 或 SQL 等联络数据库十分了解了。咱们习惯于将用户特点以列的办法展现内行中。但实际国际的数据果真如此吗？
在互联国际中，用户不能被视为独立的实体。他们之间存在必定的联络，咱们有时期望在构建机器学习模型时考虑到这些联络。
在联络数据库中，咱们无法在不同的行（用户）之间运用这种联络，但在图数据库中，这样做十分简略。
在这篇文章中，咱们将评论一些数据科学家应该了解的十分重要的图算法，以及怎么运用 Python 完成它们。
衔接组件
咱们都知道聚类的作业机制，你能够将衔接组件视为一种在相关/衔接数据中查找集群/个别的硬聚类算法。
举个比如：假定你有衔接国际上任何两个城市道路的数据。现在你需求找出国际上一切大洲以及它们所包含的城市。
你将怎么完成这一方针呢？
咱们选用的衔接组件算法是依据广度优先搜索算法（Breadth First Search，BFS）/深度优先搜索算法（Depth First Search，DFS）的特殊情况。这儿不再打开介绍作业原理，咱们只看一下怎么运用 Networkx 发动和运转此代码。
运用
从零售视点看：假定咱们有许多客户运用许多账户。运用衔接组件算法的一种办法是在这个数据会集找出不同的族。
咱们能够依据相同的信用卡运用情况、相同地址、相同手机号码来树立某些客户 ID 之间的衔接。一旦有这些衔接，咱们就能够运转衔接组件算法为有衔接的客户创立单个集群，然后为其分配一个家庭 ID。
然后，咱们能够运用这些家庭 ID，依据家庭需求供给个性化引荐。咱们还能够运用家庭 ID，经过创立依据家庭的分组功能来推动分类算法。
从金融视点：另一个用例是运用这些家庭 ID 抓捕诈骗犯。假如某个帐户有过被诈骗阅历，那么相关帐户很简单再次遭到诈骗。
施行的可能性仅仅遭到本身想象力的约束。（想象力越丰厚，算法的运用越广泛。）
代码
咱们将运用 Python 中的 Networkx 模块来创立和剖析图。下面以包含城市和城市间间隔信息的图为例，完成咱们的意图。
带有随机间隔的图
首要创立一个带有城市名（边）和间隔信息的列表，间隔代表边的权重。
让咱们运用 Networkx 创立一个图:
现在咱们想从这张图中找出不同的大洲及其城市，这能够运用衔接组件算法来完成：
如你所见，只需求运用极点和边，咱们就能够在数据中找到不同的组件。该算法能够在不同的数据上运转，然后满意上面说到的各种用例。
最短途径
持续运用上述示例，现在咱们有德国城市及城市之间间隔的图。怎么找到从法兰克福（开始节点）到慕尼黑的最短间隔？咱们用来处理此问题的算法被称为 Dijkstra。用 Dijkstra 自己的话说：
从鹿特丹到格罗宁根游览的最短道路是什么？这便是最短途径算法，我花了大约 20 分钟规划了它。一天早上，我和我的未婚妻在阿姆斯特丹购物，累了，咱们便坐在咖啡馆的露台上喝咖啡，我只想着能否完成最短途径算法，然后我成功了。
正如我所说，这是一个二十分钟的创造。事实上，它发表于 1959 年，现在来看它的可读性也十分高。它之所以如此美好，其间一个原因便是我没用笔纸就规划了它。后来我才知道，没有笔纸规划的有点之一是你不得不防止一切可防止的复杂问题。终究，令我惊奇的是，这个算法成为我的闻名效果之一。
运用
Dijkstra 算法的变体在 Google 地图中有着广泛运用，用于寻觅最短道路。
假定你有沃尔玛商铺中各个过道方位和过道之间间隔的数据。您期望为从 A 到 D 的顾客供给最短途径。
你现已看到 linkedIn 显现一级衔接和二级衔接的办法。而这背面的机制是什么呢？
代码
你也能够找到一切对之间的最短途径：
最小生成树（Minimum Spanning Tree，MST）
现在咱们面对另一个问题。假定咱们在水管铺设公司或电线公司作业。咱们需求运用最少的电线/管道来衔接图中一切城市。咱们怎么做到这一点？
左：无向图；右：对应 MST
运用
最小生成树在网络规划中有直接运用，包含计算机网络、电信网络、交通网络、供水网络和电网（开始是为它们创造的）。
MST 用于近似游览商问题。
聚类：首要构建 MST，然后运用类间间隔和类内间隔确认阈值，用于打破 MST 中某些边。
图画切割：首要在图上构建 MST，其间像素是节点，像素之间的间隔依据某种相似性衡量（色彩、强度等）
代码
左：无向图；右：对应 MST.
Pagerank
上图为谷歌供给长时间支撑的页面排序算法（page sorting algorithm）。它依据输入和输出链接的数量和质量为页面打分。
运用
Pagerank 可用于任何咱们想要预算网络节点重要性的当地。
它已被用于查找影响力最高的论文；
它已被 Google 用于网页排名；
它可用于将推文-用户和推文排序为节点。假如用户 A 跟帖用户 B，则在用户之间创立链接；假如用户发推/转推，则在用户和推文之间树立链接；
引荐引擎。
代码
在本次操练中，咱们将运用 Facebook 数据。咱们在 facebook 用户之间有一个边/链接文件。首要经过以下办法创立 Facebook 图：
它是这样的：
Facebook 用户图
现在咱们想要找出具有高影响力的用户。直观地说，Pagerank 算法会给具有许多朋友的用户打高分，而这些朋友又具有许多 Facebook 朋友。
运用以下代码能够得到排序的 PageRank 或最具影响力的用户：
以上 ID 即为最有影响力的用户。最具影响力用户的子图如下所示：
黄色为最具影响力用户
中心性衡量
你能够将许多中心性衡量用作机器学习模型的特征，这儿只谈其间的两个。
其他衡量链接：https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html#current-flow-closeness。
介数中心性：不只具有很多朋友的用户很重要，将一个地理方位衔接到另一个方位的用户也很重要，由于这样能够让用户看到不同地址的内容。
介数中心性量化了一个特定节点在其他两个节点之间最短途径中呈现的次数。
点度中心性：它仅仅节点的衔接数。
代码
以下是查找子图介数中心性的代码：
你能够在此处检查按介数中心性值确认巨细的节点。他们能够被认为是信息传递者。打破任何具有高介数中心性的节点将会将图形分红许多部分。
原文地址：https://towardsdatascience.com/data-scientists-the-five-graph-algorithms-that-you-should-know-30f454fa5513
本文为机器之心编译，转载请联络本大众号取得授权。
------------------------------------------------
