,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：v0‚k； 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（squares‚circles‚triangles and diamonds indicate four communities） 按照上面的规则‚对不同的 p out 随机生成100 个网络图‚并对每一个网络图选择从第1个到第 128个节点作为起始节点来搜索包含128个成员的 社团‚得到局部社团外部链接度 L 与社团的成员数 ·114· 北 京 科 技 大 学 学 报 第31卷