现 重 叠社 区。
关键词 ：社 区发现 ； 重 叠社 区 ； 相 似度 ； 划分 密度 中图分 类号 ： Ｔ Ｐ ３ ９ ３ ； Ｔ Ｐ ３ ０ １ ． ６ 文献标 志码 ：Ａ 文章编 号 ：１ ０ ０ １ ． ３ ６ ９ ５ （ ２ ０ １ ３ ） ０ １ ． ０ ２ ２ １ ． ０ ３
ｖ ｅ ｒ ｌ ａ ｐ ｐ ｉ ｎ ｇ ｃ ｏ ｍｍｕ ｎ ｉ ｔ ｙ ｉ ｎ ｎ ｅ ｔ ｗ ｏ ｒ ｋ ｓ ａ ｔ ｌ ａ ｓ ｔ ．Ｌ ｉ ｎ ｅ ｇ ｒ ａ ｐ ｈ ｗ ｏ ｕ ｌ ｄ ｂ ｅ ｃ ｏ ｎ ｓ ｔ ｒ ｕ ｃ ｔ ｅ ｄ ｂ ｅ ｆ ｏ ｅ ｕ ｓ ｉ ｎ ｇ ＥＧＮ ｌｇ ａ ｏ ｒ ｉ ｔ ｈ ｍ ｗ ｈ ｉ ｃ ｈ ｂ ａ ｓ ｅ ｄ ｏ ｎ ｔ ｈ ｅ ｒ ｅ － ｌ ａ ｔ ｉ ｏ ｎ ｓ ｈ ｉ ｐ ｏ ｆ ｎ ｏ ｄ ｅ ｓ ｉ ｎ ｎ ｅ ｔ ｗｏ ｒ ｋ ． Ａｎ ｄ ａ ｆ ｔ ｅ ｒ ｔ ｈ ａ ｔ ，ｔ ｈ ｅ ｌｇ ａ ｏ ｒ ｉ ｔ ｈ ｍ ｃ ａ ｌ ｃ ｕ ｌ ａ ｔ ｅ ｄ ｈｅ ｔ ｓ ｉ ｍｉ ｌ ａ ｒ ｉ ｔ ｙ ｏ ｆ ｅ ｄ ｇ ｅ ｓ ｉ ｎ ｎ ｅ ｔ ｗ ｏ ｒ ｋ ．Ｉ ｔ ｐ ｒ ｏ ｐ ｏ ｓ ｅ ｄ ｈｅ ｔ ｍｅ ｔ ｈ ｏ ｄ ｏ ｆ ｃ ａ ｌ ｃ ｕ ｌ ａ ｔ ｉ ｏ ｎ ｏ ｆ ｅ ｄ ｇ ｅ ｓ ｉ ｍｉ ｌ ａ ｉ ｒ ｔ ｙ ｗ ｈ ｉ ｃ ｈ ｂ ａ ｓ ｅ ｄ ｏ ｎ ｔ ｈ ｅ ｓ ｉ ｍｉ ｌ ａ ｒ ｉ ｔ ｙ ｏ ｆ ｎ ｏ ｄ ｅ ，ａ ｎ ｄ ｔ ｈ ｅ ｎ ｃ ｏ ｎ ｓ ｔ ｕｃ ｒ ｔ ｅ ｄ ｄ ｅ ｎ ｄ ｒ ｏ ｒａ ｇ ｍ ｏ ｆ ｌ ｉ ｎ ｅ ｒａ ｇ ｐ ｈ
ｄ ｏ ｉ ： １ ０ ． ３ ９ ６ ９ ／ ｊ ． ｉ ｓ ｓ ｎ ． １ ０ ０ １ ． ３ ６ ９ ５ ． ２ ０ １ ３ ． ０ １ ． ０ ５ ６
Ｏ ｖ ｅ ｒ ｌ ａ ｐ ｐ ｉ ｎ ｇ ｃ ｏ ｍｍｕ ｎ ｉ ｔ ｉ ｅ ｓ ｄ ｅ ｔ ｅ ｃ ｔ ｉ ｎ ｇ ｂ ａ ｓ ｅ ｄ ｏ ｎ ｓ ｉ ｍｉ ｌ ａ ｒ ｉ ｔ ｙ ｏ ｆ ｅ ｄ ｇ ｅ
ｔ ｉ ｏ ｎ ｅ ｄ ｔ ｏ ａ ｌ ｌ ｉ ｎ ｄ ｅ ｐ ｅ ｎ ｄ ｅ ｎ ｔ ｃ ｏ ｍｍｕ ｎ ｉ ｔ ｙ ，ｃ ｏ ｎ ｓ ｅ ｑ ｕ ｅ ｎ ｌ ｔ ｙ ｎ ｏ ｄ ｅ ｓ ｃ ｏ ｕ ｌ ｄ ｂ ｅ ｐ ａ ｒ ｔ ｉ ｔ ｉ ｏ ｎ ｅ ｄ ｔ ｏ ｍｕ ｌ ｔ ｉ ｐ ｌ ｅ ｃ ｏ ｍｍｕ ｎ ｉ ｔ ｉ ｅ ｓ ．Ｉ ｔ ｃ ｏ ｕ ｌ ｄ ｄ ｅ ｔ ｅ ｃ ｔ ｔ ｈ ｅ Ｏ －
第３ ０卷 第 １期
２ ０ １ ３年 １月
计 算 机 应 用 研 究
Ａｐ ｐ ｌ ｉ ｃ ａ ｔ ｉ ｏ ｎ Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ ｏ ｆ Ｃ ｏ ｍｐ ｕ ｔ ｅ ｒ ｓ
Ｖｏ １ ． ３ ０ Ｎｏ ． １
Ｊ ａ ｎ ．２ ０１ ３
基 于 连 边 相 似 度 的重 叠社 区发 现 算 法研 究 木
Ｓ ＨＩ Ｗｅ ｉ ，Ｆ Ｕ Ｈｅ － ｇ ａ ｎ ｇ ，Ｚ ＨＡＮＧ Ｃ ｈ ｅ ｎ ｇ
（ Ｃ ｏ ｔ ｌ ｅ ｇ ￣ ｏ ｆＣ ｏ ｍ ｐ ｕ ｔ ｅ ｒ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ， Ｃ ｈ ｏ ｎ ｇ ｑ ｉ ｎ ｇ Ｕ ｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ ， Ｃ ｈ ｏ ｎ ｇ ｑ ｉ ｒ ｔ ｇ ４ ０ ０ ０ ４ ４ ， Ｃ ｈ ｉ ｎ ａ ）
施
摘
伟， 傅鹤 岗 ， 张
程
（ 重庆大学 计算机学院， 重庆 ４ ０ ０ ０ ４ ４ ） 要 ：针对 Ｇ Ｎ算法在发现重叠社区时存在的不足， 以及为 了降低算法时间复杂度， 提 出一种基于网络 图中
连边相似度划分连边集的重叠社区发现算法 Ｅ Ｇ Ｎ。算法依据网络 图的连边集进行划分 ， 每一条边被划分到某个 特定的社 区， 而一个节点可以关联 多条连边 ， 因此节点可以被划分到不同的社区， 从而发现重叠社 区。Ｅ Ｇ Ｎ算法
首 先 需要 构造 网络 节 点之 间连 边 关 系的边 图； 然后根 据 边 图 中节 点的 关 系计 算 网络 图 中连 边 的相 似度 ， 在节点
之间相似度的基础上提 出了连边之间相似度的计算方法； 再按 照相似度 由小到大对边图删除边 ， 构建 出边图的 树状 图。树状图的每一层对应 网络的一个划分， 采用划分密度函数 来衡量划分的质量， 以此寻找 最优的划分。 最后将算法应 用到 Ｚ ａ ｃ ｈ ａ ｒ ｙ空手道俱乐部网络中， 并与 Ｇ Ｎ算法进行对比， 实验结果表明 Ｅ Ｇ Ｎ算法能够很好地发
ｃ ａ ｌ ｌ ｅ ｄ Ｅ Ｇ Ｎ ｗ ｈ ｉ ｃ ｈ ｂ ａ ｓ ｅ ｄ ｏ ｎ ｈｅ ｔ ｐ ａ ｒ ｔ ｉ ｔ ｉ ｏ ｎ ｏ ｆ ｅ ｄ ｇ ｅ ｓ ｉ ｎ ｎ ｅ ｔ ｗ ｏ ｒ ｋ ．Ａ ｃ ｃ ｏ ｒ ｄ ｉ ｎ ｇ ｔ ｏ ｔ ｈ ｅ ｐ ａ ｒ ｔ ｉ ｔ ｉ ｏ ｎ ｏ ｆ ｅ ｄ ｇ ｅ ｓ ， ｅ ａ ｃ ｈ ｅ ｄ ｇ ｅ ｗ ｏ ｕ ｌ ｄ ｂ ｅ ｐ ａ ｒ ｔ ｉ —
Ａｂ ｓ ｔ ｒ ａ ｃ ｔ ：Ｔ ｏ ｖ ｏ ｉ ｄ ＧＮ ｌｏ ａ ｒ ｉ ｔ ｈ ｍ’ Ｓ ｐ ｒ ｏ ｂ ｌ ｅ ｍ ｎｄ ａ ｒ ｅ ｄ ｕ ｃ ｅ ｔ ｈ ｅ ｃ ｏ ｍｐ ｕ ｔ ａ ｔ ｉ ｏ ｎ ａ ｌ ｃ ｏ ｍｐ ｌ ｅ ｘ ｉ ｔ ｙ ，ｔ ｈ ｉ ｓ ｐ ａ ｐ ｅ ｒ ｐ ｒ ｏ ｐ ｏ ｓ ｅ ｄ ａ ｎ ｅ ｗ ａ ｌ ｇ ｏ ｒ ｉ ｔ ｈ ｍ