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

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

doi:10.12263/DZXB.20201422

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2025-12-08

- A Streaming-Based Overlapping Community Detection Algorithm in Large-Scale Network
- ACTA ELECTRONICA SINICA Vol. 50, Issue 8, Pages: 1951-1958(2022)
- 作者机构：
  
  信息工程大学信息技术研究所，河南郑州 450002
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20201422
  CLC： TP311;
- Received：11 December 2020，
  
  Revised：2021-06-17，
  
  Published：25 August 2022
- 稿件说明：
移动端阅览
李辉,张建朋,陈福才.基于流式分析的大规模网络重叠社区发现算法[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

The Non-negative Matrix Factorization Based Algorithm for Community Detection in Sparse Networks

Community Detection in Heterogeneous Network with Semantic Paths

Related Author

Jian-peng ZHANG

Fu-cai CHEN

Hui LI

ZUO Wan-li

PENG Tao

GUO Lin

JIN Hong

HU Zhi-qun

Related Institution

Institute of Information Technology，Information Engineering University

Symbol Computation and Knowledge Engineer of Ministry of Education of Jilin University

College of Computer Science and Technology of Jilin University

College of Computer Science and Technology of Jilin University Changchun Jilin China

Symbol Computation and Knowledge Engineer of Ministry of Education of Jilin University Changchun Jilin China

⁰