A Dynamic Community Discovery Method via Fusing Node Change Information

HE Chao-bo; CHENG Qi-wei; CHENG Jun-wei; LIU Xing-yu; YU Peng; CHEN Qi-mai

doi:10.12263/DZXB.20221142

您当前的位置：

首页 >

文章列表页 >

A Dynamic Community Discovery Method via Fusing Node Change Information

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

- A Dynamic Community Discovery Method via Fusing Node Change Information
- ACTA ELECTRONICA SINICA Vol. 52, Issue 8, Pages: 2786-2798(2024)
- 作者机构：
  
  1.华南师范大学计算机学院，广东广州 510631
  2.维沃移动通信有限公司，广东东莞 523859
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62077045)
- DOI：10.12263/DZXB.20221142
  CLC： TP311;
- Received：11 October 2022，
  
  Revised：2023-01-02，
  
  Published：25 August 2024
- 稿件说明：
移动端阅览
贺超波, 成其伟, 程俊伟, 等. 一种融合节点变化信息的动态社区发现方法[J]. 电子学报, 2024, 52(08): 2786-2798.

HE Chao-bo, CHENG Qi-wei, CHENG Jun-wei, et al. A Dynamic Community Discovery Method via Fusing Node Change Information[J]. Acta Electronica Sinica, 2024, 52(08): 2786-2798.
贺超波, 成其伟, 程俊伟, 等. 一种融合节点变化信息的动态社区发现方法[J]. 电子学报, 2024, 52(08): 2786-2798. DOI：10.12263/DZXB.20221142

HE Chao-bo, CHENG Qi-wei, CHENG Jun-wei, et al. A Dynamic Community Discovery Method via Fusing Node Change Information[J]. Acta Electronica Sinica, 2024, 52(08): 2786-2798. DOI：10.12263/DZXB.20221142

摘要

动态社区发现旨在检测动态复杂网络中蕴含的社区结构，对于揭示网络的功能及演化模式具有重要研究价值.由于相邻时刻网络的社区结构具有平滑性，前一时刻网络的社区划分信息可以用于监督当前时刻网络的社区划分过程，但已有方法均难以有效提取这些信息来提高动态社区发现性能.针对该问题，提出一种融合节点变化信息的动态社区发现方法（Semi-supervised Nonnegative Matrix Factorization combining Node Change Information， NCI-SeNMF）. NCI-SeNMF首先采用

-core分析方法提取前一时刻社区网络的degeneracy-core，并选取degeneracy-core中的节点构造社区隶属先验信息，然后对相邻时刻网络的节点局部拓扑结构变化程度进行量化，并将其用于进一步修正社区隶属先验信息，最后通过半监督非负矩阵分解模型集成社区隶属先验信息进行动态社区发现.在多个人工合成动态网络和真实世界动态网络上进行大量对比实验，结果表明，NCI-SeNMF比现有动态社区发现方法在主要评价指标上至少提升了4.8%.

Abstract

Dynamic community discovery aims to detect community structure in dynamic complex networks

and has important research value for revealing the functions and evolution patterns of networks. Because the community structure of the adjacent snapshot networks is smooth

the community discovery result of the previous snapshot network can be used to supervise the community discovery process of the current snapshot network. However

existing methods are difficult to effectively extract these information to improve the performance of dynamic community discovery. In view of this

a dynamic community discovery method named NCI-SeNMF (Semi-supervised Nonnegative Matrix Factorization combining Node Change Information) is proposed

which can fuse node change information. NCI-SeNMF firstly uses

-core analysis method to extract the degeneracy core of every community network at the previous snapshot

and selects the nodes in the degeneracy core to construct the prior community membership information. Then

it quantifies the change degree of the local topology structure of the nodes in the adjacent snapshot networks

and applies it to further improve the prior community membership information. Finally

it integrates the prior community membership information through semi-supervised nonnegative matrix factorization mo

del to discover dynamic communities. Extensive comparative experiments have been conducted on several synthetic and real-world dynamic networks

and the results show that NCI-SeNMF improves at least 4.8% in term of core evaluation metrics comparing with the existing dynamic community discovery methods.

关键词

Keywords

references

WANG X F , CHEN G R . Complex networks: Small-world, scale-free and beyond [J ] . IEEE Circuits and Systems Magazine , 2003 , 3 ( 1 ): 6 - 20 .

FORTUNATO S , HRIC D . Community detection in networks: A user guide [J ] . Physics Reports , 2016 , 659 : 1 - 44 .

MANSOUREH N , MOHAMMAD H F Z , SUSAN B . Fuzzy community detection on the basis of similarities in structural/attribute in large-scale social networks [J ] . Artificial Intelligence Review , 2022 , 55 : 1373 - 1407 .

LIU S Y , WANG S H . Trajectory community discovery and recommendation by multi-source diffusion modeling [J ] . IEEE Transactions on Knowledge and Data Engineering , 2017 , 29 ( 4 ): 898 - 911 .

HU Z W , LIN A , WILLETT P . Identification of research communities in cited and uncited publications using a co-authorship network [J ] . Scientometrics , 2019 ( 118 ): 1 - 19 .

DILMAGHANI S , BRUST M R , RIBEIRO C H C , et al . From communities to protein complexes: A local community detection algorithm on PPI networks [J ] . PLoS One , 2022 , 17 ( 1 ): e0260484 .

潘剑飞 , 董一鸿 , 陈华辉 , 等 . 基于结构紧密性的重叠社区发现算法 [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)

HE D X , LIU H X , FENG Z Y , et al . A joint community detection model: Integrating directed and undirected probabilistic graphical models via factor graph with attention mechanism [J ] . IEEE Transactions on Big Data , 2022 , 8 ( 4 ): 994 - 1006 .

GARZA S E , SCHAEFFER S E . Community detection with the label propagation algorithm: A survey [J ] . Physica A: Statistical Mechanics and its Applications , 2019 , 534 : 122058 .

MOSCATO V , PICARIELLO A , SPERLI G . Community detection based on game theory [J ] . Engineering Applications of Artificial Intelligence , 2019 , 85 : 773 - 782 .

HE C B , FEI X , CHENG Q W , et al . A survey of community detection in complex networks using nonnegative matrix factorization [J ] . IEEE Transactions on Computational Social Systems , 2022 , 9 ( 2 ): 440 - 457 .

SU X , XUE S , LIU F Z , et al . A comprehensive survey on community detection with deep learning [J ] . IEEE Transactions on Neural Networks and Learning Systems , 2024 , 35 ( 4 ): 4682 - 4702 .

ROSSETTI G , CAZABET R . Community discovery in dynamic networks: A survey [J ] . ACM Computing Survey , 2019 , 51 ( 2 ): 35 .

李赫 , 印莹 , 李源 , 等 . 基于多目标演化聚类的大规模动态网络社区检测 [J ] . 计算机研究与发展 , 2019 , 56 ( 2 ): 281 - 292 .

LI H , YIN Y , LI Y , et al . Large-scale dynamic network community detection by multi-objective evolutionary clustering [J ] . Journal of Computer Research and Development , 2019 , 56 ( 2 ): 281 - 292 . (in Chinese)

DHOUIOUI Z , AKAICHI J . Tracking dynamic community evolution in social networks [C ] // 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2014) . Piscataway : IEEE , 2014 : 764 - 770 .

İLHAN N , ÖĞÜDÜCÜ Ş G . Predicting community evolution based on time series modeling [C ] // Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015 . New York : ACM , 2015 : 1509 - 1516 .

PENG H , YANG R Y , WANG Z , et al . Lime: Low-cost and incremental learning for dynamic heterogeneous information networks [J ] . IEEE Transactions on Computers , 2022 , 71 ( 3 ): 628 - 642 .

WISSEM I , SABEUR A , HAITHEM M , et al . A distributed and incremental algorithm for large-scale graph clustering [J ] . Future Generation Computer Systems , 2022 , 34 : 334 - 347 .

AGARWAL P , VERMA R , AGARWAL A , et al . DyPerm: Maximizing permanence for dynamic community detection [C ] //PHUNG D, TSENG V, WEBB G, et al. Pacific-Asia Conference on Knowledge Discovery and Data Mining .

Cham: Springer , 2018 : 437 - 449 .

YIN Y , ZHAO Y H , LI H , et al . Multi-objective evolutionary clustering for large-scale dynamic community detection [J ] . Information Sciences , 2021 , 549 : 269 - 287 .

WANG S H , LI G P , HU G Y , et al . Community detection in dynamic networks using constraint non-negative matrix factorization [J ] . Intelligent Data Analysis , 2020 , 24 ( 1 ): 119 - 139 .

MA X K , ZHANG B H , MA C Z , et al . Co-regularized nonnegative matrix factorization for evolving community detection in dynamic networks [J ] . Information Sciences , 2020 , 528 : 265 - 279 .

SHIN K , ELIASSI-RAD T , FALOUTSOS C . CoreScope: Graph mining using k-core analysis—Patterns, anomalies and algorithms [C ] // 2016 IEEE 16th International Conference on Data Mining (ICDM) . Piscataway : IEEE , 2016 : 469 - 478 .

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

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 , 10 , 10008 .

MALLIAROS F D , VAZIRGIANNIS M . To stay or not to stay: Modeling engagement dynamics in social graphs [C ] // Proceedings of the 22nd ACM International Conference on Information & Knowledge Management - CIKM’13 . New York : ACM , 2013 : 469 - 478 .

ZHOU T , LÜ L , ZHANG Y C . Predicting missing links via local information [J ] . The European Physical Journal B , 2009 , 71 ( 4 ): 623 - 630 .

成其伟 , 陈启买 , 贺超波 , 等 . 基于改进对称二值非负矩阵分解的重叠社区发现方法 [J ] . 计算机应用 , 2020 , 40 ( 11 ): 3203 - 3210 .

CHENG Q W , CHEN Q M , HE C B , et al . Overlapping community detection method based on improved symmetric binary nonnegative matrix factorization [J ] . Journal of Computer Applications , 2020 , 40 ( 11 ): 3203 - 3210 . (in Chinese)

JIAO P F , LYU H D , LI X M , et al . Temporal community detection based on symmetric nonnegative matrix factorization [J ] . International Journal of Modern Physics B , 2017 , 31 ( 13 ): 1750102 .

LIN Y R , CHI Y , ZHU S H , et al . Facetnet: A framework for analyzing communities and their evolutions in dynamic networks [C ] // Proceedings of the 17th International Conference on World Wide Web . New York : ACM , 2008 : 685 - 694 .

WANG P , GAO Z L , MA X K . Dynamic community detection based on network structural perturbation and topological similarity [J ] . Journal of Statistical Mechanics: Theory and Experiment , 2017 , 2017 ( 1 ): 013401 .

GREENE D , DOYLE D , CUNNINGHAM P . Tracking the evolution of communities in dynamic social networks [C ] // 2010 International Conference on Advances in Social Networks Analysis and Mining . Piscataway : IEEE , 2010 : 176 - 183 .

吴旻诚 . 多层网络中结构与动力学研究 [D ] . 浙江 : 浙江大学 , 2021 .

WU M C . Research on the Structure and Dynamics in Multilayer Networks [D ] . Zhejiang : Zhejiang University , 2021 . (in Chinese)

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Community Discovery and Evolution Analysis Method for Dynamic Attributed Networks

Statistical Mechanics Properties of Bernoulli Generator Matrix Codes

Identification of Node Importance Order Structure Based on Multi-Order Neighborhood Contribution of Complex Network

Community Detection in Complex Networks Based on Link Label Propagation

Related Author

CHENG Qi-mai

HE Chao-bo

TANG Yong

CHENG Hao

YANG Jia-qi

MA Xiao

MENG Fan-hui

HU Gang

Related Institution

Pazhou Lab

Guangdong Province Key Laboratory of Information Security Technology

School of Computer Science and Engineering， Sun Yat-Sen University

School of Systems Science and Engineering， Sun Yat-Sen University

School of Management Science and Engineering， Anhui University of Technology， Maanshan

⁰