- 1 -
复杂网络健壮社团挖掘算法#
靳二辉，马小科，高琳**
（西安电子科技大学计算机学院，西安 710071）
摘要：提出了一种基于贝叶斯网络的健壮社团挖掘算法，通过对每个普通社团分别构建贝叶5
斯网络，并根据条件概率表和证据信息进行推理，得到贝叶斯网络中每个结点隶属于健壮社
团的后验概率以提取健壮社团。试验结果表明该方法对健壮社团发现的有效性。
关键词：复杂网络；社团发现；健壮社团；贝叶斯网络
中图分类号：
10
A novel algorithm for the robust community in complex
networks
Jin Erhui, Ma Xiaoke, Gao Lin
(School of Computer Science and Technology, Xidian University, Xi’an 710071)
Abstract: In this paper, a Bayesian network based algorithm for robust community in complex 15
network is developed. Through constructing Bayesian network for every common community,
according to conditional probabilities table and prior probabilities for reasoning, the posterior
probabilities of every node being in a robust community is obtained to extract robust communities.
Finally, we experimentally verify the effectiveness of two algorithms in networks.
Keywords: Complex network; Community discovering; Robust community; Bayesian network 20
0 引言
随着对网络性质的物理意义和数学特性的深入研究，网络的概念被越来越广泛地应用在
各个领域，例如万维网、流行病学、科学引文和合作、代谢系统以及生态系统等。人们发现
许多真实网络中都存在着一个重要的特性——社团（即模块）结构，即整个网络是由若干个25
社团构成的，这些社团具有内紧外松的结构特征。例如，WWW 可以看作是由大量网站社
团组成，根据网站所讨论的话题的性质将网络划分为不同的社团。类似地，在生物网络或者
电路网络中，也可根据各个节点不同的功能特性划分为不同的社团。各个社团内部节点间连
接相对紧密，各个社团之间的连接却相对稀疏。
然而，一般情况下找到网络中社团结构的精确解是一个 NP难题。当网络的规模较大时，30
解决上述问题有许多试探性算法，其中比较著名的两个算法包括：
（1）基于 Laplacian 图形特征值的谱平分法[1]：该算法是基于各个顶点之间连接的相
似度（也称相似性），把网络划分为各个社团。根据向网络中添加连边或者从网络中移除边，
该类算法又可分为凝聚方法和分裂方法；
（2）Kernighan-Lin算法[2]：它采用了一种贪婪算法，根据使社团内部及社团间的边最35
优化的原则对原始的网络进行分类。
本文将以如何检测出复杂网络中的健壮社团为主要内容展开详细论述，提出两种健壮社
团发现算法，分别为：基于贝叶斯网络的健壮社团发现算法和基于矩阵扰动理论的健壮社团
发现算法。通过实验仿真证明了两种算法用于解决该问题的有效性。
- 2 -
1 基于贝叶斯网络的健壮社团发现算法 40
在具体应用中，系统往往只关注于局部覆盖而非全局划分，如蛋白质相互作用网络，社
团对应于具备某种特定功能的蛋白质复合体，而研究者更关注于复合体中的核心部分，称之
为健壮社团。如何挖掘出有特定意义的健壮社团具有重要的现实意义与应用价值。
本节提出了一种基于贝叶斯网络推理的健壮社团发掘算法。利用贝叶斯网络的条件独立
性进行严格推理，将知识表示和知识推理相结合，把健壮社团检测问题映射为不确定知识的45
表达和推理问题。然后构造贝叶斯网络，根据节点的度信息确定贝叶斯网络相关参数（即各
个节点的条件概率），最后将内部联系紧密的节点确立为证据节点，在贝叶斯网络中进行信
度传播，得到各个节点的健壮性概率，从而推导出健壮社团。
贝叶斯网络
贝叶斯网络（简称 BN）是一种基于网络结构的有向无环图，亦称因果网络、概率因果50
网络、概率因果—影响模型、概率影响图，别名信度网络，应用于表达和分析不确定性事物，
利用不完全或部分确定的知识进行推理[3]。该方法是基于概率论、图论的一种不确定性知
识表达和推理模型。其早期的典型应用包括专家系统、故障诊断领域、软件帮助系统和医疗
诊断等，现 BN已成为人工智能领域中不确定知识表达和推理的一种流行方法。
算法 55
在给出具体算法之前，首先从贝叶斯网络观点出发来刻画健壮社团的标准，定义如下：
定义 给定一个集合S真包含于结点集合V ，由集合S所生成的导出子图 ( )G S 为健
壮社团，当且仅当由S所构成的贝叶斯网络在给定证据条件下，网络处于某种状态的联合概
率足够大，比如 1 2( 1, 1, , 1)kP s s s τ= = … = ≥ ，其中τ 为事先设定的阈值。
我们把健壮社团定义为网络中联系更为紧密的社团结构，基于这样的想法，可以先把整60
个网络按照一般的社团发现算法，将它划分为几个社团，然后再对每个社团分别找到其中健
壮的社团结构，在该算法中通过构建一个贝叶斯网络，然后在该网络上进行推理以完成健壮
社团的提取。
根据节点内度和外度的定义得知，对于节点 i而言， in outi i id d d= + ，并且 in outi id d− 越
大，节点 i就越有可能属于健壮社团。 65
贝叶斯网络中的节点即为该社团中所有的节点对象，每个节点的取值状态有两种：0和
1，0 表示该节点不属于健壮社团，取值为 1 表示该节点属于健壮社团。节点间的相互联系
通过网络的拓扑结构来确定（注意：该算法不需要从数据集中进行贝叶斯网络结构的学习）。
计算社团内每个节点的 in outi id d− 值。选择该值较大的节点作为贝叶斯网络的上层节点（即
根节点），其余的节点按照与已确定为上层节点的拓扑关系来构建贝叶斯网络，边的方向由70
上层节点指向其余节点。这里还有另外一种方法可以用于确定将哪些节点设为根节点，找出
该社团中的最大完全子图，这个子图可以看作是该社团中联系最紧密的部分，即核心部分，
将属于该最大完全子图的所有节点作为根节点进而构造贝叶斯网络。贝叶斯网络参数（即各
个节点的条件概率表）由该节点的度，内度和外度信息计算得出。
贝叶斯网络构建完成后，将那些最上层节点设为证据节点（取值为 1，即属于健壮社团），75
在整个贝叶斯网络中进行信度传播，完成推理，得到其余节点也属于该健壮社团的概率。
由上述算法思想可知，算法过程分为以下几个部分：首先用常规的算法找到复杂网络中
- 3 -
中国科技论文在线
的社团结构；然后为每个社团构建一个贝叶斯网络，推理后提取健壮社团。
普聚类用于初次划分
传统的聚类算法，如 K-means算法、EM算法等都是建立在凸球形的样本空间上，当样80
本空间不为凸时，算法会陷入局部最优。而谱聚类算法是一种新型的聚类算法，它能够在任
意形状的样本空间上聚类，且收敛于全局最优解。谱聚类算法最初用于计算机视觉、VLSI
设计等领域中解决图分割问题，近年来被研究应用到复杂网络聚类。
谱聚类算法首先建立在图论中的谱图理论基础上，本质是将聚类问题转化为图的最优划
分问题。该算法首先定义一个描述成对数据点相似度的亲和矩阵，并计算矩阵的特征值和特85
征向量，然后选择合适的特征向量聚类不同的数据点。在这里，选用图的拉普拉斯矩阵和它
的特征向量。
健壮社团提取
在上一节中，选用谱聚类算法，把一个网络划分为若干个子网络（即社团），这一节完
成为每个社团都构建一个贝叶斯网络，并给定一些证据节点，对网络进行推理，根据推理结90
果提取健壮社团。
构建一个贝叶斯网络的三个步骤如下：
（1）确定节点和取值状态。社团中的每个节点作为贝叶斯网络的节点。算法的目的是
为了确定这些点是不是属于某个健壮社团，因此每个节点的取值有两种：0 和 1。0 表示该
节点不属于健壮社团；1表示该节点属于健壮社团。 95
（2）确定节点之间的连边。按照以下步骤生成拓扑连边：
首先要对社团内的每个节点分别计算 id ， inid (内度)， outid (外度)。
接下来选出一些节点作为贝叶斯网络的根节点，选为根的这些节点必须是最有可能属于
健壮社团的节点。在这里有两种选择方法：在该社团内找出最大完全子图，完全子图是社团
内部联系最为紧密的部分，将属于完全子图的节点作为根节点是比较合理的；另外一种方法100
是对社团中的节点按照 in outi id d− 值进行从大到小排序，值大的节点属于健壮社团的可能性
更大，因此可以选择前k个作为贝叶斯网络的根节点。
然后按照社团中节点的拓扑序把其余节点加入贝叶斯网络中。依次从根节点出发，把与
之相连的节点加入贝叶斯网络中，边的方向由根节点指向下层节点。再从下层节点出发继续
构造，最终形成一个层次的贝叶斯网络。注意在构造过程行环检测，因为贝叶斯网络是一个105
有向无环图。
（3）最后为贝叶斯网络中的每个节点都设置条件概率表，对于根节点，只设置其先验
概率。例如，节点 i是根节点， iV 指节点 i的取值，如图 1所示，其概率如表 1所示。
图 1 朴素的贝叶斯网络 110
Fig. 1 simple bayesian network
115
- 4 -
中国科技论文在线
表 1 根节点的条件概率表
Tab. 1 the conditional probability distribution of the root
0iV =
out
i
i
d
d
1iV =
in
i
i
d
d
对于非根节点，其条件概率根据其内度和外度来计算得到，如表 2。
120
表 2 非根节点的条件概率表
Tab. 2 the conditional probability distribution of the non-roots
1 2VV
3V
00 01 10 11
0 3
3
2outd
d
+ 3
3
1outd
d
+ 3
3
1outd
d
+ 3
3
outd
d
1 3
3
2ind
d
− 3
3
1ind
d
− 3
3
1ind
d
− 3
3
ind
d
说明：当节点 1和 2都取值 0的情况下，即 1和 2都不属于健壮社团时，节点 3与社团
外的连边数就增加两条，同时与社团内的连边数就减少了两条，其不属于健壮社团的概率就125
增大。其余各式的意义与此类似。
以此类推，对于有 3个或 3个以上父节点的节点，其条件概率表的构造与上表类似，共
有 23列，与所有父节点的状态组合数相同，概率表达式中需要加上多少或者减去多少与父
节点状态组合中 0的取值个数有关。
按照以上步骤就能构建一个满足要求的贝叶斯网络。 130
贝叶斯网络构建完成之后，设置一些证据节点，即把那些最有可能属于健壮社团的节点
取值为 1。在构建贝叶斯网络的时候，所选择的根节点都符合这个条件，因此我们把贝叶斯
网络的根节点作为证据节点取值为 1。然后选择一种推理算法进行概率传播。
贝叶斯网络推理算法分为两大类：精确推理算法和近似推理算法。在给定证据条件下精
确推理算法能得到每个节点的准确后验概率，近似推理算法得到的是每个节点的近似后验概135
率，精确算法的计算复杂度比近似算法要高。在此选择精确推理算法中应用最为广泛，效果
较好的联合树方法进行推理。
根据健壮社团的定义和推理得到的每个节点后验概率，来确定节点是否属于健壮社团。
这里设置一个阈值α ，当某个节点取值为 1的后验概率大于α 时，把它加入到健壮社团中，
当然那些证据节点必然属于健壮社团。对于α 的设置，跟健壮社团的规模成正比，α 取 1140
时，只有那些证据节点属于健壮社团，当α 取 0 时，贝叶斯网络中的所有节点都属于健壮
社团。这里通过实验来得到合适的值。
2 实验结果
实验中所采用的数据有三个，分别是空手道俱乐部内部成员关系数据（34 个节点），
足球俱乐部成员关系数据（115个节点），另外一个是 128个节点的随机图，所采用的初始145
划分方法与第三章实验中所用的方法相同，即谱聚类算法。
- 5 -
中国科技论文在线
对原始网络进行初始划分，然后分别构建贝叶斯网络，设置证据结点利用 BNJ 软件对
所构建的每个贝叶斯网络进行推理，得到的健壮社团在原网络中表示如图 2所示。
图 2 基于贝叶斯网络的健壮社团 150
Fig. 2 robust communities discovered by our algorithm
其中，用圆角方块表示的节点属于健壮社团，用圆圈表示的节点不属于健壮社团。
对于该网络进行多次扰动，每次扰动都在原网络的基础上进行，对扰动后的网络用矩阵
摄动理论得到新的谱信息，再次划分，对多次划分的结果进行比较，得到的健壮社团如图 3155
所示，其中圆角方块表示的节点属于健壮社团，圆圈表示的节点不属于健壮社团。
图 3 基于矩阵扰动理论的健壮社团
Fig. 3 Robust communities discovered by the perturbation methods.
160
这个结果与用贝叶斯推理方法得到的健壮社团结果类似，只是对于某些在每次扰动后都
能正确分类的节点，也归为相应的健壮社团中。
通过与用贝叶斯推理方法得到的健壮社团结果比较发现，用扰动理论得到的健壮社团的
规模要略大于并且包括了用贝叶斯方法得到的健壮社团。这是由于贝叶斯网络只是通过对网
络拓扑结构进行分析，其规模的大小与概率阈值的设定有直接关系，如果将阈值设置小一些，165
其规模会增大。而基于扰动理论的算法是从健壮社团对网络的较小扰动表现出稳定性的角度
来分析，从而得到健壮社团。因此它的结果跟实验过程中所选择的社团检测算法，以及进行
扰动和结果比较的次数都有直接的关系。
本章提出的将矩阵扰动理论用于复杂网络的方法，不仅仅局限于发现健壮社团，还可以
用于检测谱聚类算法所发现社团的健壮性。利用一些评价方法，如基于结点对统计的方法、170
基于信息论的方法等，来检测用某种谱聚类算法得到的社团结构的健壮性，这里的健壮性指
的是对于网络扰动所表现出来的稳定性。
175
- 6 -
中国科技论文在线
[参考文献] (References)
[1] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal on
Matrix Analysis and Applications,1990, 11: 430-452.
[2] Kernighan B W, Lin S. An efficient heuristic procedure for portioning graphs[J]. Bell System Technical
Journal, 1970, 49: 291-307. 180
[3] Draper D. Localized partial evaluation of bayesian belief networks[D]. Seattle: University of Washington, 1995.
[4] Karrer B, Levina E, Newman M E J. Robustness of community structure in networks[J]. Physical Review E.
2008, 77(44): 1-9.
[5] Chen Suhuan. Matrix Perturbation Theory in Structural Dynamic Design(结构动态设计的矩阵摄动理论). 1st
Edition[M]. Beijing：Science Press. 2007. 185
