计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (8): 127-135.doi: 10.11896/jsjkx.240600103

• 数据库&大数据&数据科学 • 上一篇    下一篇

基于层次结构嵌入的动态社区检测

朱瑞1, 叶亚琴1,2, 李圣文1, 汤子健1, 肖玥1   

  1. 1 中国地质大学(武汉)计算机学院 武汉 430078
    2 智能地学信息处理湖北省重点实验室 武汉 430078
  • 收稿日期:2024-06-17 修回日期:2024-08-31 出版日期:2025-08-15 发布日期:2025-08-08
  • 通讯作者: 叶亚琴(yeyaqin@cug.edu.cn)
  • 作者简介:(1202110914@cug.edu.cn)
  • 基金资助:
    国家自然科学基金(42071382);智能地学信息处理湖北省重点实验室开放研究项目(KLIGIP-2022-B14);桐兴(湖北)投资咨询有限公司合作项目(2021116490)

Dynamic Community Detection with Hierarchical Modularity Optimization

ZHU Rui1, YE Yaqin1,2, LI Shengwen1, TANG Zijian1, XIAO Yue1   

  1. 1 School of Computer Science,China University of Geosciences,Wuhan 430078,China
    2 Hubei Key Laboratory of Intelligent Geo-Information Processing,Wuhan 430078,China
  • Received:2024-06-17 Revised:2024-08-31 Online:2025-08-15 Published:2025-08-08
  • About author:ZHU Rui,born in 2000,postgraduate.Her main research interests include spatial-temporal data mining and network analysis.
    YE Yaqin,born in 1979,Ph.D,associate professor,postgraduate supervisor,is a member of CCF(No.42951M).Her main research interests include intelligent computing of urban multimodal trajectories and spatial reasoning.
  • Supported by:
    National Natural Science Foundation of China(42071382),Open Research Project of Hubei Key Laboratory of Intelligent Geo-Information Processing(KLIGIP-2022-B14) and Tongxing(Hubei) Investment Consulting Co. Project(2021116490).

PDF (PC)

12

摘要： 作为理解复杂网络内在模式和组织结构的有力工具,动态社区检测揭示了网络中相互密集连接的节点集合的演化过程,是社会科学、城市规划等领域的一项基本任务。近年来,动态社区检测领域涌现了大量基于表征学习的方法。这些方法通过融合网络拓扑结构和演化特征,将节点映射到低维连续向量空间中,实现了对节点相似度和差异性的准确度量。然而,现有表征学习方法未能充分考虑节点的长距离信息,导致节点表征未能全面捕捉网络的全局特征。对此,提出了一种基于层次结构嵌入的动态社区检测算法 DHM。具体而言,DHM基于网络的多粒度特性生成层次结构,并通过设计自底向上和自顶向下的消息传递机制,将不同层次的节点组织关系嵌入至节点表征。在人工网络数据集和真实网络数据集上进行的实验结果显示,DHM在标准互信息、调整兰德指数和模块度3个指标上优于现有的动态社区检测算法,可以较好地完成时序网络下的社区检测任务。

关键词: 动态社区检测, 时序网络, 模块度优化, 层次结构, 表征学习

Abstract: Serving as a powerful tool for understanding intrinsic patterns and organizational structures within complex networks,dynamic community detection unveils the evolutionary process of densely connected sets of nodes,standing as a fundamental task in disciplines such as social sciences and urban planning.In recent years,various methods based on representation learning have been applied to the field of dynamic community detection.These methods map structured nodes into low-dimensional continuous latent space by integrating network topology and evolution characteristics,achieving reliable measurement of node similarity and difference.However,existing representation learning methods inadequately consider nodes' long-range information,falling short of capturing global structural features.To address this issue,this paper proposes DHM,which combines modularity optimization and hierarchical structure embedding to capture long-range node interactions.Specifically,DHM generates hierarchical organization based on the network's multi-granularity nature and embeds different levels of node relationships into node representations through bottom-up and top-down message-passing mechanisms.Experimental results on synthetic and real-world network datasets demonstrate that DHM outperforms existing dynamic community detection algorithms in terms of normalized mutual information,adjusted Rand index,and modularity,and can effectively detect communities in temporal networks.

Key words: Dynamic community detection, Dynamic networks, Modularity optimization, Hierarchical structure, Representation learning

中图分类号: 

  • TP181
[1]DOURISBOURE Y,GERACI F,PELLEGRINI M.Extractionand classification of dense communities in the web[C]//Proceedings of the 16th International Conference on World Wide Web.2007:461-470.
[2]LINY R,CHI Y,ZHU S,et al.Analyzing communities and their evolutions in dynamic social networks[J].ACM Transactions on Knowledge Discovery from Data,2009,3(2):1-31.
[3]SINGHC K,JOLAD S.Structure and evolution of Indian physics co-authorship networks[J].Scientometrics,2019,118(2):385-406.
[4]ROSSETTI G,CAZABET R.Community discovery in dynamicnetworks:a survey[J].ACM Computing Surveys,2018,51(2):1-37.
[5]MA R X,DENG G S.Research of Dynamic Community Discovery Based on Role Assorted Thoughts[J].Chinese Journal of Computer Science,2012,39(9):60-63,70.
[6]WANG B B,XIN J C,CHEN J Y,et al.Motif-aware Adaptive Cross-layer Random W alk Community Detection[J].Chinese Journal of Computer Science,2024,51(6):128-134.
[7]CHEN J,YUAN B.Detecting functional modules in the yeastprotein-protein interaction network[J].Bioinformatics,2006,22(18):2283-2290.
[8]DU N,WU B,PEI X,et al.Community detection in large-scalesocial networks[C]//Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 Workshop on Web Mining and Social Network Analysis.2007:16-25.
[9]PAN Y,WANG S H,ZHANG L,et al.Survey of Community Detection in Complex Network[J].Chinese Journal of Computer Science,2022,49(S2):208-218.
[10]HOPCROFT J,KHAN O,KULIS B,et al.Tracking evolvingcommunities in large linked networks[J].Proceedings of the National Academy of Sciences,2004,101(suppl_1):5249-5253.
[11]LIT,WANG W,JIAO P,et al.Exploring temporal community structure via network embedding[J].IEEE Transactions on Cybernetics,2023,53(11):7021-7033.
[12]GUIMERAR,MOSSA S,TURTSCHI A,et al.The worldwide air transportation network:Anomalous centrality,community structure,and cities' global roles[J].Proceedings of the Na-tional Academy of Sciences,2005,102(22):7794-7799.
[13]LUKASOVá A.Hierarchical agglomerative clustering procedure[J].Pattern Recognition,1979,11(5/6):365-381.
[14]TAJEUNAE G,BOUGUESSA M,WANG S.Tracking the evolution of community structures in time-evolving social networks[C]//2015 IEEE International Conference on Data Science and Advanced Analytics(DSAA).IEEE,2015:1-10.
[15]LEVANDOWSKYM,WINTER D.Distance between sets[J].Nature,1971,234(5323):34-35.
[16]JIAT,CAI C,LI X,et al.Dynamical community detection and spatiotemporal analysis in multilayer spatial interaction networks using trajectory data[J].International Journal of Geographical Information Science,2022,36(9):1719-1740.
[17]TRAAGV A,WALTMAN L,VAN ECK N J.From Louvain to Leiden:guaranteeing well-connected communities[J].Scientific Reports,2019,9(1):5233.
[18]NGUYENN P,DINH T N,XUAN Y,et al.Adaptive algorithms for detecting community structure in dynamic social networks[C]//2011 Proceedings IEEE INFOCOM.IEEE,2011:2282-2290.
[19]ZHUANGD,CHANG J M,LI M.DynaMo:Dynamic community detection by incrementally maximizing modularity[J].IEEE Transactions on Knowledge and Data Engineering,2019,33(5):1934-1945.
[20]LONGH,LI X,LIU X W,et al.BBTA:Detecting communities incrementally from dynamic networks based on tracking of backbones and bridges[J].Applied Intelligence,2023,53(1):1084-1100.
[21]LINY R,CHI Y,ZHU S,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.2008:685-694.
[22]FU L D,NIE J J.Dynamic Community Detection Based on Evolutionary Spectral Method[J].Chinese Journal of Computer Science,2018,45(2):171-174.
[23]LIUF,CHOI D,XIE L,et al.Global spectral clustering in dynamic networks[J].Proceedings of the National Academy of Sciences,2018,115(5):927-932.
[24]MA X,DONG D.Evolutionary nonnegative matrix factorization algorithms for community detection in dynamic networks[J].IEEE Transactions on Knowledge and Data Engineering,2017,29(5):1045-1058.
[25]LI D,LIN Q,MA X.Identification of dynamic community intemporal network via joint learning graph representation and nonnegative matrix factorization[J].Neurocomputing,2021,435:77-90.
[26]LI D,MA X,GONG M.Joint learning of feature extraction and clustering for large-scale temporal networks[J].IEEE Transactions on Cybernetics,2023,53(3):1653-1666.
[27]GOYA LP,KAMRA N,HE X,et al.Dyngem:Deep embedding method for dynamic graphs[J].arXiv:1805.11273,2018.
[28]GOYAL P,CHHETRI S R,CANEDO A.dyngraph2vec:Capturing network dynamics using dynamic graph representation learning[J].Knowledge-Based Systems,2020,187:104816.
[29]PU S,ZHAO W D.Community Detection Algorithm for Dyna-mic Academic Network[J].Chinese Journal of Computer Science,2022,49(1):89-94.
[30]PAREJA A,DOMENICONI G,CHEN J,et al.Evolvegcn:Evolving graph convolutional networks for dynamic graphs[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2020:5363-5370.
[31]GAO C,ZHU J,ZHANG F,et al.A novel representation lear-ning for dynamic graphs based on graph convolutional networks[J].IEEE Transactions on Cybernetics,2023,53(6):3599-3612.
[32]LIU H,HE L,ZHANG F,et al.Dynamic community detection over evolving networks based on the optimized deep graph infomax[J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2022,32(5):053119.
[33]KIPF T N,WELLING M.Variational graph auto-encoders[C]//Neural Information Processing Systems Workshop on Bayesian Deep Learning.2016.
[34]ECKART C,YOUNG G.The approximation of one matrix by another of lower rank[J].Psychometrika,1936,1:211-218.
[35]QIU C,HUANG Z,XU W,et al.VGAER:graph neural network reconstruction based community detection[J].arXiv:2201.04066,2022.
[36]ROSSETTI G.RDyn:graph benchmark handling community dynamics[J].Journal of Complex Networks,2017,5(6):893-912.
[37]NEWMANM E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.
[38]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.IEEE,2010:176-183.
[39]GÉNOIS M,BARRAT A.Can co-location be used as a proxy for face-to-face contacts?[J].EPJ Data Science,2018,7(1):1-18.
[40]SUN J,FALOUTSOS C,PAPADIMITRIOU S,et al.Graph-scope:parameter-free mining of large time-evolving graphs[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2007:687-696.
[41]PARANJAPEA,BENSON A R,LESKOVEC J.Motifs in temporal networks[C]//Proceedings of the 10th ACM International Conference on Web Search and Data Mining.2017:601-610.
[42]ROSSI R,AHMED N.The network data repository with interactive graph analytics and visualization[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2015.
[43]LIUF,WU J,ZHOU C,et al.Evolutionary community detection in dynamic social networks[C]//2019 International Joint Conference on Neural Networks(IJCNN).IEEE,2019:1-7.
[44]AGARWALP,VERMA R,AGARWAL A,et al.DyPerm:Maximizing permanence for dynamic community detection[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining.Cham:Springer,2018:437-449.
[45]ZHANG Z,CUI P,PEI J,et al.Timers:Error-bounded svd restart on dynamic networks[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2018.
[46]ESTÉVEZ P A,TESMER M,PEREZ C A,et al.Normalized mutual information feature selection[J].IEEE Transactions on Neural Networks,2009,20(2):189-201.
[47]HUBERT L,ARABIE P.Comparing partitions[J].Journal ofClassification,1985,2:193-218.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发