电子学报 ›› 2022, Vol. 50 ›› Issue (8): 1951-1958.DOI: 10.12263/DZXB.20201422

• 学术论文 • 上一篇    下一篇

基于流式分析的大规模网络重叠社区发现算法

李辉, 张建朋, 陈福才   

  1. 信息工程大学信息技术研究所,河南 郑州 450002
  • 收稿日期:2020-12-11 修回日期:2021-06-17 出版日期:2022-08-25
    • 通讯作者:
    • 张建朋
    • 作者简介:
    • 李辉 男,1996年出生,湖北丹江口人.国家数字交换系统工程技术研究中心硕士生.主要研究方向为社区发现.E-mail: lihui@alumni.hust.edu.cn
      张建朋 男,1988年出生,河北廊坊人.国家数字交换系统工程技术研究中心助理研究员.主要研究方向为大数据分析、图聚类.E-mail: zjp@ndsc.com.cn
      陈福才 男,1974年出生,江西南昌人.国家数字交换系统工程技术研究中心研究员.主要研究方向为网络安全.E-mail: fucai0309@163.com
    • 基金资助:
    • 国家自然基金青年基金 (62002384); 郑州市协同创新重大专项 (162/32410218); 中国博士后科学基金面上项目 (2020M683760)

A Streaming-Based Overlapping Community Detection Algorithm in Large-Scale Network

LI Hui, ZHANG Jian-peng, CHEN Fu-cai   

  1. Institute of Information Technology,Information Engineering University,Zhengzhou,Henan 450002,China
  • Received:2020-12-11 Revised:2021-06-17 Online:2022-08-25 Published:2022-09-08
    • Corresponding author:
    • ZHANG Jian-peng

摘要:

为了提高在大规模网络中发现社区的效率,提出一种基于流式分析的大规模网络重叠社区发现算法(Streaming-based Overlapping Community Detection algorithm,SOCD).算法对网络中的边进行流式处理,每次只处理一条边且每条边仅被处理一次.根据节点的度、节点对社区的贡献度以及节点移动前后社区间连边数量的变化等信息对节点进行划分.在人工合成网络和真实大规模网络上的一系列实验表明,SOCD算法在时间消耗和内存占用上具有较大的优势,比传统方法快10倍以上,且具有较强的鲁棒性,能够在线性时间和空间复杂度下高效、准确地挖掘网络中的重叠社区结构.

关键词: 社区发现, 重叠社区, 大规模网络, 流式分析, 节点贡献度

Abstract:

To improve the efficiency of community detection in large-scale network, a streaming-based overlapping community detection algorithm(SOCD) is proposed. SOCD processes the edges in a streaming fashion and handles one edge at a time, and each edge is processed only once. The algorithm discovers the community based on the degree of node, the contribution of node to the community, and the change of the number of connected edges between communities. Extensive experiments on synthetic networks and real large-scale networks show that SOCD has great advantages in time consumptions and memory footprints. It is more than 10 times faster than traditional methods and has strong robustness. It can efficiently and accurately mine the overlapping community structures in the network under linear time and space complexity.

Key words: community detection, overlapping community, large-scale network, streaming analysis, node contribution

中图分类号: