高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于贡献函数的重叠社区划分算法

刘功申 孟魁 郭弘毅 苏波 李建华

刘功申, 孟魁, 郭弘毅, 苏波, 李建华. 基于贡献函数的重叠社区划分算法[J]. 电子与信息学报, 2017, 39(8): 1964-1971. doi: 10.11999/JEIT161109
引用本文: 刘功申, 孟魁, 郭弘毅, 苏波, 李建华. 基于贡献函数的重叠社区划分算法[J]. 电子与信息学报, 2017, 39(8): 1964-1971. doi: 10.11999/JEIT161109
LIU Gongshen, MENG Kui, GUO Hongyi, SU Bo, LI Jianhua . Overlapping-communities Recognition Algorithm Based on Contribution Function[J]. Journal of Electronics & Information Technology, 2017, 39(8): 1964-1971. doi: 10.11999/JEIT161109
Citation: LIU Gongshen, MENG Kui, GUO Hongyi, SU Bo, LI Jianhua . Overlapping-communities Recognition Algorithm Based on Contribution Function[J]. Journal of Electronics & Information Technology, 2017, 39(8): 1964-1971. doi: 10.11999/JEIT161109

基于贡献函数的重叠社区划分算法

doi: 10.11999/JEIT161109
基金项目: 

国家973关键技术研究项目(2013CB329603),国家自然科学基金(61472248)

Overlapping-communities Recognition Algorithm Based on Contribution Function

Funds: 

The National 973 Key Basic Research Program of China (2013CB329603), The National Natural Science Foundation of China (61472248)

  • 摘要: 现实世界中的网络结构呈现出重叠社区的特征。在研究经典的标签算法的基础上,该文提出基于贡献函数的重叠社区发现算法。算法将每个节点用三元组(阈值、标签、从属系数)集合来表示。节点的阈值是每次迭代过程中标签淘汰的依据,该值由多元线性方程自动计算而来。从属系数用于衡量当前节点与标签所标识社区的相关度,从属系数的值越大说明该节点与标签所标识社区的关联性越强。在每一次迭代的过程中,算法依据贡献函数计算每个节点的从属系数,并生成新的三元组集合。然后依据标签决策规则淘汰标签,进行从属系数规范化。通过对真实的复杂网络和LFR(Lancichinetti Fortunato Radicchi)自动生成的网络进行测试可知,该算法的社区划分准确率高,而且划分结果稳定。
  • WANG Xiaofeng, LIU Gongshen, PAN Li, et al. Uncovering fuzzy communities in networks with structural similarity[J]. Neurocomputing, 2016, 210(1): 26-33.
    PALLA G, DERENVI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818.
    LEE C, REID F, McDAID A, et al. Detecting highly overlapping community structure by greedy clique expansion [C]. ACM International Conference on Paper Presented at SNA-KDD Workshop, Washington DC, USA, 2010. arXiv: 1002.1827.
    GREGORY S. An algorithm to find overlapping community structure in networks[J]. LNCS, 2007, 4702(12): 91-102.
    SHI Xiaohua. Community detection in social network with pair wisely constrained symmetric non-negative matrix factorization[C]. Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Paris, France, 2015: 541-546.
    LIU Xiao, WEI Yiming, WANG Jian, et al. Community detection enhancement using no-negative matrix factorization with graph regularization[J]. International Journal of Modern Physics B, 2016, 30(20): 1650130.
    WANG Zhaoxian, WANG Wenjun, XUE Guixiang, et al. Semi-supervised community detection framework based on non-negative factorization using individual labels[C], The Sixth International Conference on Swarm Intelligence, Beijing, China, 2015, 349-359
    RAGHAVAN U N, ALBERT R, and KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E Statistical Nonlinear Soft Matter Physics, 2007, 76(3 Pt 2):036106.
    GREGORY S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2009, 12(10): 2011-2024.
    ULRIK B. A faster algorithm for betweenness centrality[J]. Journal of Mathematical Sociology, 2001, 25(2): 163-177.
    EPPSTEIN D and WANG J. Fast approximation of gentrality[J]. Journal of Graph Algorithms and Applications, 2004, 8(1): 39-45.
    KLEINBERG J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM (JACM), 1999, 46(5): 604-632.
    NICOSIA V, MANGIONI G, CARCHIOLO V, et al. Extending the definition of modularity to directed graphs with overlapping communities[J]. Journal of Statistical Mechanics Theory Experiment, 2009, 2009(3): 3166-3168.
    LANCICHINETTI A, FORTUNATO S, and RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear Soft Matter Physics, 2008, 78(2): 046110.
    CAO Xiaochun, WANG Xiao, JIN Di, et al. Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization[J]. Scientific Reports, 2013, 03: 2993. doi: 10.1038/srep02993.
  • 加载中
计量
  • 文章访问数:  1252
  • HTML全文浏览量:  130
  • PDF下载量:  409
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-10-18
  • 修回日期:  2017-04-24
  • 刊出日期:  2017-08-19

目录

    /

    返回文章
    返回