社区发现是复杂网络研究领域的一个重要问题,传统社区发现方法是通过节点间连边紧密程度而实现社区划分的,无法纳入节点的非结构属性.对此,文章基于变分图自编码器(VGAE),提出了一种兼顾节点连边与属性信息的网络社区发现方法(VGAE-INA,VGAE incorporating node attributes),并利用两个不同领域的现实网络数据进行了验证.研究结果表明,通过无监督的迭代学习,文章所提出的融合节点属性特征的变分图自编码器方法可以在同时考虑节点连边关系和节点属性特征情况下有效完成网络社区探查的任务.
Abstract
Community detection is an important issue in the field of complex network research. However, the traditional methods that achieve community detection through the density of edges can not include the non-structural attributes of nodes. In this paper, we propose a method of community detection based on variational graph auto-encoders (VGAE) incorporating node attributes, namely VGAE-INA, and then test the method by real network data in two different fields. Through the experiment, we find that the modularity obtained by the proposed method is not significantly different from the traditional methods (such as the Louvain method) and the methods based on deep learning (such as the node2vec method), but the node similarity in the community is much higher than these methods. This result indicates that through unsupervised iterative learning, VGAE-INA can effectively detect the network community under the condition of considering both connections and attributes of nodes. At the same time, our method also lays the groundwork for the performance improvement of practical applications based on community detection such as personalized recommendations and opinion mining in crowds.
关键词
复杂网络 /
社区发现 /
变分图自编码器 /
节点属性
{{custom_keyword}} /
Key words
Complex network /
community detection /
variational graph auto-encoders (VGAE) /
node attributes
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Girvan M, Newman M E J.Community structure in social and biological networks.Proceedings of the National Academy of Sciences, 2002, 99(12):7821-7826.
[2] Spirin V, Mirny L A.Protein complexes and functional modules in molecular networks.Proceedings of the National Academy of Sciences, 2003, 100(1):12123-12128.
[3] Chen P, Redner S.Community structure of the physical review citation network.Journal of Informetrics, 2010, 4(3):278-290.
[4] Chen J, Yuan B.Detecting functional modules in the yeast protein-protein interaction network.Bioinformatics, 2006, 22(18):2283-2290.
[5] Girvan M, Newman M E J.Community structure in social and biological networks.Proceedings of the National Academy of Sciences, 2002, 99(12):7821-7826.
[6] Newman M E J.Fast algorithm for detecting community structure in networks.Physical Review E, 2004, 69(6):066133.
[7] Blondel V D, Guillaume J L, Lambiotte R, et al.Fast unfolding of communities in large networks.Journal of Statistical Mechanics:Theory and Experiment, 2008, 2008(10):P10008.
[8] Fortunato S, Barthelemy M.Resolution limit in community detection.Proceedings of the National Academy of Sciences, 2007, 104(1):36-41.
[9] Ng A Y, Jordan M I, Weiss Y.On spectral clustering:Analysis and an algorithm.Advances in Neural Information Processing Systems, 2002, 849-856.
[10] Liu F, Xue S, Wu J, et al.Deep learning for community detection:Progress, challenges and opportunities.International Joint Conferences on Artificial Intelligence, 2020, 4981-4987.
[11] Xin X, Wang C, Ying X, et al.Deep community detection in topologically incomplete networks.Physica A:Statistical Mechanics and Its Applications, 2017, 469:342-352.
[12] 张军祥,李书琴,刘斌.基于平滑I1范数的深度稀疏自动编码器社区识别算法.计算机应用研究, 2020, 37(4):1063-1068.(Zhang J X, Li S Q, Liu B.Sparse autoencoder community recognition algorithm based on smoothed I1 norm.Application Research of Computers, 2020, 37(4):1063-1068.)
[13] 尚敬文,王朝坤,辛欣,等.基于深度稀疏自动编码器的社区发现算法.软件学报, 2017, 28(3):648-662.(Shang J W, Wang C K, Xin X, et al.Community detection algorithm based on deep sparse autoencoder.Journal of Software, 2017, 28(3):648-662.)
[14] 李亚芳,梁烨,冯韦玮,等.基于社区优化的深度网络嵌入方法.计算机应用, 2021, 41(7):1956-1963.(Li Y F, Liang Y, Feng W W, et al.Deep network embedding method based on community optimization.Journal of Computer Applications, 2021, 41(7):1956-1963.)
[15] 张士进,张胜,田纪彪,等.基于深度编码器的复杂网络社区发现算法.计算机工程与科学, 2020, 42(9):1640-1648.(Zhang S J, Zhang S, Tian J B, et al.Complex network community detection algorithm based on deep encoder.Computer Engineering and Science, 2020, 42(9):1640-1648.)
[16] Cao J, Jin D, Yang L, et al.Incorporating network structure with node contents for community detection on large networks using deep learning.Neurocomputing, 2018, 297:71-81.
[17] Jia Y, Zhang Q, Zhang W, et al.CommunityGAN:Community detection with generative adversarial nets.The World Wide Web Conference, 2019, 784-794.
[18] Xie Y, Gong M, Wang S, et al.Community discovery in networks with deep sparse filtering.Pattern Recognition:The Journal of the Pattern Recognition Society, 2018, 81:50-59.
[19] Chen Z, Li L, Bruna J.Supervised community detection with line graph neural networks.arXiv preprint, 2020, https://doi.org/10.48550/arXiv.1705.08415.
[20] Ferreyra N E D, Hecking T, Aïmeur E, et al.Community detection for access-control decisions:Analysing the role of homophily and information diffusion in online social networks.Online Social Networks and Media, 2022, 29:100203.
[21] De Salve A, Guidi B, Ricci L, et al.Discovering homophily in online social networks.Mobile Networks&Applications, 2018, 23(6):1715-1726.
[22] Li Y, Han Q, Liu J.Community detection based on autoencoder reconstruction similarity matrix.Journal of Physics:Conference Series, 2019, 1345(3):032055.
[23] Huang X, Chen D, Ren T, et al.A survey of community detection methods in multilayer networks.Data Mining and Knowledge Discovery, 2021, 35(1):1-45.
[24] 李寅龙.节点结构-属性融合的社区发现方法研究.硕士论文,哈尔滨工程大学,哈尔滨,2020.(Li Y L.Research on community detection method of node structure-attribute fusion.Master Thesis.Harbin Engineering University, Harbin, 2020.)
[25] Santos F P, Lelkes Y, Levin S A.Link recommendation algorithms and dynamics of polarization in online social networks.Proceedings of the National Academy of Sciences, 2021, 118(50):e2102141118.
[26] Kipf T N, Welling M.Variational Graph Auto-Encoders.arXiv preprint, 2016, https://arxiv.org/abs/1611.07308.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金(71871108)资助课题.
{{custom_fund}}
PDF(811 KB)
