Question

在数学上，图是一组与边相连的节点的集合。边、节点和图的类型有许多种，它们具有不同的连接和解析方式。因此，在开始剖析图之前，我们先给出一些重要的定义。

图的元素、类型和密度

如果图中至少有一条边是有向的（例如，一条节点A到节点B的有向边对应的是从A到B的连接，而不是从B到A的连接），则图本身就是有方向的，这样的图称为有向图。如果图中有平行边（即节点A可以通过多条边连接到节点B），则该图称为多图。从节点A到节点A的边称为循环。不存在循环和平行边的图称为简单图。

图的边可以分配权重。权重通常（但不是必须）是0和1之间的数字（包括0和1）。权重越大意味着节点之间的连接越强。具有加权边的图称为加权图。

边的权重是边的一种属性。边可能还有其他属性，包括数字、布尔和字符串类型的变量。图的节点同样可以具有类似的属性。

图的节点的度被定义为连接（入射）到节点的边数。对于有向图来说，度进一步区分为入度（以节点为终点的边数）和出度（以节点为起点的边数）。

图的密度d（0≤d≤1）表示图与完全图的接近程度。所谓完全图是指包含所有可能边的图。例如，一个具有e条边和n个节点的有向图，其密度为：

相应的无向图的密度为：

图的结构

图以及图所引出的网络都是多样化、多面性、令人兴奋的对象。了解必要的术语有助于更好地掌握相关知识。

节点间的连通性是基于图上的游走过程得出的概念。一个游走过程是由一组边的序列构成的，其中一条边的端点是另一条边的起点。乘坐公共汽车从“家”节点到“地铁站A”节点，然后乘坐地铁从“地铁站A”到“地铁站B”，再从“地铁站B”步行到“我们的办公室”节点，我们就完成了一个图上的游走（虽然只有一部分是真正靠步行完成的）。我们称不与自身相交的游走（也就是说，游走过程中除了第一个和最后一个节点外，节点出现的次数都小于两次）为路径。一个闭合的路径称为循环。当我们结束艰难的一天回到家时，一天的游走就构成了循环2。

2注意不能原路返回，否则不构成路径，更不是循环。——译者注

和测量现实生活中两个对象之间的距离一样，我们可以测量任意两个节点之间的距离，这个距离是连接节点的所有路径中最小的边数（有时也称为“跳”）。加权图没有距离的定义，不过有时你可以假装图没有加权，仍然用边数来计算距离。对于有向图而言，从A到B的距离并不总是等于从B到A的距离。实际上，也许我们只能从A到B，而不能从B到A！从出生到死亡的生命历程就是一个伤感的却再清楚不过的例子。

图中任意两个节点之间的最大距离称为图的直径（D）。与圆不同，图没有面积。

连通分量或分量是图中这样一组节点的集合：集合中的每个节点都具有到达集合中的所有其他节点的路径。对于有向图来说，连通分量又分为强连通分量（有实际的连接路径）和弱连通分量（将边转换为无向边后才存在连接路径）。

如果图有多个分量，则最大的分量称为巨型连通分量（GCC）。GCC的规模通常很大，此时为了避免遇到连接不存在的问题，最好使用GCC，而不是整个图。

有时图的两个部分是互连的，但其连接是如此地微妙，以至于移除单条边后图就被分开了。这样的边被称为桥。

团是这样一组节点的集合：每个节点都与集合中的其他节点直接相连。D'Artagnan和三个火枪手就组成了一个团，包括任何奉行“人人为我，我为人人”原则的组合也一样。我们称图中最大的团为最大团。如果一个团不能通过向其中添加另一个节点而扩大，则称这个团为极大团。最大团一定是极大团，但反过来未必成立。完全图本身就是一个最大团。

星形图是这样一组节点的集合：集合中存在一个节点与其他所有节点相连接，但是其他节点之间不存在连接。星形图通常存在于分级的多层次系统中（例如公司、军事机构和互联网）。

直接与节点A相连接的一组节点称为节点A的邻域（A的G(A)）。邻域是雪球效应的关键部分。雪球效应是一种数据获取技术，通过随机选择的种子节点跟踪到其邻居节点，进一步到达邻居的邻居节点（二度邻域），并不断重复该过程。

节点A的局部集聚系数（或简称为集聚系数）是A的邻域所具有的边数CC(A)（不包括直接与A相连的边）除以最大可能的边数。换句话说，集聚系数是去除节点A后A的邻域的密度。星形图中任意节点的集聚系数为0。完全图中任意节点的集聚系数为1。可以把CC(A)看作G(A)的星形相似度或是其完全性的度量。

网络社区是这样一组节点的集合：集合中节点互连的边数远大于穿过社区边界的边数。模块度（m∈[-1/2, 1]）是社区结构质量的度量。它被定义为社区内节点的互连边数比例与随机情况下的边数比例之差。高模块化（m≈1）表征了一个拥有密集和清晰可见社区的网络。识别这样的社区可能是网络数据分析最重要的结果（具体内容参考第39单元）。

中心性

中心性是网络中节点重要性的度量。有多种类型的中心性度量，它们从不同方面对节点的重要性进行了衡量。为了方便起见，中心性通常被缩放到0（对应不重要的外围节点）和1（对应重要的中心节点）之间。

度中心性

节点A的度中心性是A的邻居节点个数，也就是A的度或G(A)的大小。可以通过除以A的最大可能邻居数n-1，将其缩放到合适的范围。

接近中心性

节点A的接近中心性是其他所有节点到节点A的平均最短路径长度L_BA的倒数：

中介中间性

节点A的中介中心性是指网络中所有两个节点之间的最短路径中，经过A点的路径数量与最短路径总数量之比。

特征矢量中心性

节点A的特征矢量中心性被定义为A的所有邻居节点的特征矢量中心性的加权和，这是一个递归定义：

最后两个中心性度量的计算代价非常大，而且对于大型网络可能并不实用。