－ 1）
（ 假定 nc = 2 时，Dc = 0）
对于一个给定网络 G 有 M 条边，N 个节点，P =
｛ P1 ，P2 ，…，Pc｝ 对应网络的一个社团结构划分，mc 表 示其中任意一个社团 Pc 的边数，nc 表示社团 Pc 中有 边相连的节点个数。
划分密度总量： 对应整个社团结构的划分密度。
D
2 改进算法
2． 1 算法思想
原算法是先合并成树，然后根据划分密度 D 达 到最大断开。本文的思路是同时考虑边相似度从大 到小的顺序和扩展模块度 Q0 是否增大两个标准，最 后得到一个边的森林结构，然后还原成节点，从而得
到点聚类的重叠社团结构。 具体算法步骤如下： （ 1） 先计算所有相邻边对的相似度 S； （ 2） 按从大到小的顺序对 S 排序； （ 3） 按 S 从大到小的顺序合并边对，并同时计算
LYU Xiao-jun
（ School of Computer，South China Normal University，Guangzhou 510631，China）
Abstract： A new overlapping communities detection algorithm based on links is proposed in this paper，which made the result better for using the extended modularity comparing the algorithm proposed by Ahn［1］． The algorithm can deal with small-scale non highly overlapping networks and obtains a good partition result． Key words： overlapping communities； extended modularity； non highly overlapping
| |
对于给定网络 G 中有公共节点 k 的相邻边 eik 和 ejk，节点 i 和它的邻居节点记为 n + （ i） ； 同理，节点 j 和它的邻居节点记为 n + （ j） 。
1． 2 划分密度
划分密度分量： 对应每个社团的划分密度。
Dc
=
nc （
mc － （ nc － 1） nc － 1） /2 － （ nc
以前，人们往往从节点的角度出发来进行社团挖 掘算法的研 究，但 是 重 叠 社 团 结 构 中 的“骑 墙 节 点 ” 可能会同时属于多个社团，所以从节点角度划分重叠 社团结构效果不是很理想。最近，Evans 等［5］和 Ahn 等［1］分别发 表 了 以 边 为 研 究 对 象 来 划 分 社 团，因 为 节点可能会 属 于 多 个 社 团，但 边 表 示 节 点 之 间 的 关 系，一般只能对应一种确定关系。这样以边为对象来 划分社团能更真实地反映节点在复杂网络中的角色。 但是 Ahn 等［1］提出的算法在小规模非高度重叠的网 络，如 Karate Club 网络、Email 网络中的划分效果并 不是很好，因此本文提出一种改进算法，实验结果表 明这种算法在小规模非高度重叠的网络中也能取得 与实际基本相符的社团划分结果。
0引言
复杂网络 一 般 指 节 点 众 多、连 接 关 系 复 杂 的 网 络，包括社会网络、电力网络、生物网络、新陈代谢网 络等。根据学者的研究，复杂网络一般都具有小世界 现象和幂律分布等统计特性，具体表现为网络中具有 社团结构。所谓社团结构是指整个网络可以由若干 个社团组成，社团之间的连接相对稀疏，社团内部的 连接相对稠密。本文研究的内容就是要从复杂网络 中检测出社团结构，从而更深刻地理解复杂网络的拓 扑特性。
3 实验结果及分析
本文算法是对文献［1］中算法的改进，故下面以 5 个经典的网络（ Karate Club 网络、Dolphins 网络、American-College-Football 网络、Email 网络、Jazz-musician 网络） 就这两个算法的社团划分结果做对比。
表 1 实验结果对比
2013 年第 8 期 文章编号： 1006-2475（ 2013） 08-0046-03
计算机与现代化 JISUANJI YU XIANDAIHUA
总第 216 期
复杂网络重叠社团挖掘算法
吕晓军
( 华南师范大学计算机学院，广东 广州 510631)
摘要： 针对 Ahn 等［1］提出的基于边划分的重叠社团挖掘算法，本文利用扩展模块度做了改进，得到一种新的以边为研究
社团结构可以分为非重叠社团结构和重叠社团 结构。非重叠社团结构是指社团之间互不重叠，每个 节点有且仅属于一个社团。非重叠社团结构把每个 节点严格地划分到某个社团中，而真实世界中这种硬 划分并不能真正反映节点和社团的实际关系，如社会 网络中的人属于多个集体、网络中的网页属于多个主 题等。把这种一个节点可以属于多个社团的节点叫 “骑墙节点”，具有这种“骑墙节点”的社团结构就叫 做重叠社团结构。重叠社团结构更符合真实网络的 社团组织规律，成为近几年社团发现研究的新热点。
络能取得较理想的划分结果，与实13 年第 8 期
但是本文算法所取得的结果中重叠节点过多，是以后 在进一步研究中需要解决的问题。
由于篇幅所限，本文仅列出空手道俱乐部（ Karate Club） 用改进算法得出的社团划分结果：
cluster 1（ 20） ： 9，10，14，15，16，19，20，21，23，24， 25，26，27，28，29，30，31，32，33，34，
算法 网络
Ahn 算法
本文算法
Karate club
22 个社团 D = 0． 285 3 个社团 Q0 = 0． 388
Dolphins
65 个社团 D = 0． 316 4 个社团 Q0 = 0． 482
College football 158 个社团 D = 0． 550 7 个社团 Q0 = 0． 497
Q0 是否增加，如果增加或不变，则正式合并，否则放弃 合并。直到一轮扫描完毕；
（ 4） 再次考虑还没合并的边对，按 S 的相似度从 大到小再次合并，并考虑 Q0 是否增加或不变；
（ 5） 重复步骤（ 4） ，直到所有边都用到或 Q0 开始 减小。
2． 2 算法主程序
void main（ void） ｛ / /主程序包含有 3 个模块 clock_t start，end； Ｒead_Graph（ ） ； / / --step 1： 从文件中读图 start = clock（ ） ； Compute_ClusterForest（ ） ； / / --Step 2： 计算并得到边的森 林结构，继而还原得到关于点的重叠社团结构 GetClusterＲesult（ ） ； end = clock（ ） ； Write_Ｒesult（ ） ； / / --step 3： 输出并将点的社团结构写入 到文本文件中 printf（ " 运行时间为： % ． 3lf 秒 \ n" ，1． 0* （ end-start） / CLK _TCK） ； printf（ " 程序运行完毕，按任意键退出． ． ． \ n" ） ； getch（ ） ； ｝
示网络中节点集合； Auv 是邻接矩阵，当 u，v 有边相连 时为 1，否则为 0； ku，kv 表示节点 u，v 的度； kcu 表示节 点 u 在社团 c 中的内度； m 表示网络中边的总数。
1． 4 Ahn 算法思路
（ 1） 计算所有相邻边对的相似度 S； （ 2） 按从大到小的顺序对 S 排序； （ 3） 按 S 从大到小的顺 序 合 并 边 对，如 果 S 相 同，则同时合并边对，直到合并成为一棵层次聚类树； （ 4） 根据划分密度总量 D 达到最大的标准来断 开得到的层次聚类树，从而得到基于边划分的重叠社 团结构。
cluster 2（ 6） ： 1，5，6，7，11，17， cluster 3（ 18） ： 1，2，3，4，8，9，10，12，13，14，18， 20，22，28，29，31，32，33，
4 结束语
尽管复杂网络的社团检测问题得到了大量的研 究，但还存在一些尚未解决的基本问题，如社团概念 虽然大量使用，但却缺少严格的数学定义； 大多数社 团检测算法虽然性能优越，但所需计算量却很大，尤 其是重叠社团检测算法的研究，其与实际社团结构更 相符，但也更复杂，尚存许多问题亟待解决。这说明 复杂网络中社团检测的研究还需要付出大量的努力。
1 基本概念及相关算法
给定一个无向无权的网络 G = （ V，E） ，V 表示网 络中节点的集合，E 表示边的集合。本文的目的就是 从给定网络中挖掘出以节点为元素的重叠社团结构。
由于是对 Ahn 等［1］提出的算法进行改进，所以 先介绍 Ahn 等在文献［1］中提到的两个重要定义，然 后介绍 重 叠 社 团 中 常 用 评 价 标 准 扩 展 模 块 度 的 概
参考文献： ［1］ Ahn Y Y，Bagrow J P，Lehmann S． Link communities re-
veal multiscale complexity in networks［J］． Nature，2010， 466（ 7307） ： 761-764． ［2］ Chen D，Shang M，Lv Z，et al． Detecting overlapping communities of weighted networks via a local algorithm［J］． Physica A： Statistical Mechanics and its Applications， 2010，389（ 19） ： 4177-4187． ［3］ 骆志刚，丁凡，蒋晓舟，等． 复杂网络社团发现算法研究 新进展［J］． 国防科技大学学报，2011，33（ 1） ： 47-52． ［4］ Shang M S，Chen D B，Zhou T． Detecting overlapping communities based on community cores in complex networks ［J］． Chinese Physics Letters，2010，27（ 5） ： 264-267．