完全子图的邻域重叠社团结构探测

引言

许多实际网络中都包含着一些群体，这些群体内部的节点连接紧密，我们称这些群体叫做团簇、社团或者模块。社团内连接紧密，社团外连接稀疏。对社团结构的探测是复杂网络研究的重要课题之一。在过去的几年中，出现了许多针对非邻域重叠网络的社团探测算法。而在现实世界里，许多网络的社团之间存在邻域重叠结构。所谓邻域，就是设A是拓扑空间(X,T)的一个子集，点x∈A。如果存在集合U，满足：

U是开集，即U∈T；

点x∈U；

U是A的子集。

则称点x是A的一个内点，并称A是点x的一个邻域。所谓重叠结构，就是存在一些特殊的节点，它们不仅仅属于一个社团，可能是多个社团共有的，我们称这些特殊的节点叫做重叠节点。如在进行科学家合作网中的生物网络的蛋白质网络研究中，就发现有重叠节点的存在。

1邻域重叠网络

图1所示是一个邻域重叠网络模型。其中黄色区域的社团与蓝色区域的社团之间有一个重叠节点，黄色区域的社团与绿色区域的社团之间有三个重叠节点。

图1邻域重叠网络模型

重叠节点在复杂网络中扮演着特殊的角色，大部分社团探测算法又无法探测它们。近年来，各种关于邻域重叠的社

团探测算法被广泛使用。Baumes等人提出了两个有效的算法，即用有效的启发式RaRe算法和IS算法来寻找局部最优簇。这些算法对研究随机网络和真实网络都是有效的。

Lancichmetti等人提出了基于适应函数优化的算法来探测重叠社团％FiedlerM.则提出了基于Laplacian矩阵特征向量的二分算法。KernighanB.W.等人提出Kernighan-Lin算法，通过优化社团内部和之间的边数来实现社团的划分。Newman提出了模块度最大化的快速贪婪算法。这些算法都适用于比较复杂的大型网络。但是，这些算法却无法处理大型网络中遍布众多完全子图(clique)的网络结构，如蛋白质网络中有众多蛋白质都是重叠节点。这些问题自从Palla等人提出clique过滤算法(CliquePercolationMethod，以下简称CPM算法)后，问题才得以解决。

CPM算法以完全子图为基础。从某种意义上，通过CPM算法可以把网络看作是许多小的完全子图集合。采用从大到小、迭代回归的算法来寻找完全子图。因为在CPM算法中定义clique是相对严格的，网络中往往存在不属于clique的节点，所以不能完整地找到社团结构。为了能够解决这一问题，学者又提出了使用k-means聚类、基于GN算法的COGNA算法，该算法不仅可以探测网络的社团结构，而且可以找到连接社团的“桥节点”，但是，对于孤立节点的处理，则稳定性不高。

本文提出了基于完全子图的社团探测算法。该算法在合并完全子图团簇时，计算每一对完全子图的连接度重叠节点个数，并设置合并完全子图的阈值，如果大于阈值，则合并。在处理不在团簇内的其他节点时，按照比例系数大小为划分规则进行划分，同时计算其模块度值，并验证邻域重叠划分算法的可行性。

2基于k-clique算法的重叠社团结构划分算法的改进

2.1模块度

Newman和Girvan提出了用模块度值来衡量社团划分质量的方案:

Q=/(es-a2(1)

=1

其中，e”表示所有社团，中的边权总和;表示社团i与其它社团的连边权度之和。如果是无权网络，则边权为1。尽管这种测量方法在社会网络中得到了广泛应用，但其仍然面临着一些问题。Q函数倾向于找到粗糙的而不是精细的网络簇结构，因而无法应用于邻域重叠网络社团质量的探测［22］。因此，ShenH.W.等人又提出了扩展的度量方法,具体如下：

Q。=2m//dcudcv(Auv-紧)°)

c!Puv其中，4表示节点u和节点v之间的权度；表示节点u与相邻节点之间的权度之和；表示整个网络的权度之和用来判断节点u是否在社团C之中，如果节点u在社团C内部，则毎=1,否则毎=0；表示所划分的所有社团。

在非邻域重叠网络中，一个节点仅属于一个社团。然而，在邻域重叠网络中，一个节点可能属于多个社团。因此，应该将毎替换为«„，表示重叠节点u所属社团的个数。重新定义模块度如下：

TOC \o "1-5" \h \z

6c!P

2.2算法的流程与改进

在网络中，i 代表一个节点，mi 代表节点 i 所属的社团个数。社团 α 和社团 β 共有 Sα,β 个节点，可以定义 Sα,β 为社团的重叠大小。社团 α 的连边数量可以称为社团度，用 da com 来表示。社团 α 内部的节点个数定义为社团 α 的大小，用Sa com来表示。本文对社团结构的定义以完全子图为网络核心，所划分出来的团簇是由许多 k-cliques 所组成的集合。

本文的算法由三部分组成：第一是寻找网络中所有的最大完全子图；第二是将完全子图合并成为更大的团簇；第三是处理不在团簇里面的剩余节点，实现社团结构的划分。其算法流程图如图2所示。

图2社团探测算法流程图

第一步：寻找网络中所有的最大完全子图。具体操作时可以把k-clique作为网络核心，将两两节点之间的相关系数矩阵设置阈值转化为0-1矩阵，然后输入0-1矩阵，这样就可以输出最大完全子图序列，其流程图如图3所示。

图3k-clique算法流程图

具体实现时,首先给出一个节点为i的图G,中有社团C如果社团C没有连接节点，则输出C。反之，则社团C并联连接节点V,记做{C}U{V)。把{C}U{V}的邻接节点的数目记为t({C}U{V})；然后，再给一个节点为j的简单图G,社团c最大时为max(C)„如果max(C)没有邻居节点，则输出max(C)o若max(C)与连接节点V不是一个团，则删除C与V之间的连接。

第二步：主要是合并完全子图。在找到网络中所有最大完全子图之后，将连接紧密的完全子图合并为更大的团簇。传统的合并方法是在完全子图之间没有重叠节点的情况下，计算完全子图之间的连接度，即完全子图之间的连接边数。设置用来判断团簇间连接是否紧密的阈值，如果连接度大于设定阈值，则合并。图4所示是两种双10-cliques连接情况的比较。其中图4(a)是没有重叠节点的双10-cliques。而本文的研究对象是具有高连接性的网络，在寻找出完全子图之后发现，大多数完全子图之间具有如图4(b)所示的重叠节点，仅仅考虑连接度是不可行的，所以，本文对其进行了改进。具体步骤是:首先计算每一对clique的连接度，用C表示；然后设置合并完全子图的阈值如果CmNCC,则将这对完全子图合并,然后重复上面的工作，直到C<CC。

第三步：处理不在团簇里面的剩余节点。将孤立节点划分在团簇中，并实现社团结构的划分。本文提出用连接度(Cg)的规则来划分。如果一个节点与多个团簇相连，则定义一个节点与团簇的边数为C(u,c),其中，"代表节点，c代表团簇。团簇的大小，也就是团簇中节点的个数为S，则可定义划分阈值为C(u,c)/S。这个阈值叫做连接度，用CG(ConnectingDegree)来表示。

(a)没有重叠节点的双10-cliques(b)高重叠性双10-cliques

图4两种双10-cliques连接情况比较

图5所示是处理不在团簇里面的剩余节点的示意图。图中,节点11是不在团簇里面的剩余节点。粉色圆圈节点和黄色三角形节点分别表示不同的团簇。按照连接度大小(CN)来划分,节点11与粉色圆圈节点的团簇的连接度CN=2/7,其中2表示节点11与粉色圆圈节点的团簇的边数为2,7表示粉色圆圈节点的团簇的大小，即节点个数为7用同样的方法可计算节点11与黄色三角形节点的团簇的连接度SF=1/3。显然1/3>2/7,那么节点11与粉色圆圈团簇的连接性就比黄色三角形团簇要强，所以将节点11划分在了黄色三角形节点的团簇当中。

图5不在团簇里面的剩余节点处理示意图

3空手道网络和科学家合作网的划分

将本文的算法应用到空手道网络当中的重叠社团结构划分示意图如图6所示。其中，粉色圆圈节点和绿色三角符号节点分别代表两个不同的社团，蓝色正方形节点代表两个社团的重叠节点。这个美国大学空手道网络当中包含34个节点、78条边。由于俱乐部主管和指导员发生了矛盾，所以俱乐部分裂为分别以主管和指导员为核心的两个团体。

设置阈值CC为0.5,实现邻域重叠社团划分。粉色圆形节点分别是1,2,3,4,5,6,7,8,11,12,13,14,17,18,20,22；绿色三角形节点分别是9,15,16,19,21,23,24,25,26,27,28,29,30,31,32,33,34；蓝色正方形为两社团之间的重叠节点10。计算其模块度值为0.3881。

若将算法应用到科学家合作网当中，图7所示是划分科学家合作网当中由393个节点组成的网络拓扑图，其中不同颜色圆圈节点代表不同的社团划分。按照该算法可划分出27个社团结构，有72个重叠节点，模块度值为0.8217,算法复杂度为0(1)。图7中展示了科学家合作网社团的划分情况。

图6空手道网络邻域重叠社团结构划分

图7科学家合作网邻域重叠社团结构划分示意图

图8所示是大小为8的社团和节点数为4的社团代表科学家的连接情况。从图8中可以看出，科学家VicsekT.是重叠节点。又因为他是这个团簇中连边最多的，其聚类系数也最大，因而起到了"桥梁"的作用。BrandesU.,CarlsonJ.和VespignaniA.:AlbaR.,MooreC.和TurskiP.分别组成了3-cliques关系。

本文对基于完全子图的社团探测算法进行改进。在合并完全子图团簇时，计算每一对完全子图的连接度重叠节点个数,设置合并完全子图的阈值，如果大于阈值，则合并。在处理不在团簇内的其他节点时，提出用比例系数大小来划分。本文同时将改进算法应用在空手道俱乐部网络和科学家合作网当中，从而验证了改进算法的可行性。

20210915_61417bc2641b6__完全子图的邻域重叠社团结构探测