Community detection with attributed random walk via seed replacement

Abstract

Community detection methods based on random walks are widely adopted in various network analysis tasks. It could capture structures and attributed information while alleviating the issues of noises. Though random walks on plain networks have been studied before, in real-world networks, nodes are often not pure vertices, but own different characteristics, described by the rich set of data associated with them. These node attributes contain plentiful information that often complements the network, and bring opportunities to the random-walk-based analysis. However, node attributes make the node interactions more complicated and are heterogeneous with respect to topological structures. Accordingly, attributed community detection based on random walk is challenging as it requires joint modelling of graph structures and node attributes.

To bridge this gap, we propose a Community detection with Attributed random walk via Seed replacement (CAS). Our model is able to conquer the limitation of directly utilize the original network topology and ignore the attribute information. In particular, the algorithm consists of four stages to better identify communities. (1) Select initial seed nodes in the network; (2) Capture the better-quality seed replacement path set; (3) Generate the structure-attribute interaction transition matrix and perform the colored random walk; (4) Utilize the parallel conductance to expand the communities. Experiments on synthetic and real-world networks demonstrate the effectiveness of CAS.

Graphical abstract

Keywords

community detection / seeds / colored random walk / parallel conductance

References

[1] Bandyopadhyay S, Vivek S V, Murty M N. Outlier resistant unsupervised deep architectures for attributed network embedding. In: Proceedings of the 13th International Conference on Web Search and Data Mining. 2020, 25−33

[2] Zhe C, Sun A, Xiao X. Community detection on large complex attribute network. In: Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. 2019, 2041− 2049

[3] Wang C, Pan S, Hu R, Long G, Jiang J, Zhang C. Attributed graph clustering: A deep attentional embedding approach. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 1906.06532

[4] Bo H, McConville R, Hong J, Liu W. Social Network Influence Ranking via Embedding Network Interactions for User Recommendation. In: Proceedings of the Web Conference. 2020, 379− 384

[5] Li C , Bai J , Zhang L , Tang H , Luo Y . Opinion community detection and opinion leader detection based on text information and network topology in cloud environment. Information Sciences, 2019, 504 : 61– 83

[6] Huang X, Song Q, Li Y, Hu X. Graph recurrent networks with attributed random walks. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019, 732− 740

[7] Xie W B , Lee Y L , Wang C , Chen D B , Zhou T . Hierarchical clustering supported by reciprocal nearest neighbors. Information Sciences, 2020, 527 : 279– 292

[8] Van L H , Chow T W , Chen G . Scalable spectral clustering for overlapping community detection in large-scale networks. IEEE Transactions on Knowledge and Data Engineering, 2019, 32( 4): 754– 767

[9] Zhu J , Chen B , Zeng Y . Community detection based on modularity and k-plexes. Information Sciences, 2020, 513 : 127– 142

[10] Wąs T, Rahwan T, Skibski O. Random walk decay centrality. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2019, 33: 2197− 2204

[11] Fan Y, Li N, Li C, Ma Z, Latecki L J, Su K. Restart and random walk in local search for maximum vertex weight cliques with evaluations in clustering aggregation. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence. 2017, 622− 630

[12] Peng W , Wang J , Zhao B , Wang L . Identification of protein complexes using weighted pagerank-nibble algorithm and core-attachment structure. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2014, 12( 1): 179– 192

[13] Whang J J , Gleich D F , Dhillon I S . Overlapping community detection using neighborhood-inflated seed expansion. IEEE Transactions on Knowledge and Data Engineering, 2016, 28( 5): 1272– 1284

[14] Yan Y, Bian Y, Luo D, Lee D, Zhang X. Constrained local graph clustering by colored random walk. In: Proceedings of the world wide web conference. 2019, 2137− 2146

[15] Li P , Wang H , Zhu K Q , Wang Z , Hu X , Wu X . A large probabilistic semantic network based approach to compute term similarity. IEEE Transactions on Knowledge and Data Engineering, 2015, 27( 10): 2604– 2617

[16] Ding X, Zhang J, Yang J. A robust two-stage algorithm for local community detection. In: Proceedings of the Knowledge-Based Systems. 2018, 152, 188− 199

[17] Kloumann I M, Kleinberg J M. Community membership identification from small seed sets. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014, 1366− 1375

[18] Freitas S, Cao N, Xia Y, Chau D H P, Tong H. Local Partition in Rich Graphs. In: Proceedings of the 2018 IEEE International Conference on Big Data. 2018, 1001− 1008

[19] Lancichinetti A , Fortunato S . Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 2009, 80( 1): 016118–

[20] Luo D, Ni J, Wang S, Bian Y, Yu X, Zhang X. Deep multi-graph clustering via attentive cross-graph association. In: Proceedings of the 13th International Conference on Web Search and Data Mining. 2020, 393− 401

[21] Cen Y, Zou X, Zhang J, Yang H, Zhou J, Tang J. Representation learning for attributed multiplex heterogeneous network. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019, 1358− 1368

[22] Bo D, Wang X, Shi C, Zhu M, Lu E, Cui P. Structural deep clustering network. In: Proceedings of The Web Conference 2020. 2020, 1400− 1410

[23] Li Y, Sha C, Huang X, Zhang Y. Community detection in attributed graphs: An embedding approach. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2018, 32(1)

[24] Bian Y, Ni J, Cheng W, Zhang X. Many heads are better than one: local community detection by the multi-walker chain. In: Proceedings of the IEEE International Conference on Data Mining. 2017, 21− 30

Acknowledgements

This work is supported by the National Natural Science Foundation of China (Grant Nos. 61762078, 61363058, 61966004, 61966009,U1711263,U1811264), Natural Science Foundation of Gansu Province (21JR7RA114), Northwest Normal University Young Teachers Research Capacity Promotion Plan (NWNU-LKQN2019-2) and Research Fund of Guangxi Key Laboratory of Trusted Software (kx202003).

RIGHTS & PERMISSIONS

2022 Higher Education Press