A Community Discovery and Evolution Analysis Method for Dynamic Attributed Networks

HE Chao-bo; CHENG Qi-wei; CHENG Jun-wei; YANG Jia-qi; CHENG Hao; TANG Yong

doi:10.12263/DZXB.20230239

您当前的位置：

首页 >

文章列表页 >

A Community Discovery and Evolution Analysis Method for Dynamic Attributed Networks

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

- A Community Discovery and Evolution Analysis Method for Dynamic Attributed Networks
- ACTA ELECTRONICA SINICA Vol. 52, Issue 11, Pages: 3757-3768(2024)
- 作者机构：
  
  1.华南师范大学计算机学院，广东广州 510631
  2.琶洲实验室，广东广州 510335
  3.维沃移动通信有限公司，广东东莞 523859
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62077045)
- DOI：10.12263/DZXB.20230239
  CLC： TP311
- Received：14 March 2023，
  
  Revised：2023-05-24，
  
  Published：25 November 2024
- 稿件说明：
移动端阅览
贺超波, 成其伟, 程俊伟, 等. 动态属性网络的语义社区发现及演化分析方法[J]. 电子学报, 2024, 52(11): 3757-3768.

HE Chao-bo, CHENG Qi-wei, CHENG Jun-wei, et al. A Community Discovery and Evolution Analysis Method for Dynamic Attributed Networks[J]. Acta Electronica Sinica, 2024, 52(11): 3757-3768.
贺超波, 成其伟, 程俊伟, 等. 动态属性网络的语义社区发现及演化分析方法[J]. 电子学报, 2024, 52(11): 3757-3768. DOI：10.12263/DZXB.20230239

HE Chao-bo, CHENG Qi-wei, CHENG Jun-wei, et al. A Community Discovery and Evolution Analysis Method for Dynamic Attributed Networks[J]. Acta Electronica Sinica, 2024, 52(11): 3757-3768. DOI：10.12263/DZXB.20230239

摘要

动态属性网络的语义社区发现及演化分析具有重要研究价值，其包含动态社区发现、社区语义解释及社区演化分析三个任务，但现有方法均难以同时实现.针对该问题，提出一种基于联合非负矩阵分解的方法DAN-NMF（NMF for Dynamic Attributed Networks）. DAN-NMF可以统一集成网络拓扑结构信息、节点属性信息及社区演化平滑约束信息，并利用最大最小化优化框架推导相关因子矩阵的迭代更新规则，从而可以直接获得动态社区发现、社区语义解释及社区演化分析结果.在人工合成和真实的动态属性网络进行大量相关实验，结果表明DAN-NMF比最优的基准方法在准确性指标上至少提高了7.3%.此外，在真实动态属性网络上的相关数据分析结果也表明DAN-NMF能够有效地发现动态社区的演化模式，并提供丰富的社区语义解释.

Abstract

The topic of semantic community discovery and evolution analysis in dynamic attributed networks has important research value. It needs to simultaneously accomplish the tasks of dynamic community discovery

community semantic interpretation and community evolution analysis

but existing methods are difficult to achieve this goal. In view of this

this paper proposes a method DAN-NMF (NMF for Dynamic Attributed Networks) based on joint nonnegative matrix factorization. DAN-NMF can uniformly integrate network topology information

attribute information and smooth constraint information from community evolution

and derive iterative update rules of the related factor matrices using the majorization-minimization optimization framework

which helps it to directly obtain the results of dynamic community discovery

community semantic interpretation and community evolution analysis. Extensive experiments are conducted on multiple synthetic and real-world dynamic attributed networks. The results show that DAN-NMF has improved by at least 7.3% in term of accuracy metric

compared to the optimal baseline. Moreover

the data analysis results on real-world dynamic attributed networks also demonstrate that DAN-NMF can effectively discover the evolution patterns of dynamic communities and provide rich community semantic interpretations.

关键词

Keywords

references

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

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 .

MOSCATO V , PICARIELLO A , SPERLÍ G . Community detection based on Game Theory [J ] . Engineering Applications of Artificial Intelligence , 2019 , 85 : 773 - 782 .

JIN D , YU Z Z , JIAO P F , et al . A survey of community detection approaches: From statistical modeling to deep learning [J ] . IEEE Transactions on Knowledge and Data Engineering , 2023 , 35 ( 2 ): 1149 - 1170 .

PALLA G , BARABÁSI A L , VICSEK T . Quantifying social group evolution [J ] . Nature , 2007 , 446 : 664 - 667 .

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 . NewYork : ACM , 2015 : 1509 - 1516 .

LI W M , ZHOU X K , YANG C , et al . Multi-objective optimization algorithm based on characteristics fusion of dynamic social networks for community discovery [J ] . Information Fusion , 2022 , 79 : 110 - 123 .

AGARWAL P , VERMA R , AGARWAL A , et al . DyPerm: Maximizing permanence for dynamic community detection [M ] // Advancesin Knowledge Discovery and Data Mining . Cham : Springer International Publishing , 2018 : 437 - 449 .

MENG F R , ZHANG F , ZHU M , et al . Incremental density-based link clustering algorithm for community detection in dynamic networks [J ] . Mathematical Problems in Engineering , 2016 : 1873504 .

郭昆 , 彭胜波 , 陈羽中 , 等 . 基于密度聚类的增量动态社区发现算法 [J ] . 模式识别与人工智能 , 2018 , 31 ( 11 ): 965 - 978 .

GUO K , PENG S B , CHEN Y Z , et al . Incremental dynamic community detection algorithm based on density clustering [J ] . Pattern Recognition and Artificial Intelligence , 2018 , 31 ( 11 ): 965 - 978 . (in Chinese)

PARK N , ROSSI R , KOH E , et al . CGC: Contrastive graph clustering for community detection and tracking [C ] // Proceedings of the ACM Web Conference 2022 . NewYork : ACM , 2022 : 1115 - 1126 .

CHAKRABARTI D , KUMAR R , TOMKINS A . Evolutionary clustering [C ] // Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . New York : ACM , 2006 : 554 - 560 .

潘剑飞 , 曹燕 , 董一鸿 , 等 . 基于Attention深度随机森林的社区演化事件预测 [J ] . 电子学报 , 2019 , 47 ( 10 ): 2050 - 2060 .

PAN J F , CAO Y , DONG Y H , et al . The community evolution event prediction based on attention deep random forest [J ] . Acta Electronica Sinica , 2019 , 47 ( 10 ): 2050 - 2060 . (in Chinese)

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 .

BELLO G A , HARENBERG S , AGRAWAL A , et al . Community detection in dynamic attributed graphs [M ] // Advanced Data Mining and Applications . Cham : Springer International Publishing , 2016 : 329 - 344 .

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 .

APPEL A P , CUNHA R L F , AGGARWAL C C , et al . Temporally evolving community detection and prediction in content-centric networks [M ] // Machine Learning and Knowledge Discovery in Databases . Cham : Springer International Publishing , 2019 : 3 - 18 .

ZHANG Y L , WU B , NING N W , et al . Dynamic topical community detection in social network: A generative model approach [J ] . IEEE Access , 2019 , 7 : 74528 - 74541 .

LI D , ZHANG S , MA X . Dynamic module detection in temporal attributed networks of cancers [J ] . IEEE/ACM Transactions on Computational Biology and Bioinformatics , 2022 , 19 ( 4 ): 2219 - 2230 .

LEE D D , SEUNG H S . Learning the parts of objects by non-negative matrix factorization [J ] . Nature , 1999 , 401 : 788 - 791 .

DING C , HE X F , SIMON H D . On the equivalence of nonnegative matrix factorization and spectral clustering [C ] // Proceedings of the 2005 SIAM International Conference on Data Mining . Philadelphia, PA : Society for Industrial and Applied Mathematics , 2005 : 606 - 610 .

金弟 , 刘子扬 , 贺瑞芳 , 等 . 面向带属性复杂网络的鲁棒、强解释性社团发现方法 [J ] . 计算机学报 , 2018 , 41 ( 7 ): 1476 - 1489 .

JIN D , LIU Z Y , HE R F , et al . A robust and strong explanation community detection method for attributed networks [J ] . Chinese Journal of Computers , 2018 , 41 ( 7 ): 1476 - 1489 . (in Chinese)

CHOUZENOUX E , FEST J B . SABRINA: A stochastic subspace majorization-minimization algorithm [J ] . Journal of Optimization Theory and Applications , 2022 , 195 ( 3 ): 919 - 952 .

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 .

ROSSETTI G . RDYN:Graph benchmark handling community dynamics [J ] . Journal of Complex Networks , 2017 , 5 ( 6 ): 893 - 912 .

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 .

CHAKRABORTY T , DALMIA A , MUKHERJEE A , et al . Metrics for community analysis: A survey [J ] . ACM Computing Surveys , 2018 , 50 ( 4 ): 1 - 37 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Dynamic Community Discovery Method via Fusing Node Change Information

Accelerated Algorithm to Incomplete Nonnegative Matrix Factorization

Robust Speaker Verification Under Additive Noise Condition

Community Detection in Heterogeneous Network with Semantic Paths

Related Author

CHEN Qi-mai

YU Peng

LIU Xing-yu

HE Chao-bo

SHANG Fan-hua

JIAO Li-cheng

SHI Jia-rong

ZHANG Er-hua

Related Institution

Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Institute of Intelligent Information Processing, Xidian University

School of Computer Science and Engineering, Nanjing University of Science and Technology

国家数字交换系统工程技术研究中心

Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University) Ministry of Education Changchun Jilin China

College of Compuer Science and Technology Jilin University Changchun Jilin China

⁰