D0I:10.13374/1.issnl00103.2009.0L.013 第31卷第1期 北京科技大学学报 Vol.31 No.1 2009年1月 Journal of University of Science and Technology Beijing Jan.2009 基于最小社团链接度增量的社团结构挖掘算法 王立敏2)高学东)武森) 1)北京科技大学经济管理学院，北京1000832)北京科技大学中国教育经济信息网管理中心，北京100083 摘要针对复杂网络社团结构挖掘算法复杂度高的问题，定义了一个衡量局部社团结构的指标，提出了一种基于最小社团 链接度增量的社团结构挖掘算法·本算法的时间复杂度为O(k),其中d为网络的平均节点度数，k为搜索的节点数.为了 验证本算法的性能和计算的准确性，把本算法与一种经典的挖掘局部社团结构方法一Clauset算法，进行了比较.实验结果 表明：本算法抽取的社团结构与Clauset算法相比基本一致，但在性能上有了显著提高 关键词复杂网络；链接度：社团结构：挖掘算法 分类号TP393 Mining algorithm of community structure based on the minimal increment of link degree of a community WANG Li-min2.GAO Xue-dong),WU Sen) 1)School of Economics and Management.University of Science and Technology Beijing Beijing 100083.China 2)Management Center of China Education Economy Information Net,University of Science and Technology Beijing Beijing 100083.China ABSTRACI A measure of local community structure was defined,and an mining algorithm of local community structure based on the minimal increment of link degree of a community was presented for resolving the time complexity problems of finding local com- munity structure in complex networks.The algorithm ran in time 0(kd)for general graphs,where d is the mean degree and k is the number of vertices to be explored.In order to determine its performance and calculation precision,the algorithm was compared with the classical local community identification approach,Clauset algorithm.Experimental results show that mining results of the al- gorithm are as effective as those of Clauset algorithm on the whole,and the algorithm is much faster than Clauset algorithm. KEY WORDS complex network:link degree:community structure:mining algorithm 复杂网络的结构描述已经成为物理学家关注的 近几年，研究者提出许多用于挖掘网络社团结 一个热点，目前，研究者除了研究网络的统计特征 构的技术，其中比较著名的是由Newman和Girvan 和动力学特征外，越来越重视社团的结构]，试图 提出基于边介数的算法[2，刃，此算法已经被用于各 揭示看上去错综复杂的网络是怎样由相对独立又相 种网络中，但算法运行的时间复杂度为O(nm), 互交错的社团组成的.这对于理解网络的结构和功 其中n和m分别为网络中的节点数和边数，此后， 能特性有着深刻的理论意义和现实意义， 一些学者们又提出了许多不同的算法[山，但是这 2002年，首次由Girvan和Newman提出了复 些算法的前提条件是需要知道所研究网络的整体结 杂网络的社团结构概念[]，社团就是网络中的节点 构，对于许多规模比较大而且具有动态特征的网络 集合·社团内节点之间具有比较紧密的链接，而社 来说，如万维网，要完全了解网络的整体结构不太可 团之间节点的链接相对比较松散，目前，尽管社团 能，因此这个要求就使得许多算法的应用受到了限 还没有一个统一的、量化的定义，但这种定义已经被 制，更重要的是，在实际应用中，有时并不需要了解 广大学者所接受 整个网络的社团结构，只是需要知道某个局部的社 收稿日期：2008-01-08 基金项目：教育部新世纪优秀人才支持计划资助项目(N。·NCET一05O097) 作者简介：王立敏(l971一)，女，博士研究生，E-mail:wanglimin@cee~ustb.ed:cn:高学东(1964一)，男，教授，博士生导师
基于最小社团链接度增量的社团结构挖掘算法 王立敏12） 高学东1） 武 森1） 1） 北京科技大学经济管理学院北京100083 2） 北京科技大学中国教育经济信息网管理中心北京100083 摘 要 针对复杂网络社团结构挖掘算法复杂度高的问题定义了一个衡量局部社团结构的指标提出了一种基于最小社团 链接度增量的社团结构挖掘算法．本算法的时间复杂度为 O（ kd）其中 d 为网络的平均节点度数k 为搜索的节点数．为了 验证本算法的性能和计算的准确性把本算法与一种经典的挖掘局部社团结构方法———Clauset 算法进行了比较．实验结果 表明：本算法抽取的社团结构与 Clauset 算法相比基本一致但在性能上有了显著提高． 关键词 复杂网络；链接度；社团结构；挖掘算法 分类号 TP393 Mining algorithm of community structure based on the minimal increment of link degree of a community W A NG L-i min 12）GA O Xue-dong 1）W U Sen 1） 1） School of Economics and ManagementUniversity of Science and Technology BeijingBeijing100083China 2） Management Center of China Education Economy Information NetUniversity of Science and Technology BeijingBeijing100083China ABSTRACT A measure of local community structure was definedand an mining algorithm of local community structure based on the minimal increment of link degree of a community was presented for resolving the time complexity problems of finding local community structure in complex networks．T he algorithm ran in time O（ kd） for general graphswhere d is the mean degree and k is the number of vertices to be explored．In order to determine its performance and calculation precisionthe algorithm was compared with the classical local community identification approachClauset algorithm．Experimental results show that mining results of the algorithm are as effective as those of Clauset algorithm on the wholeand the algorithm is much faster than Clauset algorithm． KEY WORDS complex network；link degree；community structure；mining algorithm 收稿日期：2008-01-08 基金项目：教育部新世纪优秀人才支持计划资助项目（No．NCET—05—0097） 作者简介：王立敏（1971—）女博士研究生E-mail：wanglimin＠cee．ustb．edu．cn；高学东（1964—）男教授博士生导师 复杂网络的结构描述已经成为物理学家关注的 一个热点．目前研究者除了研究网络的统计特征 和动力学特征外越来越重视社团的结构［1—5］试图 揭示看上去错综复杂的网络是怎样由相对独立又相 互交错的社团组成的．这对于理解网络的结构和功 能特性有着深刻的理论意义和现实意义． 2002年首次由 Girvan 和 Newman 提出了复 杂网络的社团结构概念［6］社团就是网络中的节点 集合．社团内节点之间具有比较紧密的链接而社 团之间节点的链接相对比较松散．目前尽管社团 还没有一个统一的、量化的定义但这种定义已经被 广大学者所接受． 近几年研究者提出许多用于挖掘网络社团结 构的技术其中比较著名的是由 Newman 和 Girvan 提出基于边介数的算法［27］．此算法已经被用于各 种网络中但算法运行的时间复杂度为 O（ n 2m） 其中 n 和 m 分别为网络中的节点数和边数．此后 一些学者们又提出了许多不同的算法［8—11］但是这 些算法的前提条件是需要知道所研究网络的整体结 构．对于许多规模比较大而且具有动态特征的网络 来说如万维网要完全了解网络的整体结构不太可 能．因此这个要求就使得许多算法的应用受到了限 制．更重要的是在实际应用中有时并不需要了解 整个网络的社团结构只是需要知道某个局部的社 第31卷 第1期 2009年 1月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．31No．1 Jan．2009 DOI:10．13374／j．issn1001－053x．2009．01．013
第1期 王立敏等：基于最小社团链接度增量的社团结构挖掘算法 .113 团结构，在这种情况下，不希望消耗过多的时间来 团的链接数达到局部最小时，社团的结构才较为显 寻找全部的社团结构，例如：对于犯罪网络，公安部 著，根据该思想，本文提出了局部社团外部链接度 门最想了解的是犯罪集团的头目所接触的犯罪嫌疑 的概念 人（即犯罪头目所属的局部社团结构），以便能更好 地一网打尽整个犯罪团伙；对于疾病传播网络，疾病 控制中心可能想在最短时间内掌握发病的病源所接 触的人群，以便及时切断疾病传播的途径，使疾病的 传播得到有效控制.因此，就产生了在不完全了解 网络整体结构的情况下，对网络的局部社团结构进 行研究的必要性 2005年Bagrow12]提出了一种利用局部信息来 探测整个网络社团结构的方法，称为BB算法，它是 通过由一个起始节点逐层向外扩展的方法，在每一 步执行过程中，判断整个一层总暴露度是否满足当 图1一个小型的具有社团结构性质的网络（网络中的节点自然 地分成三个不同的簇，簇内的节点之间的链接较多，簇之间节点 前设定的阈值，如果满足就把整个一层的节点加入 的链接较少) 到社团中，否则停止，事实上，在复杂网络中社团的 Fig.I Small network with community structure (in this case there 同一层邻居节点有可能属于不同的社团.因此，BB are three communities,denoted by the dashed circles,which have 算法存在的最大缺陷在于它是把社团的整个一层邻 dense internal links but between which there are only a lower density 居节点全部加入到社团或者全部排除在社团之外， of external links) 之后，Clauset[3]提出“局部模块性”的概念，并根据 为了直观地描述社团内部节点之间以及社团内 此概念给出了一个挖掘局部社团结构的算法， 部与外部之间的链接关系，用C表示社团内节点的 Clauset算法是围绕着初始节点每次选择局部模块 集合，v:和表示网络中任意两个节点，C表示社 增量最大的节点加入到社团中的方法，由于局部模 团外节点的集合，则社团C的链接矩阵C表示如 块增量的计算与社团的内外部的链接状况有关，因 下： 此算法的时间复杂度为O(kd),d为节点的平均 1, 节点度，k为将要寻找的社团成员数目， C0, :和相连，且∈C或u,∈C() 其他 本文提出了一个衡量局部社团结构数量特征的 然后，定义局部社团外部链接度L为： 指标一局部社团外部链接度，并给出了一种简单、 L=∑c(ij) (2) 快速挖掘网络局部社团结构的算法 1,:∈C,且∈C:或∈C,且∈C 1相关概念 其中，(i,)一0，其他 社团结构的识别是通过最大化全局社团结构的 局部社团外部链接度是一个从局部角度出发来 数量化指标来实现的，例如，Girvan和Newman提 看社团结构的显著性程度的指标，局部社团外部链 出的衡量网络划分质量的标准一模块性Q,Q的 接度越小，说明局部社团结构越显著 计算需要使用整个网络的链接数m·对于在网络的 通常，局部社团外部链接度L的变化与起始节 整体结构不太清楚的情况下，模块性Q是根本无法 点的度数有关，大致存在两种情况：一种是选择了节 计算的，因此，如果不了解网络结构的全局知识，那 点度数较小的起始节点，从起始节点开始L值较 么社团结构的度量标准就不能使用这种具有全局特 小，随着社团成员的增加而逐步增大，增大到一定值 性的指标.针对这种情况，本文提出了一种衡量局 后又开始减小到局部最小值：另一种是选择了节点 部社团结构数量特征的指标一局部社团外部链接 度数较大的起始节点，从起始节点开始L值就比较 度 大，随着社团成员的增加而逐步减小，一直到达局部 根据Girvan和Newman对社团结构的定义可 最小值，当L达到局部最小值时，局部社团的结构 知，社团内部节点之间的链接程度明显高于社团之 相对比较显著，因此通过L的变化就可以很容易 间的链接程度，如图1所示.当一个社团与其他社 地找到社团的边界
团结构．在这种情况下不希望消耗过多的时间来 寻找全部的社团结构．例如：对于犯罪网络公安部 门最想了解的是犯罪集团的头目所接触的犯罪嫌疑 人（即犯罪头目所属的局部社团结构）以便能更好 地一网打尽整个犯罪团伙；对于疾病传播网络疾病 控制中心可能想在最短时间内掌握发病的病源所接 触的人群以便及时切断疾病传播的途径使疾病的 传播得到有效控制．因此就产生了在不完全了解 网络整体结构的情况下对网络的局部社团结构进 行研究的必要性． 2005年 Bagrow ［12］提出了一种利用局部信息来 探测整个网络社团结构的方法称为 BB 算法．它是 通过由一个起始节点逐层向外扩展的方法．在每一 步执行过程中判断整个一层总暴露度是否满足当 前设定的阈值．如果满足就把整个一层的节点加入 到社团中否则停止．事实上在复杂网络中社团的 同一层邻居节点有可能属于不同的社团．因此BB 算法存在的最大缺陷在于它是把社团的整个一层邻 居节点全部加入到社团或者全部排除在社团之外． 之后Clauset ［13］提出“局部模块性”的概念并根据 此概念给出了一个挖掘局部社团结构的算法． Clauset 算法是围绕着初始节点每次选择局部模块 增量最大的节点加入到社团中的方法．由于局部模 块增量的计算与社团的内外部的链接状况有关因 此算法的时间复杂度为 O（ k 2d）d 为节点的平均 节点度k 为将要寻找的社团成员数目． 本文提出了一个衡量局部社团结构数量特征的 指标———局部社团外部链接度并给出了一种简单、 快速挖掘网络局部社团结构的算法． 1 相关概念 社团结构的识别是通过最大化全局社团结构的 数量化指标来实现的．例如Girvan 和 Newman 提 出的衡量网络划分质量的标准———模块性 QQ 的 计算需要使用整个网络的链接数 m．对于在网络的 整体结构不太清楚的情况下模块性 Q 是根本无法 计算的．因此如果不了解网络结构的全局知识那 么社团结构的度量标准就不能使用这种具有全局特 性的指标．针对这种情况本文提出了一种衡量局 部社团结构数量特征的指标———局部社团外部链接 度． 根据 Girvan 和 Newman 对社团结构的定义可 知社团内部节点之间的链接程度明显高于社团之 间的链接程度如图1所示．当一个社团与其他社 团的链接数达到局部最小时社团的结构才较为显 著．根据该思想本文提出了局部社团外部链接度 的概念． 图1 一个小型的具有社团结构性质的网络（网络中的节点自然 地分成三个不同的簇簇内的节点之间的链接较多簇之间节点 的链接较少） Fig．1 Small network with community structure （in this case there are three communitiesdenoted by the dashed circleswhich have dense internal links but between which there are only a lower density of external links） 为了直观地描述社团内部节点之间以及社团内 部与外部之间的链接关系用 C 表示社团内节点的 集合vi 和 vj 表示网络中任意两个节点C 表示社 团外节点的集合则社团 C 的链接矩阵 Cij 表示如 下： Cij＝ 1 vi 和 vj 相连且 vi∈C 或 vj∈C 0 其他 （1） 然后定义局部社团外部链接度 L 为： L＝ ∑ij Cijδ（ ij） （2） 其中δ（ ij）＝ 1 vi∈C且 vj∈C；或 vj∈C且 vi∈C 0 其他 局部社团外部链接度是一个从局部角度出发来 看社团结构的显著性程度的指标．局部社团外部链 接度越小说明局部社团结构越显著． 通常局部社团外部链接度 L 的变化与起始节 点的度数有关大致存在两种情况：一种是选择了节 点度数较小的起始节点从起始节点开始 L 值较 小随着社团成员的增加而逐步增大增大到一定值 后又开始减小到局部最小值；另一种是选择了节点 度数较大的起始节点从起始节点开始 L 值就比较 大随着社团成员的增加而逐步减小一直到达局部 最小值．当 L 达到局部最小值时局部社团的结构 相对比较显著．因此通过 L 的变化就可以很容易 地找到社团的边界． 第1期 王立敏等： 基于最小社团链接度增量的社团结构挖掘算法 ·113·
,114 北京科技大学学报 第31卷 由式(4)可以看出，△L:的计算与社团内外部的 2算法的描述 链接情况无关，只与新加入节点的链接情况有关，因 根据局部社团外部链接度的定义可知，当新的 此社团寻找一个新的节点的计算复杂度为O(d), 节点i合并到社团C后，局部社团外部链接度可能 其中d为网络图的平均节点度.故寻找k个社团 会发生一定的变化、把节点i合并前后局部社团外 成员的计算复杂度为O(kd),其中k为要寻找的社 部链接度的变化量称为节点i的局部社团外部链接 团成员数，把d看作常数，本算法的时间复杂度几 度增量，记为△Li: 乎接近于线性，显然，本算法的时间复杂度明显低 △L=L'-L (3) 于Clauset算法 其中，L与L分别表示加入节点i之前和之后的局 3算法的应用 部社团外部链接度， △L:的计算式(3)经过整理后，简化为： 为了验证本算法的性能和计算的准确性，把本 △L:=E9-E, (4) 算法和Clauset算法应用在计算机生成网络和两个 其中，E表示节点i与社团C外部节点之间的链 真实网络中来进行比较，结果显示，本算法的准确 率与Clauset算法从整体上来说差不多.但是，本算 接数，E表示节点i与社团C内部节点之间的链接 数 法的性能明显优于Clauset算法 3.1计算机生成网络 △L:是用来衡量节点i合并到某社团后局部社 计算机生成网络已经成为一种标准的测试网 团结构的显著性程度变化的指标，如果把一个节点 络，因此，把本算法应用到一组知道社团结构的计 放入某社团，导致局部社团外部链接度增长最慢（或 算机生成的随机网络图中[]，在这些网络图中，每 下降最快)，那么就意味着该节点加入到该社团后形 一个图都有128个节点组成，分成四个社团，每个社 成的局部社团结构是显著的，因此节点的局部社团 团有32个节点，如图2所示，每个节点的节点度p 外部链接度增量△L:较小的节点比△L:增量较大 都被分成两部分，分别为与社团内部相连的边数p“ 的节点更适合合并到该社团中，于是，在对网络节 和与社团外部相连的边数p,即p一pm+p.节 点进行划分的时候，可以根据△L:的值决定哪个节 点之间链接的边都是独立的和随机的.因此p“和 点更适合属于某社团， p的值是网络图中所有节点的平均值，保持p为 本文提出了一种由起始节点开始逐点向外扩张 一个常数16，可以通过调整p的值来改变社团边 的算法，设定一个起始节点0，并把0加入到社 界的尖锐性， 团C中，o的邻居加入到U中.算法执行的每一 步，通过计算U中每一个节点的局部社团外部链接 度增量△L,选择△L:下降最大的节点合并到社团 C中，然后更新U.这个过程不断重复直到找到指 定的k个节点，或者发现完全封闭的社团，算法就 停止，算法的描述如下， Input:vo,; Output:C; (1)select vertex voto C (2)add all neighbors of C to U 图2p“为1的计算机生成社团结构（方形.圆形、三角形和菱形 (3)while IcI<k do 表示网络中四个不同的社团) (4)for each v:∈Udo Fig.2 Community structure of computer generated networks, where p is I(squares,circles,triangles and diamonds indicate four (5)compute△L: communities) (6)end for (7)find△L;such that△L:is minimum 按照上面的规则，对不同的pm随机生成100 (8)add that vito C 个网络图，并对每一个网络图选择从第1个到第 (9)add all new neighbors of that vito U 128个节点作为起始节点来搜索包含128个成员的 (10)end while 社团，得到局部社团外部链接度L与社团的成员数
2 算法的描述 根据局部社团外部链接度的定义可知当新的 节点 i 合并到社团 C 后局部社团外部链接度可能 会发生一定的变化．把节点 i 合并前后局部社团外 部链接度的变化量称为节点 i 的局部社团外部链接 度增量记为ΔL i： ΔL i＝ L′— L （3） 其中L 与 L′分别表示加入节点 i 之前和之后的局 部社团外部链接度． ΔL i 的计算式（3）经过整理后简化为： ΔL i＝ E out i — E in i （4） 其中E out i 表示节点 i 与社团 C 外部节点之间的链 接数E in i 表示节点 i 与社团 C 内部节点之间的链接 数． ΔL i 是用来衡量节点 i 合并到某社团后局部社 团结构的显著性程度变化的指标．如果把一个节点 放入某社团导致局部社团外部链接度增长最慢（或 下降最快）那么就意味着该节点加入到该社团后形 成的局部社团结构是显著的．因此节点的局部社团 外部链接度增量ΔL i 较小的节点比ΔL i 增量较大 的节点更适合合并到该社团中．于是在对网络节 点进行划分的时候可以根据ΔL i 的值决定哪个节 点更适合属于某社团． 本文提出了一种由起始节点开始逐点向外扩张 的算法．设定一个起始节点 v0并把 v0 加入到社 团 C 中v0 的邻居加入到 U 中．算法执行的每一 步通过计算 U 中每一个节点的局部社团外部链接 度增量ΔL i选择ΔL i 下降最大的节点合并到社团 C 中然后更新 U．这个过程不断重复直到找到指 定的 k 个节点或者发现完全封闭的社团算法就 停止．算法的描述如下． Input：v0k； Output：C； （1）select vertex v0to C （2）add all neighbors of C to U （3）while｜C｜＜k do （4）for each vi∈ U do （5）compute ΔL i （6）end for （7）find ΔL i such that ΔL i is minimum （8）add that vi to C （9）add all new neighbors of that vi to U （10）end while 由式（4）可以看出ΔL i 的计算与社团内外部的 链接情况无关只与新加入节点的链接情况有关因 此社团寻找一个新的节点的计算复杂度为 O（ d） 其中 d 为网络图的平均节点度．故寻找 k 个社团 成员的计算复杂度为 O（ kd）其中 k 为要寻找的社 团成员数．把 d 看作常数本算法的时间复杂度几 乎接近于线性．显然本算法的时间复杂度明显低 于 Clauset 算法． 3 算法的应用 为了验证本算法的性能和计算的准确性把本 算法和 Clauset 算法应用在计算机生成网络和两个 真实网络中来进行比较．结果显示本算法的准确 率与 Clauset 算法从整体上来说差不多．但是本算 法的性能明显优于 Clauset 算法． 3∙1 计算机生成网络 计算机生成网络已经成为一种标准的测试网 络．因此把本算法应用到一组知道社团结构的计 算机生成的随机网络图中［2］．在这些网络图中每 一个图都有128个节点组成分成四个社团每个社 团有32个节点如图2所示．每个节点的节点度 p 都被分成两部分分别为与社团内部相连的边数 p in 和与社团外部相连的边数 p out即 p＝ p in＋ p out．节 点之间链接的边都是独立的和随机的．因此 p in和 p out的值是网络图中所有节点的平均值．保持 p 为 一个常数16可以通过调整 p out的值来改变社团边 界的尖锐性． 图2 p out为1的计算机生成社团结构（方形、圆形、三角形和菱形 表示网络中四个不同的社团） Fig．2 Community structure of computer-generated networks where p out is1（squarescirclestriangles and diamonds indicate four communities） 按照上面的规则对不同的 p out 随机生成100 个网络图并对每一个网络图选择从第1个到第 128个节点作为起始节点来搜索包含128个成员的 社团得到局部社团外部链接度 L 与社团的成员数 ·114· 北 京 科 技 大 学 学 报 第31卷
第1期 王立敏等：基于最小社团链接度增量的社团结构挖掘算法 ,115, t的函数关系图，如图3所示.图3中每一条曲线都 2.5 是由100个随机图平均得到的，为了清楚起见，只 2.0 在图中列出了p"为1到7等七种情况下的函数关 Clauset算法 系.，从图中可以看出，在这七个曲线图中，p值越 小，在t=(32,64,96,128)时，L达到局部最小的特 1.0 征越明显，四个局部社团结构也比较显著；随着p 本算法 的增长，L的波谷高度也在不断地增加，四个局部 20 40 6080 100 120 140 社团结构也越来越不明显.特别地，当p=7时， 社州的成员数 网络中存在的四个局部社团结构已经不太明显了· 图5本算法和Clauset算法对计算机生成的网络图搜索社团成 因此通过图3可以充分地说明用局部社团外链接度 员的运行时间 L来衡量局部社团结构的显著性是可行的 Fig.5 Relations of processing time to the number of community 700 vertices by the proposed method and Clauset algorithm +1 600 2 34 3.2 Zachary空手道俱乐部 下面举例来考查本算法和Clauset算法在社会 200 9 网络中的应用，事例出自社会网络分析的一个经典 问题1.20世纪70年代初期，Zachary用了两年的 时间来观察美国一所大学中的空手道俱乐部成员间 20 406080 100120 140 社团成员数 的相互社会关系，基于这些成员在俱乐部内部以及 外部的社会关系，他构造了他们之间的关系网，如 图3p取不同值时局部社团的外部连接度L与搜索社团成员 图6所示.事有凑巧，在调查过程中，该俱乐部的主 数：的函数关系图 管与校长之间因是否抬高俱乐部收费的问题产生了 Fig.3 Relations of the outer link degree of a local community with 争执.结果，该俱乐部分裂成了两个分别以主管和 the number of community vertices at different values of p 校长为核心的小俱乐部.图中节点1和节点33分 同时，把Clauset算法也应用到不同pu值随机 别代表了俱乐部主管和校长，而红色和蓝色的节点 生成的100个网络图中，对每一个图选择从第1个 也分别代表了分裂后的小俱乐部中的各个成员，在 到第128个节点作为起始节点来搜索128个社团成 复杂网络的社团结构分析中，Zachary网络已经成为 员，得到两种算法搜索社团成员的平均正确率的对 一个很好地用于比较挖掘网络社团结构算法准确性 比图和运行执行情况图，如图4和图5所示.图4 的经典网络 显示本算法在p=4之前两种算法的平均正确率 基本差不多，而在put=4之后差于Clauset算法， 图5中曲线的运行时间是128个点搜索社团成员所 需时间的平均值.从图5可以看出，本算法在运行 时间上与Clauset算法相比得到了显著地提高， 12 1.0 Clauset算法 0.8 本算法 图6 Zachary空手道俱乐部分裂的关系网络（方形和圆形分别表 0.6 0.4 示分裂后两个小俱乐部的成员) 0.2 Fig.6 Splitting of the Zachary club network (squares and circles in- 0 dicate the two communities observed by Zachary) 值 图7给出了本算法和Clauset算法对34个起始 图4本算法和Clauset算法搜索社团成员的正确率 节点搜索社团成员的正确率的对照曲线，图中横轴 Fig.4 Rates of correctly classified vertices by the proposed method 表示34个起始节点，纵轴表示每个起始节点搜索社 and Clause algorithm 团成员的正确比率
t 的函数关系图如图3所示．图3中每一条曲线都 是由100个随机图平均得到的．为了清楚起见只 在图中列出了 p out为1到7等七种情况下的函数关 系．从图中可以看出在这七个曲线图中p out值越 小在 t＝（326496128）时L 达到局部最小的特 征越明显四个局部社团结构也比较显著；随着 p out 的增长L 的波谷高度也在不断地增加四个局部 社团结构也越来越不明显．特别地当 p out＝7时 网络中存在的四个局部社团结构已经不太明显了． 因此通过图3可以充分地说明用局部社团外链接度 L 来衡量局部社团结构的显著性是可行的． 图3 p out取不同值时局部社团的外部连接度 L 与搜索社团成员 数 t 的函数关系图 Fig．3 Relations of the outer link degree of a local community with the number of community vertices at different values of p out 同时把 Clauset 算法也应用到不同 p out值随机 生成的100个网络图中对每一个图选择从第1个 到第128个节点作为起始节点来搜索128个社团成 员得到两种算法搜索社团成员的平均正确率的对 比图和运行执行情况图如图4和图5所示．图4 显示本算法在 p out＝4之前两种算法的平均正确率 基本差不多而在 p out ＝4之后差于 Clauset 算法． 图5中曲线的运行时间是128个点搜索社团成员所 需时间的平均值．从图5可以看出本算法在运行 时间上与 Clauset 算法相比得到了显著地提高． 图4 本算法和 Clauset 算法搜索社团成员的正确率 Fig．4 Rates of correctly classified vertices by the proposed method and Clause algorithm 图5 本算法和 Clauset 算法对计算机生成的网络图搜索社团成 员的运行时间 Fig．5 Relations of processing time to the number of community vertices by the proposed method and Clauset algorithm 3∙2 Zachary 空手道俱乐部 下面举例来考查本算法和 Clauset 算法在社会 网络中的应用．事例出自社会网络分析的一个经典 问题［14］．20世纪70年代初期Zachary 用了两年的 时间来观察美国一所大学中的空手道俱乐部成员间 的相互社会关系．基于这些成员在俱乐部内部以及 外部的社会关系他构造了他们之间的关系网如 图6所示．事有凑巧在调查过程中该俱乐部的主 管与校长之间因是否抬高俱乐部收费的问题产生了 争执．结果该俱乐部分裂成了两个分别以主管和 校长为核心的小俱乐部．图中节点1和节点33分 别代表了俱乐部主管和校长而红色和蓝色的节点 也分别代表了分裂后的小俱乐部中的各个成员．在 复杂网络的社团结构分析中Zachary 网络已经成为 一个很好地用于比较挖掘网络社团结构算法准确性 的经典网络． 图6 Zachary 空手道俱乐部分裂的关系网络（方形和圆形分别表 示分裂后两个小俱乐部的成员） Fig．6 Splitting of the Zachary club network （squares and circles indicate the two communities observed by Zachary） 图7给出了本算法和 Clauset 算法对34个起始 节点搜索社团成员的正确率的对照曲线．图中横轴 表示34个起始节点纵轴表示每个起始节点搜索社 团成员的正确比率． 第1期 王立敏等： 基于最小社团链接度增量的社团结构挖掘算法 ·115·
,116 北京科技大学学报 第31卷 1.2 随机选择一个节点（节点度为275）为起始点来 搜索含有1250个成员的社团，得到局部社团外部 0.8 链接度L随着社团成员数t的变化关系图，如图9 0.6 所示，从图9中可以看到，在第263,309,344和428 0.4 等17个节点处的社团结构较为显著 ◆一本算法 0.2 一Clauset算法 300r 15202303540 250 起始节点 200 伤 图7本文算法和Clauset算法对Zachary俱乐部网络搜索社团成 100 员的正确率 Fig.7 Rates of correctly classified vertices using the Zachary club network by Clause algorithm and the proposed method 200 400600800100012001400 社团的成员数 从图7中可以看到，本算法中搜索社团成员全 图9局部社团外部链接度随者社团成员数的变化关系 对的有16个节点，Clauset算法全对的有13个节 Fig.9 Relation of the outer link degree of a local community with 点；本算法中有7个起始节点的正确率高于Clauset the number of community vertices 算法，有l0个起始节点的正确率低于Clauset算法， 此外，本算法的34个节点的平均正确率为0.9246， 分析本算法推测到的局部社团和实际情况是否 高于Clauset算法的平均正确率0.9228.因此，两种 一致.在图8中三角形节点表示起始节点所在的社 算法的正确率基本上差不多.Clauset算法运行的平 团.由于起始节点所在的社团中节点度为1的节点 均时间为0.16s,本算法运行的平均时间为0.009s, 较多，而起始节点的节点度又比较大，因此从起始点 可见本算法运行时间明显少于Clauset算法， 开始，局部社团外部链接度L随着社团成员的增加 3.3电信社群网络 而逐步减小到局部最小值.从图8中可以看到许多 本文的数据是从某市移动电信运营商的计费信 这样类似的社团结构，这恰好与图9中L呈现出多 息系统中抽取某段时间发生的64万条通话记录，共 个从局部最大值逐渐减小到局部最小值的变化曲线 包含41万个电话号码，将通话的电话号码作为图 相吻合 的节点，通话关系作为无向图的边，即如果A呼叫 另外，使用本算法和Clauset算法分别选择100 了B,那么就表示A认识B,并且B也认识A·由于 个不同的起始节点来搜索1250个社团成员，得到 选取的数据是某段时间的通话记录，因此网络中含 100个起始节点运行时间的平均值曲线，如图10所 有大量的节点度（即与该节点相连的边数）为1的节 示.从图10中可以看出，搜索的社团成员数越大， 点，整个网络图中含有连通子图4108个.本文选 本算法在计算时间上越优于Clauset算法，随机选 择其中最大的一个子图进行分析，该子图含有 取了图8中的100个节点，其中包含20个边界点， 51430个节点，65021条边，节点度平均值为2，节点 实验结果显示，本算法与Clauset算法对这些节点探 度标准偏差为10，其局部网络图如图8所示 测到的社团结构是相同的， 350 300 250 C1auet算法 200 本算法 150 100 50 图8包含51430个节点的子图中的部分网络结构（三角形的节 200 400 600800100012001400 针相的成员数 点表示起始节点所在的社团) Fig.8 A portion of community structure of the subgraph including 图10本文算法和Clauset算法运行时间对比 51 430 vertices (triangles indicate the community structure of the Fig.10 Processing time by the proposed method and Clauset algo- source vertex) rithm
图7 本文算法和 Clauset 算法对 Zachary 俱乐部网络搜索社团成 员的正确率 Fig．7 Rates of correctly classified vertices using the Zachary club network by Clause algorithm and the proposed method 从图7中可以看到本算法中搜索社团成员全 对的有16个节点Clauset 算法全对的有13个节 点；本算法中有7个起始节点的正确率高于 Clauset 算法有10个起始节点的正确率低于 Clauset 算法． 此外本算法的34个节点的平均正确率为0∙9246 高于Clauset 算法的平均正确率0∙9228．因此两种 算法的正确率基本上差不多．Clauset 算法运行的平 均时间为0∙16s本算法运行的平均时间为0∙009s 可见本算法运行时间明显少于 Clauset 算法． 图8 包含51430个节点的子图中的部分网络结构（三角形的节 点表示起始节点所在的社团） Fig．8 A portion of community structure of the subgraph including 51430 vertices （triangles indicate the community structure of the source vertex） 3∙3 电信社群网络 本文的数据是从某市移动电信运营商的计费信 息系统中抽取某段时间发生的64万条通话记录共 包含41万个电话号码．将通话的电话号码作为图 的节点通话关系作为无向图的边即如果 A 呼叫 了 B那么就表示 A 认识 B并且 B 也认识 A．由于 选取的数据是某段时间的通话记录因此网络中含 有大量的节点度（即与该节点相连的边数）为1的节 点．整个网络图中含有连通子图4108个．本文选 择其中最大的一个子图进行分析．该子图含有 51430个节点65021条边节点度平均值为2节点 度标准偏差为10其局部网络图如图8所示． 随机选择一个节点（节点度为275）为起始点来 搜索含有1250个成员的社团得到局部社团外部 链接度 L 随着社团成员数 t 的变化关系图如图9 所示．从图9中可以看到在第263309344和428 等17个节点处的社团结构较为显著． 图9 局部社团外部链接度随着社团成员数的变化关系 Fig．9 Relation of the outer link degree of a local community with the number of community vertices 分析本算法推测到的局部社团和实际情况是否 一致．在图8中三角形节点表示起始节点所在的社 团．由于起始节点所在的社团中节点度为1的节点 较多而起始节点的节点度又比较大因此从起始点 开始局部社团外部链接度 L 随着社团成员的增加 而逐步减小到局部最小值．从图8中可以看到许多 这样类似的社团结构这恰好与图9中 L 呈现出多 个从局部最大值逐渐减小到局部最小值的变化曲线 相吻合． 图10 本文算法和 Clauset 算法运行时间对比 Fig．10 Processing time by the proposed method and Clauset algorithm 另外使用本算法和 Clauset 算法分别选择100 个不同的起始节点来搜索1250个社团成员得到 100个起始节点运行时间的平均值曲线如图10所 示．从图10中可以看出搜索的社团成员数越大 本算法在计算时间上越优于 Clauset 算法．随机选 取了图8中的100个节点其中包含20个边界点 实验结果显示本算法与 Clauset 算法对这些节点探 测到的社团结构是相同的． ·116· 北 京 科 技 大 学 学 报 第31卷
第1期 王立敏等：基于最小社团链接度增量的社团结构挖掘算法 ,117, [5]Radicchi F.Castellano C.Cecconi F,et al.Defining and identify- 4结论 ing communities in networks.Proc Natl Acad Sci USA,2004. 101(9):2658 尽管目前有许多关于挖掘网络社团结构的算 [6]Girvan M.New man M E J.Community structure in social and 法，但是这些算法都需要知道网络的整体结构，而对 biological networks.Proe Natl Acad Sci USA,2002.99(2): 于规模庞大而且不断变化的网络（例如万维网）很难 7821 充分了解它的整体结构，此外，在实际应用中，在某 [7]Newman M E J.Mixing patterns in networks.Phys Reo E. 些情况下只是想了解网络的局部社团结构，本文提 2003,67(2):026126 出衡量局部社团结构的数量化指标一局部社团外 [8]Duch J.Arenas A.Community detection in complex networks us- ing extreme optimization.Phys Rev E.2005.72(2):027104 部链接度，以及给出一种挖掘局部社团结构的算法， [9]Wang X T,Chen G R.Lu HT.A very fast algorithm for detect- 可以很好地解决上述问题，本算法的时间复杂度为 ing community structures in complex networks.Phys A.2007. O(kd),其中d为网络的平均节点度数，k为社团 384(2):667 成员数；但搜索社团成员的正确率较Clauset算法略差 [10]Clsuet A.Newman M E J.Cristopher M.Finding community structure in very large network.Phys Rev E.2004.70(6): 066111 参考文献 [11]Xu X W,Yuruk N.Feng Z D,et al.Scan:a structural cluster- [1]Spirin V,Mirny L A.Protein complexes and functional modules ing algorithm for networks/Proceedings of the 13th ACM in molecular networks.Proc Natl Acad Sci USA,2003,100 SIGKDD international Conference on Know ledge Discovery and (21):12123 Data Mining-New York:KDD '07 ACM.2007:824.DOI [2]Newman M E J.Girvan M.Finding and evaluating community =http:∥doi~acm-org/10.1145/1281192.1281280 structure in network.Phys Rev E.2004.69(2):026113 [12]Bagrow JP.Bollt E M.A local method for detecting communi- [3]Wilkinson D M.Huberman B A.A method for finding communi- ties.Phys Rev E,2005,72(4):046108 ty of related genes.Proc Natl Acad Sci USA,2004,101 (Suppl [13]Clauset A.Finding local community structure in networks.Phys 1):5241 RewE,2005,72(2):026132 [4]Gieiser P,Danon L.Community structure in jazz.Ade Complex [14]Zachary WW.An information flow model for conflict and fission S,2003,6(4):565 in small group.JAnthropol Res,1977.33(4):452
4 结论 尽管目前有许多关于挖掘网络社团结构的算 法但是这些算法都需要知道网络的整体结构而对 于规模庞大而且不断变化的网络（例如万维网）很难 充分了解它的整体结构．此外在实际应用中在某 些情况下只是想了解网络的局部社团结构．本文提 出衡量局部社团结构的数量化指标———局部社团外 部链接度以及给出一种挖掘局部社团结构的算法 可以很好地解决上述问题．本算法的时间复杂度为 O（ kd）其中 d 为网络的平均节点度数k 为社团 成员数；但搜索社团成员的正确率较Clauset 算法略差． 参 考 文 献 ［1］ Spirin VMirny L A．Protein complexes and functional modules in molecular networks．Proc Natl Acad Sci USA2003100 （21）：12123 ［2］ Newman M E JGirvan M．Finding and evaluating community structure in network．Phys Rev E200469（2）：026113 ［3］ Wilkinson D MHuberman B A．A method for finding community of related genes．Proc Natl Acad Sci USA2004101（Suppl 1）：5241 ［4］ Gieiser PDanon L．Community structure in jazz．A dv Complex Syst20036（4）：565 ［5］ Radicchi FCastellano CCecconi Fet al．Defining and identifying communities in networks．Proc Natl Acad Sci USA2004 101（9）：2658 ［6］ Girvan MNewman M E J．Community structure in social and biological networks．Proc Natl Acad Sci USA200299（2）： 7821 ［7］ Newman M E J．Mixing patterns in networks．Phys Rev E 200367（2）：026126 ［8］ Duch JArenas A．Community detection in complex networks using extreme optimization．Phys Rev E200572（2）：027104 ［9］ Wang X TChen G RLu H T．A very fast algorithm for detecting community structures in complex networks．Phys A2007 384（2）：667 ［10］ Clsuet ANewman M E JCristopher M．Finding community structure in very large network．Phys Rev E200470（6）： 066111 ［11］ Xu X WYuruk NFeng Z Det al．Scan：a structural clustering algorithm for networks ∥ Proceedings of the 13th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining．New York：KDD ’07ACM2007：824．DOI ＝http：∥doi．acm．org／10．1145／1281192．1281280 ［12］ Bagrow J PBollt E M．A local method for detecting communities．Phys Rev E200572（4）：046108 ［13］ Clauset A．Finding local community structure in networks．Phys Rev E200572（2）：026132 ［14］ Zachary W W．An information flow model for conflict and fission in small group．J A nthropol Res197733（4）：452 第1期 王立敏等： 基于最小社团链接度增量的社团结构挖掘算法 ·117·