Community detection with attributed random walk via seed replacement
Yang CHANG1, Huifang MA1,2(), Liang CHANG3, Zhixin LI2
1. College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China 2. Guangxi Key Lab of Multi-source Information Mining and Security, Guangxi Normal University, Guilin 541004, China 3. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China
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.
. [J]. Frontiers of Computer Science, 2022, 16(5): 165324.
Yang CHANG, Huifang MA, Liang CHANG, Zhixin LI. Community detection with attributed random walk via seed replacement. Front. Comput. Sci., 2022, 16(5): 165324.
community returned by the community detection algorithm
Tab.1
Fig.2
Fig.3
Fig.4
Datasets
Number of nodes
Mixed parameters μ
Attributes
syn1
600
0.1?0.5
{f1, f2, f3, f5}
syn2
2000
0.1?0.7
{f1, f5, f7, f9, f12, f15}
syn3
5000
0.2,0.5
{f4, f8, f13}
syn4
2000
0.4
{f6, f12, f17}
syn5
5000
0.2
?
Tab.2
Datasets
Number of nodes
Number of edges
Nodes
Edges
Attributes
DBLP
14401
224798
User
Friendship
List of authors' research areas and collaborators
Amazon
10166
148865
Product
Co-purchase relationship
Products’ features
Cora
2708
5429
Paper
Citation relationship
Words appearing in the paper
Tab.3
Fig.5
Fig.6
Fig.7
Fig.8
Fig.9
Fig.10
Fig.11
Method
Average F1-score
Average NMI score
DBLP
Amazon
Cora
DBLP
Amazon
Cora
CAS-noPath
0.492
0.532
0.508
0.487
0.501
0.483
CAS
0.742
0.723
0.755
0.712
0.705
0.692
Tab.4
Method
Average F1-score
Average NMI score
DBLP
Amazon
Cora
DBLP
Amazon
Cora
NISE
0.643
0.659
0.738
0.642
0.703
0.723
CAS-noIG
0.662
0.641
0.751
0.687
0.731
0.732
Tab.5
Method
Average F1-score
Average NMI score
syn1
syn2
syn3
syn4
syn5
syn1
syn2
syn3
syn4
syn5
CRW
0.726
0.667
0.493
0.508
0.683
0.713
0.669
0.448
0.494
0.692
SDCN
0.772
0.672
0.498
0.529
0.685
0.740
0.673
0.481
0.500
0.729
AGGMMR
0.752
0.601
0.402
0.480
0.562
0.689
0.632
0.402
0.488
0.587
CAS-noIG
0.662
0.498
0.284
0.378
0.565
0.598
0.456
0.267
0.353
0.528
CAS
0.775
0.684
0.507
0.532
0.703
0.752
0.685
0.495
0.506
0.734
Tab.6
Method
Average F1-score
Average NMI score
DBLP
Amazon
Cora
DBLP
Amazon
Cora
CRW
0.578
0.603
0.600
0.499
0.473
0.465
SDCN
0.632
0.620
0.602
0.525
0.501
0.499
AGGMMR
0.626
0.523
0.539
0.519
0.481
0.283
CAS-noIG
0.468
0.596
0.543
0.424
0.471
0.441
CAS
0.628
0.623
0.605
0.521
0.505
0.501
Tab.7
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
C Zhe, A Sun, X Xiao. 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
C Wang, S Pan, R Hu, G Long, J Jiang, C Zhang. Attributed graph clustering: A deep attentional embedding approach. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 1906.06532
4
H Bo, R McConville, J Hong, W Liu. Social Network Influence Ranking via Embedding Network Interactions for User Recommendation. In: Proceedings of the Web Conference. 2020, 379− 384
5
C Li , J Bai , L Zhang , H Tang , Y Luo . Opinion community detection and opinion leader detection based on text information and network topology in cloud environment. Information Sciences, 2019, 504 : 61– 83
6
X Huang, Q Song, Y Li, X Hu. 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
W B Xie , Y L Lee , C Wang , D B Chen , T Zhou . Hierarchical clustering supported by reciprocal nearest neighbors. Information Sciences, 2020, 527 : 279– 292
8
L H Van , T W Chow , G Chen . Scalable spectral clustering for overlapping community detection in large-scale networks. IEEE Transactions on Knowledge and Data Engineering, 2019, 32( 4): 754– 767
9
J Zhu , B Chen , Y Zeng . Community detection based on modularity and k-plexes. Information Sciences, 2020, 513 : 127– 142
10
T Wąs, T Rahwan, O Skibski. Random walk decay centrality. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2019, 33: 2197− 2204
11
Y Fan, N Li, C Li, Z Ma, L J Latecki, K Su. 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
W Peng , J Wang , B Zhao , L Wang . 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
J J Whang , D F Gleich , I S Dhillon . Overlapping community detection using neighborhood-inflated seed expansion. IEEE Transactions on Knowledge and Data Engineering, 2016, 28( 5): 1272– 1284
14
Y Yan, Y Bian, D Luo, D Lee, X Zhang. Constrained local graph clustering by colored random walk. In: Proceedings of the world wide web conference. 2019, 2137− 2146
15
P Li , H Wang , K Q Zhu , Z Wang , X Hu , X Wu . A large probabilistic semantic network based approach to compute term similarity. IEEE Transactions on Knowledge and Data Engineering, 2015, 27( 10): 2604– 2617
16
X Ding, J Zhang, J Yang. A robust two-stage algorithm for local community detection. In: Proceedings of the Knowledge-Based Systems. 2018, 152, 188− 199
17
I M Kloumann, J M Kleinberg. 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
S Freitas, N Cao, Y Xia, D H P Chau, H Tong. Local Partition in Rich Graphs. In: Proceedings of the 2018 IEEE International Conference on Big Data. 2018, 1001− 1008
19
A Lancichinetti , S Fortunato . Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 2009, 80( 1): 016118–
20
D Luo, J Ni, S Wang, Y Bian, X Yu, X Zhang. 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
Y Cen, X Zou, J Zhang, H Yang, J Zhou, J Tang. 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
D Bo, X Wang, C Shi, M Zhu, E Lu, P Cui. Structural deep clustering network. In: Proceedings of The Web Conference 2020. 2020, 1400− 1410
23
Y Li, C Sha, X Huang, Y Zhang. Community detection in attributed graphs: An embedding approach. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2018, 32(1)
24
Y Bian, J Ni, W Cheng, X Zhang. 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
