复杂网络中的邻域重叠社团结构探测

 引 言

通俗地讲，网络就是由线连接的成对点的集合，在专业领域中，这些点又被称为“顶点”或“节点”，线被称为“连边”。网络常用于许多学科的分支中描述复杂系统中元素的连接方式。这其中也包括 internet 网，其顶点代表分布在各地的计算机，边代表相连的数据 ；生物学中的食物链网的顶点则代表生态系统中的物种，边代表捕食者和被捕食者之间的交互 ；社会网络的顶点代表不同的人，边代表不同类型的社会关系，如朋友关系、合作关系、商业关系以及其他关系等。

在过去的几十年，人类掀起了网络研究的热潮，其中包括经验主义的学习，开发数学和计算工具以用来提出网络中的数据。研究网络的一个普遍方法是着重分析单个或某一小组顶点的属性，在研究过程中往往会提出一些“这个网络中最重要的顶点是哪个？”“哪些是强连接？”等诸如此类的问题。然而，这些方法用在大规模网络结构分析的时候，能够得到的有用信息却很少，为此，本文对大规模网络做一些深入的讨论。

1 网络模块化和社团结构的概念

研究网络中的大规模网络结构的最好方式是模块化和社团结构。本文中所讨论的社团结构是指网络中的顶点进行不同的分组，它们往往具有组内顶点连接比较稠密，而组间顶点连接比较稀疏的性质 [14]。举例来说，社会网络中的一群密友、万维网中互联的网页等，都可以看作一个社团。虽然社团结构不是研究网络结构的唯一方式 ( 其它的方式也可能会出现 )，但是，目前它在此领域中有一个很好的例证，因为通过研究网络的社团结构，能够让人们更加清晰地了解网络的结构和功能，所以，人们已开始关注于这方面的研究。

社团之所以会引起人们的兴趣，主要可以归结为几个原因。首先，寻找结构与功能的联系已经成为网络研究领域中的一个热点，而社团结构在本质上对应于网络系统中的功能模块。举例来说，在新陈代谢网中，如果把生物体内的全部有序化学变化看成一个网络，那么，社团就对应于特定的化学反应 ( 如将外界引入的营养物质转变为自身需要的结构元件。在社会网络中，社团与我们传统观念中的真实社团意思相近，比如一组有共同爱好的人、有共同居所、共同工作环境或一家人都可以看作一个社团。社团给人一种“物以类聚，人以群分”的感觉。

除了上述本质原因外，还有一个容易忽略的原因，那就是人们经常会问为什么社团结构那么重要呢？在许多网络中都发现了一个问题，那就是社团之间的属性有明显的不同。同时，我们也注意到，不同社团的结构特征是有变化的。这些属性对于了解系统具有重要意义，只有在社团结构层次上了解了系统的架构，这种意义才会更明显。

2 复杂网络中的社团结构

2.1 社团结构和分析算法

近年来，随着研究人员对复杂网络研究的越来越多，人们发现了一个网络的共同结构，也就是社团结构。目前人们所说的社团结构，还没有形成统一的概念，往往会被认为网络的顶点可以分组，而组内顶点连接比较稠密，组间顶点连接比较稀疏。事实上，研究人员为了搞清网络社团结构的特性，对寻找网络中社团结构的多种方法进行了实验和研究，以期找到有效的算法，尽量用比较少的信息去寻找尽量准确的社团结构。到目前为止，研究人员已经提出了若干社团发现算法，包括谱分析算法、最优目标函数算法、基于连边密度、介数、信息中心度、随机行走等，计算机领域中的图分割 (GraphPartitioning) 算法、社会科学中的层次聚类算法 (HierarchicalClustering 算法 )、W-H 算法和 GN 算法是最有代表性的方法。

但是在社团检测中，人们一般会遇到两个难题 ：一是不知道一个网络到底含有多少个社团 ；二是网络中的顶点可能属于不同的社团，即网络中存在重叠节点，这些节点也称为“骑墙”节点。重叠社团的检测对现实生活中的网络比较有效，所以，本文重点讨论重叠社团检测算法。

2.2 社团结构的定义形式

2.2.1 局部定义

社团是网络的一部分，它与网络的其它部分有少许的连接。在某种程度上，它们可以看作一个独立实体。所以，通常会单独评估一个社团。局部定义关注于子图的研究，包括它可能的邻近节点，但会忽略网络的其它部分。这里以在社会网络分析中常用的定义来分析，在局部社团中，主要有 4种相关的标准 [21]，全连、可达性、顶点度、内部和外部结合比较。所对应的社团往往是最大子图，最大子图不能再增加新的顶点或边。社团可以定义成其子图的成员，彼此之间都是“朋友”( 也就是说成员之间完全互联 )。在网络术语中，称它们为派系，也就是由彼此相连的顶点组成的子集。在社会网络分析中，一个派系就是一个最大子图。三角形是最常见的派系，同时也是真实网络中最常见的。在许多实际的应用中，人们期望社团的顶点有明显的分级，在一个中心点周围环绕着其它的顶点。但是，人们也注意到，一个顶点可能同时属于不同的派系，这也是 Palla 等人提出派系过滤算法的基础。比较子图内部和外部的凝聚情况很重要，这也是最近社团定义所做的一项工作，我们比较常见的是有关强社团和弱社团的定义。

所谓的强社团，是指社团任何一个顶点在社团内的度大于该顶点与其它社团内顶点相连的边的数量，可用公式表述如下：

而所谓的弱社团，是指社团内所有顶点在社团内的度之和大于该社团内的顶点与其它社团内顶点相连的边的数量，用公式描述为 ：

2.2.2 全局定义

许多算法要求对网络的整体结构有个了解，社团也可以以网络的整体去定义，这是因为在这种情况下，团簇作为网络的基本组成部分，在不严重影响系统功能的情况下，是不能被剖析的。过去的研究工作给我们提供了许多确定社团的全局标准，它们往往不是直接定义的。通常一些全局属性都是在算法中体现出来的。这一系列的定义都是基于一个网络不同于随机网络那么有社团结构。随机网络通常被认为没有社团结构，因为任何两个顶点都具有相同的毗邻可能性，所以它不会有一组优先连接的特别顶点。因此，人们可以做出一个“空模型”。所谓的空模型是指它能具有一些所给网络的结构特征，但其本身还是一个随机网络。最流行的空模型是由 Newman 和Girvan 提出的，它是由原始网络的随机版本组成的，是在人们期望的顶点的度与原始网络中顶点的度保持一致的约束条件下，让其边随机连接得到的。这也是后来的模块度概念的基础，事实上，模块度是社团结构的一个重要的检验标准。

2.2.3 模块度

网络中连接社团内部顶点间的边的比例与拥有相同社团结构但顶点间随机连接的网络中连接社团内部顶点间的边的比例的期望值的差值为 :

其中，Aij 代表连接矩阵中的元素 ；ki 表示顶点 i 的度 ；ci 是顶点 i 分配的社团；函数 δ(i, j) 的定义为当 i=j 时其值为 1，否则为 0；

2.2.4 归一化互信息

归一化互信息 (normalized mutual information，NMI) 是Lancichinetti 等人在 2009 年提出的，归一化互信息应用在重叠社团检测上面。对于图 C' 中的每个顶点 i，其社团隶属度可以描述成一个长度为 |C'| 的二元向量 (|C'| 为 C' 中团簇的数量 )。如果顶点 i 属于第 k 个团簇Clk，那么 (xi)k=1，否则为 0。第 k 个向量可以看做随机变量 Xk，其概率分布为 P(Xk=1)=nk/n，其中nk=| Clk | 为团簇Clk顶点的个数，n 是总的顶点数量。同理，也可以求出图 C″中第 l 个团簇的随机变量 Yl，那么，P(Xk,Yl)的联合概率密度就可定义为 ：

其 中，Xk 是 给 定 Yl 的 情 况 下 的 条 件 熵， 可 以 定 义 为H(Xk|Yl )=H(Xk,Yl )-H(Yl)。Xk 相对于整个向量 Y 的熵是基于 Xk与 Y 中团簇的最佳匹配，故可表示为 ：

X 相对于 Y 的归一条件熵可以表示为 ：

同理，也可以得到 H(Y|X)。最后得到的两个图 C′ 和 C″的归一化互信息为 :

NMI(X|Y)=1-[H(X|Y)+H(Y|X)]/2           (10)

一般情况下，扩展归一化互信息的值在 0~1 之间，等于 1时相当于最佳匹配。

3 分类聚集

对网络社团的研究可以追溯到上世纪 70 年代，那时就提出了一些检测社团的方法，特别是在计算机科学和社会学领域。计算机科学中的图分割问题，与社团检测相似，但又不完全相同，其工程上的应用受到了关注，与此同时，一些成熟的算法 ( 比如谱分割和 Kernigh-Lin 算法 ) 在其它领域的应用也取得了丰硕成果。然而，也许社会学家才是真正社团检测技术的始祖。

在社会网络中，早期出现并且目前还在广泛使用的探测社团结构的技术是分级聚类。事实上，分级聚类不是单一的技术，而是一类技术。它有一个中心思想 ：如果能导出网络中顶点的连接强度，然后把连接最强的进行分组，那么就可以把网络分成不同的社团。特定的分级聚类方法与使用的特定测量强度有关，这也是根据这些测试强度把顶点分成组的。最常见的测量是所谓的结构等价测量，这种测量关注于网络中两个顶点 i，j 共有的临近顶点的数量 nij。以社会网中的朋友关系举例来说，拥有许多共同朋友的两个人，往往比很少有共同朋友的两个人关系密切。此时共同朋友的数量就可以用作连接强度的测量。然而，为了不是仅仅使用生疏的 nij，提出了测量的标准形式，例如 jaccard 系数和余弦相似度。本文将顶点 i 与 j之间的顶点相似度定义为 ：

其中，ki 是顶点 i 的度 ( 也就是说它具有连接的数量 )，这种测量具有良好的属性，其值一般在 0 和 1 之间，0 的时候代表它们没有公共临近点，1 代表它们具有所有的临近顶点。

一旦定义了连接强度的测量值，那么就可以给顶点分组，并以分级的形式完成。首先把孤立的节点分成小的组，然后把这些小的组再分成较大的组，可以通过不同的方法让这些分组得以实现。常见的分组方式有单连接法、全连接法、平均连接法三种。目前，单连接聚类是使用最广的，因为它应用比较简单，但是事实上，平均连接聚类算法通常能得出更好的结果，而且使用也挺方便。

图 1 所示是使用平均连接聚类得到的结果，它是基于有名的空手道俱乐部网的余弦相似度。这个网络模型是观察了美国一所大学空手道俱乐部34名成员之间的社会关系得出的，这个网络之所以有趣，是因为在是否提高俱乐部会费上存在争 议，由于不能达成一致，俱乐部成员分成了两个派别，一个派系又建立了另外一个俱乐部。据说，通过了解网络中描述的友谊关系 ( 没有分裂之前的俱乐部 )，可以对两个派别的成员作出预测。

图1 小规模社会网络的平均聚类

图 1 以树状图的形式表示了分类聚集的输入结果，其代表了顶点分组成社团时的顺序，一般需从下往上读取。在底部有孤立的节点，它们被分组成对，我们沿着树状图往上移动，将被分成更大点的组，当到达最顶端，所有的顶点被分到一个组里面。在单幅图中，树状结构捕获了分类聚集的整个过程。在图中做一个水平切割，则可代表中间阶段的分组。

犹如我们看到的一样，本方法把顶点分到两个较大的组，每个组包含的顶点约占整个网络的一半，最后这两个组在树状结构的顶端合并成一个组。事实证明，算法划分成的两个组与实际的俱乐部分裂成的恰恰一致，图中用不同的颜色标出。因此，本例中这个方法非常有效。它有效地预测了社会未来的现象，通过定量数据的测量，推断了俱乐部的分割现象。分级聚类方法简单明了，易于使用，但是它不一定都能获得满意的结果。因为它有很多变量 ( 不同的测量长度和不同的连接规则 )，而且不同的变量会导致不同的结果，又不清楚哪个结果是最“恰当”的结果。本方法有聚集较强连接的顶点，但有遗漏较弱连接顶点的趋势。所以，其产生的分类不一定是完整的分类，而是几个稠密中心加上环绕其外围的孤立顶点。理想中，我们希望出现一个更可靠的方法。

4 优化方法

大约 10 年前，物理学和应用数学界的学者们对社团检测问题产生了极高的热情，并且提出了若干富有成效的方法。在第一次提议中，有些方法是基于对介数的测量。这些方法之一是计算通过网络边中的交通流得到的测量值，然后把那些交通量大的边移除。另外两种相关的方法是使用液体流算法和电流算法。另一大类方法是利用社团结构之间的连接以及网络的进程，如随机行走、Potts 模型等。另外，能形成鲜明对比的方法集则关注于局部社团的探测，其力图解决在没有发现网络中全部社团的情况下，对于给定的孤立点，如何确定它属于哪个社团的问题。优化算法中最常用的方式是基于模块度的优化。

图 2 所示是科学家合作网的模式图，也是使用模块度最大化的一个例子。模块度方法的优点之一是不需要事先知道网络中含有几个社团，而且自由的模块度可最大化，其社团的数量可以改变，并会告诉最优越的数量，并且能找到社团之间顶点的精确划分。

图 2 科学家合作网

基于适应度函数的局部优化算法应用越来越广，这里也对其进行详细介绍。本算法是为了解决分级重叠社团而提出的，算法运用了基于适应度函数的局部优化方法，社团结构由适应度直方图的顶点构成，社团的不同等级可以通过参数的调整来实现。实验证明，该算法在人工和现实网络中都取得了较好的效果。

在微观模块层次的网络架构一般非平凡，这一事实阻碍了解决方案。原因至少有二 ：一是整体等级模块，因为社团是镶套的，小社团组建成大社团，大社团再依次组建更大社团等。比如，一个大的公司组织，甚至复杂的生命也可以用网络等级描图出来。二是组织的等级形式有限，每个模块负责系统里不同的功能。社团结构的概念因为等级而变得更为丰富，它需要一种方法可以探测出所有组合等级，而不是单个。分类聚集是社会网络分析、生物和金融中一种众所周知的技术，从单个节点作为一个社团或所有的节点作为一个社团开始，根据顶点间相似度的拓扑方法，合并或者分裂一个团簇。这样，建立起等级树状结构，也叫做生物树图。通过这种方法，尽管能够产生一个分级分割，但对分割的质量无从判断。Newman 和 Girvan 两人提出了衡量分割好坏的算法，但是它只对单个分割有效。

本算法的假定条件是社团本来是局部结构，最多让模块中顶点邻近的点添加进来，这对大规模网络来说是合理的，那里的顶点与其对等点相关性不大。例如在万维网中，一个顶点对整个网络的影响不大，局部的网络只能传送局部的信息。与此类似，社会团体往往是一个小的区域生活的人们。

这里的社团是通过子图顶点的属性或适应度最大化形成的，本算法比较了几种适应度的方法，最后给出了比较优化的简单表达式 ：

这里的kinG和kou分别代表模块 G 中顶点的入度和出度 ；α 是一个正实数类型的参数，它用来控制社团的规模。入度在数值上等于模块内部连接数量的两倍，出度等于模块内成员与其它顶点连接的数量。本算法想从节点 A 开始确定一个子图，通过添加或删除子图中的一个节点达到减弱适应度函数 fG 的目的。我们称子图为节点 A 的自然社团，这就相当于给定一个参数 α 后，去寻找适应度函数的最大值。事实上，每个节点的最大值相当于整个网络，因为在给定参数 α 后，当koutG为零时，fG 会取得最大值。

当给定一个适应度函数 fG 后，节点 A 关于子图 G 的适应度函数 fGK 可由子图 G 在有节点 A 时的适应度减去子图 G在没有节点 A 时的适应度得出。其函数如下：

式中，G+{A}(G-{A}) 表示模块 G 在包含节点 A( 和不包含节点A) 的情况下获得的子图。

节点 A 的自然社团可以由下面的过程得出，设想有包括节点 A 的子图 G，最初 G 被视为节点 A，那么，算法的重叠部分包括下面的步骤 ：

(1) 找出 G 周围相邻但是不属于社团 G 内的点 ；(2) 将相邻点中拥有最大适应度的点添加到 G 中，并组成一个新的社团 G' ；

(3) 重新计算 G' 中每个顶点的适应度 ；(4) 如果一个顶点的适应度为负数，那么将它从G' 中删除，

并且组成新的社团 G″；

(5) 如果步骤 (4) 出现，那么回到步骤 (3)，其它情况下返回到步骤 (1)。

当步骤 (1) 中计算出来的适应度都为负数时，整个过程结束。这个过程相当于自适应函数的贪婪优化过程，因为每一步的改变，函数值看起来都会有较大的增长，别的方法也许能实现一样的功能。例如，除非团簇停止增长，否则我们会舍弃那些适应度为负数的节点，或者把那些能增加适应度的临近节点添加进去。这种做法往往能在短时间内获得较大的适应度。

5 k-means 算法的最佳聚类数确定

k-means 算法的基本流程由 Sönmez 在 2009 年提出。其算法描述如下：

首先，在 N 个对象中随机选取 k 个点并形成 k 个团簇，这 k 个点分别作为所在团簇的初始聚类中心。

其次，将余下的点 (N-K 中的点 ) 与其他团簇的中心的相似度进行比较，并得出相似度。

然后，把相似度比较强的点增加到团簇中，这样团簇就会越来越大。当一定的点都被划分到这个团簇的时候，团簇的中点会被重新定义。

接下来，再不断重复后面两个步骤，直到划分成一个完整的 K 派系团簇。

团簇种子是随机分配的，被认为是本算法的缺点，由于这种原因，可能不能获得最佳的划分。为了解决这个问题，k-means 算法中允许点在团簇内移动，因此，团簇内的相似度会随着其它团簇的增大而增大。另一方面，事物的转移会有利于社团的划分，但它并不能保证 100% 的成功，一种有效的检验团簇划分的方法是评估每个事物的轮廓值，也就是我们所说的 Silhouette 指标。轮廓值定义如下：

式中，a(i) 是第 i 个事物与同团簇内其它成员的平均相似度，b(i, k) 代表第 i 个事物与第 k 个团簇内成员之间的平均相似度。轮廓值 s(i) 的取值范围在 -1~+1 之间，+1 说明第 i 个物体被放在了很正确的团簇中，与其它团簇中不相似的事物之间的分割也比较好，0 表示第 i 个事物没有明显地划分到任何一个团簇中，-1 代表第 i 个事物划分到错误的团簇中。总之，平均的s(i) 为具有 N 个物体的 k 派系划分的评估提供了一个粗略的方法。s(i) 系数的值越大，说明划分越好。

本文通过 perason 相关系数分析了 273 种股票之间的相似度，并用 k-means 算法对其进行了分析。在确定最佳聚类时，其做法如下：

第一，选取聚类中心的探索范围，这里设定为[ 2, n],由于股票数为 273，所以其范围可以设为 [2,16] ；

第二，分别取 k 值在 [2,16] 之间的一个数作为聚类中心的个数，并转向 k-means 算法进行聚类 ；

第三，分别计算聚类中心为 k 时的聚类结果所对应的Silhouette 值 ；

第四，比较 k 在 [2,16] 之间分别得到的 Silhouette 值，其中最大的就是我们所要求的最佳聚类数。

至此，便可用实验得出如图 3 所示的数。本设计最后选取 k 为 11 进行聚类，其得出的结果和现实

世界中的真实情况接近。

6 结 语

随着新成果的日益出现和研究人员对方法和应用上的热情，网络结构的研究以及它与复杂系统功能和行为的联系，已经成为热门领域。本文讨论了已提出并已经得到较好应用的一些方法 ( 如块结构模型方法，现在正是研究的热门领域 )。

许多其它的算法由于篇幅的问题，本文没有一一讲解。开发的步伐也在加速，本领域为物理、生物、社会科学以及其它学科的研究提供了一些有用的资料，如果有人有能力搞清社团的大小结构，那么就相当于他为了解复杂系统开辟了一个窗口。

图 3 聚类计算出的 Silhouette

20210915_6141ea329c7b5__复杂网络中的邻域重叠社团结构探测