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

李辉; 张建朋; 陈福才

doi:10.12263/DZXB.20201422

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-12-08

- 基于流式分析的大规模网络重叠社区发现算法
- A Streaming-Based Overlapping Community Detection Algorithm in Large-Scale Network
- 电子学报 2022年50卷第8期页码：1951-1958
- 作者机构：
  
  信息工程大学信息技术研究所，河南郑州 450002
- 作者简介：
  
  [ "李辉男，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)
- DOI：10.12263/DZXB.20201422
  中图分类号： TP311;
- 收稿：2020-12-11，
  
  修回：2021-06-17，
  
  纸质出版：2022-08-25
- 稿件说明：
移动端阅览
李辉,张建朋,陈福才.基于流式分析的大规模网络重叠社区发现算法[J].电子学报,2022,50(08):1951-1958.

LI Hui,ZHANG Jian-peng,CHEN Fu-cai.A Streaming-Based Overlapping Community Detection Algorithm in Large-Scale Network[J].ACTA ELECTRONICA SINICA,2022,50(08):1951-1958.
李辉,张建朋,陈福才.基于流式分析的大规模网络重叠社区发现算法[J].电子学报,2022,50(08):1951-1958. DOI： 10.12263/DZXB.20201422.

LI Hui,ZHANG Jian-peng,CHEN Fu-cai.A Streaming-Based Overlapping Community Detection Algorithm in Large-Scale Network[J].ACTA ELECTRONICA SINICA,2022,50(08):1951-1958. DOI： 10.12263/DZXB.20201422.

摘要

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

Abstract

To improve the efficiency of community detection in large-scale network

treaming-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.

关键词

Keywords

references

LIERDE H VAN , CHOW T W S , CHEN G R . Scalable spectral clustering for overlapping community detection in large-scale networks [J]. IEEE Transactions on Knowledge and Data Engineering , 2020 , 32 ( 4 ): 754 - 767 .

BLONDEL V D , GUILLAUME J L , LAMBIOTTE R , et al . Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics: Theory and Experiment , 2008 , 2008 ( 10 ): P10008 .

HE K , SHI P , BINDEL D , et al . Krylov subspace approximation for local community detection in large networks [J]. ACM Transactions on Knowledge Discovery from Data , 2019 , 13 ( 5 ): 52(1-30 .

LUO W J , LU N N , NI L , et al . Local community detection by the nearest nodes with greater centrality [J]. Information Sciences , 2020 , 517 : 377 - 392 .

陈洁 , 李锐 , 赵姝 , 等 . 面向图表示社区检测的新型聚类覆盖算法 [J]. 电子学报 , 2020 , 48 ( 9 ): 1680 - 1687 .

CHEN J , LI R , ZHAO S , et al . A new clustering cover algorithm based on graph representation for community detection [J]. Acta Electronica Sinica , 2020 , 48 ( 9 ): 1680 - 1687 . (in Chinese)

GHOSH S , HALAPPANAVAR M , TUMEO A , et al . Distributed Louvain algorithm for graph community detection [C]// 2018 IEEE International Parallel and Distributed Processing Symposium . Vancouver, BC, Canada : IEEE , 2018 : 885 - 895 .

GHAFFARI M , LATTANZI S , MITROVIC S . Improved parallel algorithms for density-based network clustering [C]// International Conference on Machine Learning . Long Beach, California, USA : PMLR , 2019 : 2201 - 2210 .

LIAKOS P , PAPAKONSTANTINOPOULOU K , NTOULAS A , et al . Rapid detection of local communities in graph streams [J]. IEEE Transactions on Knowledge and Data Engineering , 2022 , 34 ( 5 ): 2375 - 2386 .

HOLLOCOU A , MAUDET J , BONALD T , et al . A linear streaming algorithm for community detection in very large networks [EB/OL]. ( 2017-03-08 )[ 2020-12-11 ]. https://arxiv.org/abs/1703.02955 https://arxiv.org/abs/1703.02955 .

李辉 , 陈福才 , 张建朋 , 等 . 一种基于流式分析的重叠社区发现方法及装置 : CN202010780625.X [P]. 2020-12-22 .

YUN S , LELARGE M , PROUTIERE A. Streaming , memory limited algorithms for community detection [C]// NIPS'14: Proceedings of the 27th International Conference on Neural Information Processing Systems . Montreal Canada : MIT Press , 2014 : 3167 - 3175 .

YANG J , LESKOVEC J . Overlapping community detection at scale: A nonnegative matrix factorization approach [C]// WSDM'13: Proceedings of the sixth ACM international conference on Web search and data mining . Rome, Italy : ACM , 2013 : 587 - 596 .

潘剑飞 , 董一鸿 , 陈华辉 , 等 . 基于结构紧密性的重叠社区发现算法 [J]. 电子学报 , 2019 , 47 ( 1 ): 145 - 152 .

PAN J F , DONG Y H , CHEN H H , et al . The overlapping community discovery algorithm based on compact structure [J]. Acta Electronica Sinica , 2019 , 47 ( 1 ): 145 - 152 . (in Chinese)

JIA Y T , ZHANG Q Q , ZHANG W N , et al . CommunityGAN: Community detection with generative adversarial nets [C]//WWW'19: The World Wide Web Conference. San Francisco, CA, USA : ACM , 2019 : 784 - 794 .

LANCICHINETTI A , FORTUNATO S , RADICCHI F . Benchmark graphs for testing community detection algorithms [J]. Physical Review E , 2008 , 78 ( 4 ): 046110 .

EMMONS S , KOBOUROV S , GALLANT M , et al . Analysis of network clustering algorithms and cluster quality metrics at scale [J]. PLoS One , 2016 , 11 ( 7 ): e0159161 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于非负矩阵分解的稀疏网络社区发现算法

基于语义路径的异质网络社区发现方法