• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

复杂网络的重叠社区发现并行算法

滕飞 戴荣杰 任晓春

滕飞, 戴荣杰, 任晓春. 复杂网络的重叠社区发现并行算法[J]. 西南交通大学学报, 2019, 54(1): 211-218. doi: 10.3969/j.issn.0258-2724.20160478
引用本文: 滕飞, 戴荣杰, 任晓春. 复杂网络的重叠社区发现并行算法[J]. 西南交通大学学报, 2019, 54(1): 211-218. doi: 10.3969/j.issn.0258-2724.20160478
TENG Fei, DAI Rongjie, REN Xiaochun. Parallel Algorithm for Overlapping Community Detection in Complex Networks[J]. Journal of Southwest Jiaotong University, 2019, 54(1): 211-218. doi: 10.3969/j.issn.0258-2724.20160478
Citation: TENG Fei, DAI Rongjie, REN Xiaochun. Parallel Algorithm for Overlapping Community Detection in Complex Networks[J]. Journal of Southwest Jiaotong University, 2019, 54(1): 211-218. doi: 10.3969/j.issn.0258-2724.20160478

复杂网络的重叠社区发现并行算法

doi: 10.3969/j.issn.0258-2724.20160478
基金项目: 国家自然科学基金资助项目(61573292,61572407);四川省软科学研究计划资助项目(2016ZR0034)
详细信息
    作者简介:

    滕飞(1984—),女,副教授,研究方向为数据挖掘与云计算,E-mail: fteng@swjtu.edu.cn

    通讯作者:

    任晓春(1962—),男,教授级高级工程师,研究方向为云计算与轨道工程信息化,E-mail: renxcne@163.com

  • 中图分类号: V221.3

Parallel Algorithm for Overlapping Community Detection in Complex Networks

  • 摘要: 随着网络规模的快速增长,传统社区发现算法难以处理大规模网络数据和满足复杂网络的可扩展分析需求. 本文提出一种适用于大规模复杂网络的重叠社区发现算法PHLink. 该算法根据复杂网络的无标度特性将节点建立连边的原因进行分析和归类,用以识别网络中具有重叠性的社区结构,并采用MapReduce计算框架对网络进行分割和冗余存储,减弱了图计算的耦合性,解决了社区发现算法的分布式计算问题. 通过真实网络测试,PHLink算法可以大幅度降低边计算的复杂度,对于无标度特性明显的复杂网络提取0.1%的枢纽节点即可节省94%以上的计算量,较传统算法具有较高的稳定性和准确性,并且在Hadoop平台有良好的加速性和伸缩性,可以处理千万级连边规模的大规模复杂网络.

     

  • 图 1  PHLink算法示意

    Figure 1.  Overview diagram for PHLink

    图 2  综合性能比较

    Figure 2.  Comparison of composite performance

    表  1  基准测试数据集

    Table  1.   Benchmark datasets

    网络 节点数 边数 描述
    Football 115 616 足球联盟
    Jazz 198 2 742 爵士合作
    Facebook 5 000 8 194 社交网络
    DBLP* 317 080 1 049 866 引文网络
    Amazon* 334 863 925 872 商品网络
    YouTube* 1 134 890 2 987 624 视频网络
    Skitter 3 997 962 11 095 298 网络拓扑
    下载: 导出CSV

    表  2  比例阈值对计算量的影响

    Table  2.   Effect of proportional threshold on computation

    网络 1.0% 0.5% 0.1%
    Facebook 73 48 22
    DBLP 56 37 21
    Amazon 46 35 20
    YouTube 99 98 94
    Skitter 99 98 96
    下载: 导出CSV

    表  3  运行时间比较

    Table  3.   Comparison of computation time

    网络 PHLink Link CPM Bigclam
    Football 0.21 0.24 0.73 0.69 (30)
    Jazz 16.9 25.5 56.3 (30)
    Facebook 3.62 3.92 135 (30)
    DBLP 291 395 5 358 (13.5k)
    Amazon 75.5 85.8 4 442 (75k)
    YouTube 346
    Skitter 6 242
    下载: 导出CSV

    表  4  PHLink算法加速性能

    Table  4.   Speedup for PHLink

    网络 4节点 8节点 12节点
    YouTube 603 444 346
    Skitter 17 984 9 483 6 242
    下载: 导出CSV
  • PALLA G, DERÉNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814-818
    ADAMCSEK B, PALLA G, FARKAS I J, et al. CFinder:locating cliques and overlapping modules in biological networks[J]. Bioinformatics, 2006, 22(8): 1021-1023 doi: 10.1093/bioinformatics/btl039
    LANCICHINETTI A, FORTUNATO S, KERTESZ J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physicals, 2008, 11(3): 19-44
    李首庆,徐洋. 基于自适应聚概率矩阵的JPDA算法研究[J]. 西南交通大学学报,2017,52(2): 340-347 doi: 10.3969/j.issn.0258-2724.2017.02.018

    LI Shouqing, XU Yang. Joint probabilistic data association algorithm based on adaptive cluster probability matrix[J]. Journal of Southwest Jiaotong University, 2017, 52(2): 340-347 doi: 10.3969/j.issn.0258-2724.2017.02.018
    刘世超,朱福喜,甘琳. 基于标签传播概率的重叠社区发现算法[J]. 计算机学报,2016,39(4): 717-729

    LIU Shichao, ZHU Fuxi, GAN Lin. A label-propagation probability based algorithm for overlappling community detection[J]. Chinese Journal of Computers, 2016, 39(4): 717-729
    YANG J, LESKOVEC J. Overlapping communities explain core-periphery organization of networks[J]. Proceedings of the IEEE, 2014, 102(12): 1892-1902 doi: 10.1109/JPROC.2014.2364018
    WANG X, LIU G, LI J, et al. Locating structural centers:a density-based clustering method for community detection[J]. Plos One, 2017, 12(1): e0169355 doi: 10.1371/journal.pone.0169355
    AHN Y Y, BAGROW J P, LEHMANN S. Link communities reveal multiscale complexity in networks[J]. Nature, 2010, 466(7307): 761-764 doi: 10.1038/nature09182
    SUN H, LIU J, HUANG J, et al. LinkLPA:a link-based label propagation algorithm for overlapping community detection in networks[J]. Computational Intelligence, 2017, 33(2): 308-331 doi: 10.1111/coin.12087
    乔少杰,郭俊,韩楠,等. 大规模复杂网络社区并行发现算法[J]. 计算机学报,2017,40(3): 687-700

    QIAO Shaojie, GUO Jun, HAN Nan, et al. Parallel algorithm for discovering communities in large-scale complex networks[J]. Chinese Journal of Computers, 2017, 40(3): 687-700
    BU Z, WU Z, CAO J, et al. Local community mining on distributed and dynamic networks from a multiagent perspective[J]. IEEE Transactions on Cybernetics, 2017, 46(4): 986-999
    CLAUSET A, SHALIZI C R, NEWMAN M E J. Power-law distributions in empirical data[J]. Siam Review, 2012, 51(4): 661-703
    YANG J, LESKOVEC J. Defining and evaluating network communities based on ground-truth[J]. Knowledge & Information Systems, 2012, 42(1): 745-754
    CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(2): 066111-1-066111-6
  • 加载中
图(2) / 表(4)
计量
  • 文章访问数:  518
  • HTML全文浏览量:  217
  • PDF下载量:  25
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-04-18
  • 修回日期:  2018-03-21
  • 网络出版日期:  2018-03-27
  • 刊出日期:  2019-02-01

目录

    /

    返回文章
    返回