动态属性网络的语义社区发现及演化分析方法

贺超波; 成其伟; 程俊伟; 杨佳琦; 程颢; 汤庸

doi:10.12263/DZXB.20230239

您当前的位置：

首页 >

文章列表页 >

动态属性网络的语义社区发现及演化分析方法

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

- 动态属性网络的语义社区发现及演化分析方法
- A Community Discovery and Evolution Analysis Method for Dynamic Attributed Networks
- 电子学报 2024年52卷第11期页码：3757-3768
- 作者机构：
  
  1.华南师范大学计算机学院，广东广州 510631
  2.琶洲实验室，广东广州 510335
  3.维沃移动通信有限公司，广东东莞 523859
- 作者简介：
  
  [ "贺超波男，1981年9月出生于广东省河源市.现为华南师范大学计算机学院教授，博士生导师.主要研究方向为图数据挖掘与智能教育.E-mail: hechaobo@foxmail.com" ]
  [ "成其伟男，1997年8月出生于广东省江门市.现工作于维沃移动通信有限公司.主要研究方向为社区发现.E-mail: chengqiwei13@163.com" ]
  [ "程俊伟男，1997年9月出生于福建省宁德市.现为华南师范大学计算机学院博士研究生.主要研究方向为图数据挖掘.Email: jung@m.scnu.edu.cn" ]
  [ "杨佳琦女，2000年5月出生于陕西省咸阳市.现为华南师范大学计算机学院硕士研究生.主要研究方向为知识图谱.E-mail: 2022023277@m.scnu.edu.cn" ]
  [ "程颢男，2000 年2月出生于江西省上饶市.现为华南师范大学硕士研究生.主要研究方向是符号图数据挖掘和社交网络分析.E-mail: haocheng@m.scnu.edu.cn" ]
  [ "汤庸男，1964年5月出生于湖南省张家界市.现为华南师范大学计算机学院教授，博士生导师.主要研究方向为数据智能与云服务、学术社交网络与教育大数据等.E-mail: ytang@m.scnu.edu.cn" ]
- 基金信息：
  
  国家自然科学基金(62077045)
- DOI：10.12263/DZXB.20230239
  中图分类号： TP311
- 收稿：2023-03-14，
  
  修回：2023-05-24，
  
  纸质出版：2024-11-25
- 稿件说明：
移动端阅览
贺超波, 成其伟, 程俊伟, 等. 动态属性网络的语义社区发现及演化分析方法[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 .

浏览量

下载量

CSCD

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

提交

工具集

关联资源

一种融合节点变化信息的动态社区发现方法

不完全非负矩阵分解的加速算法

加性噪声条件下鲁棒说话人确认

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