小议图论，它对Facebook和Twitter的发展有何帮助？

点击上方关注，All in AI中国

作者：Keith McNulty

在这篇文章中，我将为可能在数据科学背景下使用图论的人解析一下原理。

18世纪初期，普鲁士柯尼斯堡的居民心中存在一个疑问：该镇有七座桥，河中有两个小岛，这七座桥将两个岛连接起来，人们如何才能不重复、不遗漏地一次走完七座桥，最后回到出发点？

为什么会有一个这样的问题，人们不得而知。或许过桥要支付通行费，希望能找到一种最合算的通过方式？或许人们对桥梁感到害怕或厌倦？无论如何，关键是解决这个问题的人可能对Facebook和Twitter的发展提供可能帮助。

解决这个问题的人是瑞士数学家莱昂哈德·欧拉(（Leonhard Euler）。欧拉对柯尼斯堡的过桥问题很感兴趣，认为只有真正的数学家才能解决这样的问题。他把这个简化为一种最简单的形式，而这个问题与桥梁无关。之所以简单的原因是：人们可以需要一笔绘制这个图形而不会重复。

其答案是不能，是否定的。不信你可以尝试一下！通过这种简单的洞察力诞生了一个数学分支，也是我们如今在智能手机或计算机上发送每个人的请求的核心：图论〔Graph Theory〕！

什么是图形？

大多数人对"图形"这个术语有着非常广泛的理解，代表了大多数数学图形描述。然而，正如人们所期望的那样，在数学中有一个非常清晰的定义，即图形是什么，我们围绕它们建立有用的规则和计算，使它们对试图解决的问题有用。

在最抽象的形式中，图形是两个集合。第一个集合称为顶点集。你可以将其视为一组不同的对象：例如可能是人，或者可能是下水道路口，那么还是以人为例，我们假设顶点集是John、Alex、Somesh、Lily。第二个集合称为边集。边集中的每个边由一对顶点定义，这表示存在连接这两个顶点的边。例如对位于边集中，则John与Lily相互连接。

与许多数学概念一样，绘制图形通常很有帮助，在采用图形的情况下，以图形方式表示它们是非常自然直观。这是一个包含社交网络元素的图表：

忽略箭头的方向，以及箭头所代表的连接类型，你可以为此图定义顶点集和边集吗？ （答案在文章的结尾）。

图形的类型

我采用最常见的定义对图形进行定义。通过在图形的一般定义中添加额外的规则或标准，可以生成专门的图形类。以下是一些更常见的例子，以及它们的实际应用实例：

有向图是边集也是一种具有方向性的图形。例如，边（Justin，Movies）与边（Movies，Justin）不同。第一个边集是使用前一个图像中的箭头描绘的边，第二个边集意味着关系是另一个方向（Movies喜欢Justin，Movies可能会产生情感，否则这是不可能的）。 在Twitter上的人们也可以被视为一种有向图，也就是说有些人在关注你，而你却没有关注他们。

多图是两个顶点之间具有有多条边的图，通常描绘不同的关系。可以想像一下飞机航线路线图，每条航线都是航班号。伦敦和纽约之间会有大量的边（路线）。

伪图（Pseudographs）是允许将顶点连接到自身的图形。毋庸置疑，在描绘人际关系的图表中通常不需要这样做。但是，例如你需要使用图表来描绘办公室中的咖啡订单以及谁正在购买适合他们的商品时，那么采用伪图将非常有用。

在完整的图形中，没有更多的边可以添加到边集上。所有顶点都相互连接。它可以是一个有用的数学工具来证明图形是完整的。

树图也非常明显，但它们在数学上被定义为连接且没有循环的图形。这意味着任何一对不同的顶点都可以通过一组边相互连接，但不可能通过一组边将顶点连接到自身。家谱通常就是这样的一个例子。例如皇室成员，那么可以看看西班牙国王查尔斯二世的家谱。

所有这些不同类型的图表都被定义了一个原因，它们有助于解决现实生活中的问题。在大多数情况下，我们可以坚持使用图形、有向图和多图来完成在数据科学中需要完成的大部分工作。

邻接矩阵

在这篇文章结束之前，我简单介绍一下邻接矩阵，这是一种开始测量网络相关现象的非常有用的方法。

想象一下，我们正在处理最简单的图形。如果有数百或数千个顶点，很难以图形方式描绘它，就需要一个更系统的方法来表示边。这种方法是创建一个矩阵数组，其顶点名称横跨水平轴和垂直轴。然后，可以使用1和0来表示这些顶点之间是否存在边。以下给出一个例子：

根据图形的类型，邻接矩阵可以具有不同的属性。在基本图中，邻接矩阵沿其对角线是对称的，但有向图可能没有这个属性。图形和有向图在对角线上有零点，但是伪图可能没有。

邻接矩阵是一个非常强大的工具。例如，你认为LinkedIn如何管理其成员之间庞大的关系网络？基本上，他们使用一个巨大的邻接矩阵，带有一些额外注释，以说明人们可以连接的不同方式。它还可以帮助确定个人或团体网络的重要属性。例如，如果将上面的邻接矩阵自身相乘，则会生成一个新矩阵，该矩阵会告诉你任意两个顶点之间长度为2的路径数。如果将其提高到幂n，它就会生成一个矩阵，告诉你任意两个顶点之间的长度为n的路径数。那么你是否能够了解为什么会这样？现在你看到的LinkedIn如何为你提供有关一阶、二阶和三阶连接的信息？

图论有很大的数学丰富性，其中大部分都对人类行为分析的专业人员的工作有直接和令人振奋的应用，并且越来越多地应用于其他学科，例如医学、流行病学、政治学、社会学。在这个领域还有许多有趣的开放性问题。例如，社交网络能否为紧急响应提供帮助？社交网络如何影响政治结果？可以用来追踪疾病的传播吗？

我将在一些文章中介绍这个实质性且令人兴奋的主题，如果你打算遵循这些主题，那么最好对本文所阐述的内容感到满意。下一次，我们将研究如何应用图论来衡量网络连接、网络增长以及某人在网络中的重要性。