基于连边相似度的重叠社区发现算法研究

• 作者: 傅鹤岗 张程 施伟
• 来源期刊: 计算机应用研究
• 关键词: 社区发现 重叠社区 相似度 划分密度
• 年，卷（期）: 2013,（1）
• 所属期刊栏目: 网络与通信技术
• 页码范围: 221-223
• 页数: 3页
• 分类号: TP393|TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2013.01.056

摘要

针对GN算法在发现重叠社区时存在的不足,以及为了降低算法时间复杂度,提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN.算法依据网络图的连边集进行划分,每一条边被划分到某个特定的社区,而一个节点可以关联多条连边,因此节点可以被划分到不同的社区,从而发现重叠社区.EGN算法首先需要构造网络节点之间连边关系的边图；然后根据边图中节点的关系计算网络图中连边的相似度,在节点之间相似度的基础上提出了连边之间相似度的计算方法；再按照相似度由小到大对边图删除边,构建出边图的树状图.树状图的每一层对应网络的一个划分,采用划分密度函数来衡量划分的质量,以此寻找最优的划分.最后将算法应用到Zachary空手道俱乐部网络中,并与GN算法进行对比,实验结果表明EGN算法能够很好地发现重叠社区.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	傅鹤岗	重庆大学计算机学院	27	305	10.0	16.0
2	施伟	重庆大学计算机学院	2	29	2.0	2.0
3	张程	重庆大学计算机学院	37	241	9.0	13.0