PageRank、最小生成树：ML开发者应该了解的五种图算法

知行编程网 2022-04-19 18:00 知行编程网 | 隐藏边栏 | 抢沙发 | 3 0

文章评分 0 次，平均分 0.0 ：

转自 | 机器之心

参与 | 高璇、杜伟

作为数据科学家，我们已经对 Pandas 或 SQL 等关系数据库非常熟悉了。我们习惯于将用户属性以列的形式展示在行中。但现实世界的数据果真如此吗？

在互联世界中，用户不能被视为独立的实体。他们之间存在一定的关系，我们有时希望在构建机器学习模型时考虑到这些关系。

在关系数据库中，我们无法在不同的行（用户）之间利用这种关系，但在图数据库中，这样做非常简单。

在这篇文章中，我们将讨论一些数据科学家应该了解的非常重要的图算法，以及如何使用 Python 实现它们。

连接组件

我们都知道聚类的工作机制，你可以将连接组件视为一种在关联/连接数据中查找集群/个体的硬聚类算法。

举个例子：假设你有连接世界上任何两个城市道路的数据。现在你需要找出世界上所有大洲以及它们所包含的城市。

你将如何实现这一目标呢？

我们采用的连接组件算法是基于广度优先搜索算法（Breadth First Search，BFS）/深度优先搜索算法（Depth First Search，DFS）的特殊情况。这里不再展开介绍工作原理，我们只看一下如何使用 Networkx 启动和运行此代码。

应用

从零售角度看：假设我们有很多客户使用大量账户。使用连接组件算法的一种方法是在这个数据集中找出不同的族。

我们可以根据相同的信用卡使用情况、相同地址、相同手机号码来建立某些客户 ID 之间的连接。一旦有这些连接，我们就可以运行连接组件算法为有连接的客户创建单个集群，然后为其分配一个家庭 ID。

然后，我们可以利用这些家庭 ID，根据家庭需求提供个性化推荐。我们还可以利用家庭 ID，通过创建基于家庭的分组功能来推进分类算法。

从金融角度：另一个用例是利用这些家庭 ID 抓捕诈骗犯。如果某个帐户有过被欺诈经历，那么关联帐户很容易再次受到欺诈。

实施的可能性仅仅受到自身想象力的限制。（想象力越丰富，算法的应用越广泛。）

代码

我们将使用 Python 中的 Networkx 模块来创建和分析图。下面以包含城市和城市间距离信息的图为例，实现我们的目的。

带有随机距离的图

首先创建一个带有城市名（边）和距离信息的列表，距离代表边的权重。

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;">edgelist = [[<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">85</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">80</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Erfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">186</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">167</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Augsburg'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">84</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Kassel'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">502</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Stuttgart'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">183</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">103</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">167</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Stuttgart'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">183</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Augsburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">84</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Augsburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">250</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Kassel'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">502</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Kassel'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">173</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">85</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">217</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Kassel'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">173</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">103</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Erfurt'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">186</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">217</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">80</span>], [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Augsburg'</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">250</span>],[<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"Mumbai"</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"Delhi"</span>,<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">400</span>],[<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"Delhi"</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"Kolkata"</span>,<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">500</span>],[<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"Kolkata"</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"Bangalore"</span>,<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">600</span>],[<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"TX"</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"NY"</span>,<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">1200</span>],[<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"ALB"</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"NY"</span>,<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">800</span>]]<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

让我们使用 Networkx 创建一个图:

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;">g = nx.Graph()<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">for</span> edge <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">in</span> edgelist:<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />    g.add_edge(edge[<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0</span>],edge[<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">1</span>], weight = edge[<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">2</span>])<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

现在我们想从这张图中找出不同的大洲及其城市，这可以使用连接组件算法来实现：

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;"><span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">for</span> i, x <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">in</span> enumerate(nx.connected_components(g)):<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />    print(<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">"cc"</span>+str(i)+<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">":"</span>,x)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />------------------------------------------------------------<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />cc0: {<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Kassel'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Erfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Stuttgart'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Augsburg'</span>}<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />cc1: {<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Kolkata'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Bangalore'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mumbai'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Delhi'</span>}<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />cc2: {<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'ALB'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'NY'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'TX'</span>}<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

如你所见，只需要利用顶点和边，我们就能够在数据中找到不同的组件。该算法可以在不同的数据上运行，从而满足上面提到的各种用例。

最短路径

继续使用上述示例，现在我们有德国城市及城市之间距离的图。如何找到从法兰克福（起始节点）到慕尼黑的最短距离？我们用来解决此问题的算法被称为 Dijkstra。用 Dijkstra 自己的话说：

从鹿特丹到格罗宁根旅行的最短路线是什么？这就是最短路径算法，我花了大约 20 分钟设计了它。一天早上，我和我的未婚妻在阿姆斯特丹购物，累了，我们便坐在咖啡馆的露台上喝咖啡，我只想着能否实现最短路径算法，然后我成功了。

正如我所说，这是一个二十分钟的发明。事实上，它发表于 1959 年，现在来看它的可读性也非常高。它之所以如此美妙，其中一个原因就是我没用笔纸就设计了它。后来我才知道，没有笔纸设计的有点之一是你不得不避免所有可避免的复杂问题。最终，令我惊讶的是，这个算法成为我的著名成果之一。

应用

Dijkstra 算法的变体在 Google 地图中有着广泛使用，用于寻找最短路线。

假设你有沃尔玛商店中各个过道位置和过道之间距离的数据。您希望为从 A 到 D 的顾客提供最短路径。

你已经看到 LinkedIn 显示一级连接和二级连接的方式。而这背后的机制是什么呢？

代码

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;">print(nx.shortest_path(g, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Stuttgart'</span>,<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>,weight=<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'weight'</span>))<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />print(nx.shortest_path_length(g, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Stuttgart'</span>,<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>,weight=<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'weight'</span>))<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />--------------------------------------------------------<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />[<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Stuttgart'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>]<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">503</span><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

你也可以找到所有对之间的最短路径：

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;"><span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">for</span> x <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">in</span> nx.all_pairs_dijkstra_path(g,weight=<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'weight'</span>):<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />    print(x)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />--------------------------------------------------------<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />(<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, {<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Augsburg'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Augsburg'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Kassel'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Kassel'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Augsburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Erfurt'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Erfurt'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Stuttgart'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Stuttgart'</span>]})<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />(<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, {<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Kassel'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Kassel'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Augsburg'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Mannheim'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Karlsruhe'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Augsburg'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Munchen'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Erfurt'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Erfurt'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>], <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Stuttgart'</span>: [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Frankfurt'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Wurzburg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Numberg'</span>, <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'Stuttgart'</span>]})<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />....</section>

最小生成树

Minimum Spanning Tree，MST

现在我们面临另一个问题。假设我们在水管铺设公司或电线公司工作。我们需要使用最少的电线/管道来连接图中所有城市。我们如何做到这一点？

左：无向图；右：对应 MST

应用

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

代码

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;"><span class="hljs-comment" style="box-sizing: border-box;font-size: inherit;color: rgb(128, 128, 128);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"># nx.minimum_spanning_tree(g) returns a instance of type graph</span><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />nx.draw_networkx(*nx.minimum_spanning_tree*(g))<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

左：无向图；右：对应 MST.

Pagerank

上图为谷歌提供长期支持的页面排序算法（page sorting algorithm）。它根据输入和输出链接的数量和质量为页面打分。

应用

Pagerank 可用于任何我们想要估算网络节点重要性的地方。

它已被用于查找影响力最高的论文；
它已被 Google 用于网页排名；
它可用于将推文-用户和推文排序为节点。如果用户 A 跟帖用户 B，则在用户之间创建链接；如果用户发推/转推，则在用户和推文之间建立链接；
推荐引擎。

代码

在本次练习中，我们将使用 Facebook 数据。我们在 facebook 用户之间有一个边/链接文件。首先通过以下方法创建 Facebook 图：

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;"><span class="hljs-comment" style="box-sizing: border-box;font-size: inherit;color: rgb(128, 128, 128);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"># reading the dataset</span><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />fb = nx.read_edgelist(<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'../input/facebook-combined.txt'</span>, create_using = nx.Graph(), nodetype = int)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

它是这样的：

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;">pos = nx.spring_layout(fb)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">import</span> warnings<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />warnings.filterwarnings(<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'ignore'</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />plt.style.use(<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'fivethirtyeight'</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />plt.rcParams[<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'figure.figsize'</span>] = (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">20</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">15</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />plt.axis(<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'off'</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />nx.draw_networkx(fb, pos, with_labels = <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">False</span>, node_size = <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">35</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />plt.show()<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

Facebook 用户图

现在我们想要找出具有高影响力的用户。直观地说，Pagerank 算法会给拥有很多朋友的用户打高分，而这些朋友又拥有很多 Facebook 朋友。

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;">pageranks = nx.pagerank(fb)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />print(pageranks)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />------------------------------------------------------<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />{<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0</span>: <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.006289602618466542</span>,<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /> <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">1</span>: <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.00023590202311540972</span>,<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /> <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">2</span>: <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.00020310565091694562</span>,<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /> <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">3</span>: <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.00022552359869430617</span>,<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /> <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">4</span>: <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.00023849264701222462</span>,<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />........}<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

利用以下代码可以得到排序的 PageRank 或最具影响力的用户：

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;"><span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">import</span> operator<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />sorted_pagerank = sorted(pagerank.items(), key=operator.itemgetter(<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">1</span>),reverse = <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">True</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />print(sorted_pagerank)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />------------------------------------------------------<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />[(<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">3437</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.007614586844749603</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">107</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.006936420955866114</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">1684</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0063671621383068295</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.006289602618466542</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">1912</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0038769716008844974</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">348</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0023480969727805783</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">686</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0022193592598000193</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">3980</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.002170323579009993</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">414</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0018002990470702262</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">698</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0013171153138368807</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">483</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0012974283300616082</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">3830</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0011844348977671688</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">376</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0009014073664792464</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">2047</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.000841029154597401</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">56</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0008039024292749443</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">25</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.000800412660519768</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">828</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0007886905420662135</span>), (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">322</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">0.0007867992190291396</span>),......]<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

以上 ID 即为最有影响力的用户。最具影响力用户的子图如下所示：

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;">first_degree_connected_nodes = list(fb.neighbors(<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">3437</span>))<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />second_degree_connected_nodes = []<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">for</span> x <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">in</span> first_degree_connected_nodes:<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />    second_degree_connected_nodes+=list(fb.neighbors(x))<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />second_degree_connected_nodes.remove(<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">3437</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />second_degree_connected_nodes = list(set(second_degree_connected_nodes))<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />subgraph_3437 = nx.subgraph(fb,first_degree_connected_nodes+second_degree_connected_nodes)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />pos = nx.spring_layout(subgraph_3437)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />node_color = [<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'yellow'</span> <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">if</span> v == <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">3437</span> <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">else</span> <span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'red'</span> <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">for</span> v <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">in</span> subgraph_3437]<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />node_size =  [<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">1000</span> <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">if</span> v == <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">3437</span> <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">else</span> <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">35</span> <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">for</span> v <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">in</span> subgraph_3437]<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />plt.style.use(<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'fivethirtyeight'</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />plt.rcParams[<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'figure.figsize'</span>] = (<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">20</span>, <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">15</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />plt.axis(<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'off'</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />nx.draw_networkx(subgraph_3437, pos, with_labels = <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">False</span>, node_color=node_color,node_size=node_size )<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />plt.show()<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

黄色为最具影响力用户

中心性度量

你可以将许多中心性度量用作机器学习模型的特征，这里只谈其中的两个。

其他度量链接：https://networkx.github.io/documentation/networkx-1.10/reference/algorithms.centrality.html#current-flow-closeness。

介数中心性：不仅拥有众多朋友的用户很重要，将一个地理位置连接到另一个位置的用户也很重要，因为这样可以让用户看到不同地点的内容。

介数中心性量化了一个特定节点在其他两个节点之间最短路径中出现的次数。

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

代码

以下是查找子图介数中心性的代码：

<section style="box-sizing: border-box;padding: 0.5em;font-size: 14px;color: rgb(169, 183, 198);line-height: 18px;border-radius: 0px;background: rgb(40, 43, 46);display: block;font-family: Consolas, Inconsolata, Courier, monospace;overflow-x: auto;letter-spacing: 0px;margin-left: 8px;margin-right: 8px;overflow-wrap: normal !important;word-break: normal !important;overflow-y: auto !important;">pos = nx.spring_layout(subgraph_3437)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />betweennessCentrality = nx.betweenness_centrality(subgraph_3437,normalized=<span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">True</span>, endpoints=<span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">True</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />node_size =  [v * <span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">10000</span> <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">for</span> v <span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">in</span> betweennessCentrality.values()]<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /><br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />plt.figure(figsize=(<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">20</span>,<span class="hljs-number" style="box-sizing: border-box;font-size: inherit;color: rgb(174, 135, 250);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">20</span>))<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />nx.draw_networkx(subgraph_3437, pos=pos, with_labels=<span class="hljs-keyword" style="box-sizing: border-box;font-size: inherit;color: rgb(248, 35, 117);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">False</span>,<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />                 node_size=node_size )<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  />plt.axis(<span class="hljs-string" style="box-sizing: border-box;font-size: inherit;color: rgb(238, 220, 112);line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;">'off'</span>)<br style="box-sizing: border-box;font-size: inherit;color: inherit;line-height: inherit;overflow-wrap: inherit !important;word-break: inherit !important;"  /></section>

你可以在此处查看按介数中心性值确定大小的节点。他们可以被认为是信息传递者。打破任何具有高介数中心性的节点将会将图形分成许多部分。

原文地址：

https://towardsdatascience.com/data-scientists-the-five-graph-algorithms-that-you-should-know-30f454fa5513

—完—

为您推荐

微软 VS Code 已原生支持 Jupyter 笔记本，再也不用打开网页调试运行了

作为 IT 行业的过来人，你有什么话想对后辈说的？

程序员真的是太太太太太太太太难了！

深度学习必懂的13种概率分布

【微软】AI-神经网络基本原理简明教程

本篇文章来源于: 深度学习这件小事

本文为原创文章，版权归知行编程网所有，欢迎分享本文，转载请保留出处！

知行编程网关注：1 粉丝：1

这个人很懒，什么都没写

内容反馈

你可能也喜欢

热评文章

发表评论

联系我们

标签云

推广返利