计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (3): 36-38.DOI: 10.3778/j.issn.1002-8331.2010.03.011

• 研究、探讨 • 上一篇    下一篇

一种重叠社区发现的启发式算法

万雪飞,陈端兵,傅 彦   

  1. 电子科技大学 计算机科学与工程学院,成都 610054
  • 收稿日期:2009-02-17 修回日期:2009-04-07 出版日期:2010-01-21 发布日期:2010-01-21
  • 通讯作者: 万雪飞

Heuristic algorithm for detecting overlapping communities

WAN Xue-fei,CHEN Duan-bing,FU Yan   

  1. School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 610054,China
  • Received:2009-02-17 Revised:2009-04-07 Online:2010-01-21 Published:2010-01-21
  • Contact: WAN Xue-fei

摘要: 提出了一种重叠社区发现的启发式算法。该算法基于局部贡献度的思想,以度最大的节点作为初始社区,逐步把对社区贡献最大的邻节点加入社区;同时考虑了社区的重叠性,若存在对多个社区贡献都很大的边界节点,则把边界节点同时加入到这些社区中。最后利用重叠系数对所划分的社区进行调整,使社区结构更加合理。对两个经典的社会网络Zachary和American College
Football进行了实验测试,实验结果表明:该算法能快速准确地划分出社区,并能挖掘出社区间的边界节点。

关键词: 重叠社区, 社区结构, 社会网络, 边界节点, 启发式算法

Abstract: A heuristic algorithm is proposed to detect overlapping communities in this paper.The algorithm is based on the local modularity and the vertex with greatest degree is considered as the initial community.Then expanding the community by putting the adjacent vertex which has maximal contribution into it.Furthermore,the algorithm takes into account the overlapping property of community.If there are border vertices which contribute greatly to more than one community,adding them to these communities.Finally,In order to make the result more reasonable,the detected communities is adjusted according to overlapping coefficient.Two typical social networks,Zachary and American College Football,are applied to the algorithm.The results show that it can detect overlapping communities rapidly and correctly and also mine the border vertices.

Key words: overlapping communities, community structure, social network, border vertex, heuristic algorithm

中图分类号: