Community Detection Method Based on GNN and Improved K-means

Authors

  • Jinxin Liu

DOI:

https://doi.org/10.62051/ijcsit.v3n1.16

Keywords:

Community detection, GNN, K-means algorithm, Autoencoder

Abstract

As the scale of networks continues to expand, their structures become increasingly complex, and the diversity of node information within these networks intensifies. Traditional community detection methods are no longer capable of meeting the growing demands. Thus, the design of a powerful community detection method with low complexity and cost is an urgent issue to be addressed. This paper proposes a community detection method based on Graph Neural Networks (GNN) and an improved K-means algorithm. Initially, the original adjacency matrix is reconstructed based on the importance of nodes, resulting in a new node similarity matrix. Subsequently, a graph autoencoder is employed to extract structural information from the network graph. The decoder part utilizes the form of vector inner product to restore the similarity matrix using the structural information from the hidden layer. The features extracted by the graph autoencoder are then utilized by the improved K-means algorithm to ultimately achieve community division. Finally, this paper summarizes the shortcomings of community detection and provides a prospect for future research directions.

References

Shchur O, G√ľnnemann S. Overlapping community detection with graph neural networks [J]. arXiv preprint arXiv: 1909. 12201, 2019.

Liu F, Xue S, Wu J, et al. Deep learning for community detection: progress, challenges and opportunities [J]. arXiv preprint arXiv: 2005. 08225, 2020.

Zhang S, Tong H, Xu J, et al. Graph convolutional networks: a comprehensive review [J]. Computational Social Networks, 2019, 6(1): 1-23.

He D, Song Y, Jin D, et al. Community-centric graph convolutional network for unsupervised community detection [C]//Proceedings of the twenty-ninth international conference on international joint conferences on artificial intelligence. 2021: 3515-3521.

Jia S. A study on the improvement of K-means algorithm based on community discovery [C]//5th International Conference on Artificial Intelligence and Advanced Manufacturing (AIAM 2023). IET, 2023, 2023: 312-317.

Su X, Xue S, Liu F, et al. A comprehensive survey on community detection with deep learning [J]. IEEE Transactions on Neural Networks and Learning Systems, 2022.

de Lange S C, de Reus M A, van den Heuvel M P. The Laplacian spectrum of neural networks [J]. Frontiers in computational neuroscience, 2014, 7: 189.

Yang J, Leskovec J. Overlapping community detection at scale: a nonnegative matr-ix factorization approach [C]//Proceedings of the sixth ACM international conferen-ce on Web search and data mining. 2013: 587-596.

Yang J, McAuley J, Leskovec J. Community detection in networks with node attrib-utes [C]//2013 IEEE 13th international conference on data mining. IEEE, 2013: 1151-1156.

Zarandi F D, Rafsanjani M K. Community detection in complex networks using str-uctural similarity [J]. Physica A: Statistical Mechanics and its Applications, 2018, 503: 882-891.

Wang X, Liu G, Li J, et al. Locating structural centers: A density-based clustering method for community detection [J]. PloS one, 2017, 12(1): e0169355.

Sun F Y, Qu M, Hoffmann J, et al. vgraph: A generative model for joint community detection and node representation learning [J]. Advances in Neural Information Pro-cessing Systems, 2019, 32.

Cai B, Wang Y, Zeng L, et al. Edge classification based on Convolutional Neural Networks for community detection in complex network [J]. Physica A: Statistical Mechanics and its Applications, 2020, 556: 124826.

Jin D, Li B Y, Jiao PF, et al. Community detection via joint graph convolutional network embedding in attribute network [C]. Proceedings of ICANN, 2019: 594-606.

Jin D, Liu ZY, Li W H, et al. Graph convolutional networks meet markov random fields: Semi-supervised community detection in attribute networks [C]. Proceedings of the AAAI Conference on Artificial Intelligence, 2019: 152-159.

He D X, You X X, Feng ZY, et al. A network-specific markov random field approach to community detection [C]. Proceedings of the 32nd AAAI Conference on Artificial Intelligence, 2018: 306-313.d [45] He D X, Song Y, Jin D, et al. Community-centric graph convolutional network for unsupervised community detectionC]. Proceedings of the 29th International Joint Conference on Artificial Intelligence, 2021: 3515-3521.

He D X, Song Y, Jin D, et al. Community-centric graph convolutional network for unsupervised community detection [C]. Proceedings of the 29th International Joint Conference on Artificial Intelligence, 2021: 3515-3521.

Zheng Y P, Chen S Y, Zhang X N, et al. Heterogeneous-temporal graph convolutional networks: Make the community detection much better [J]. arXiv preprint arXiv: 1909.10248, 2019.

Wang C, Pan SR, Long GD, et al. MGAE: Marginalized graph autoencoder for graph clustering [C]. Proceedings of the Conference on Information and Knowledge Management, 2017: 889-898.

Wang C, Pan S R, Hu R Q, et al. Attributed graph clustering: A deep attentional embedding approach [C]. Proceedings of the 28th International Joint Conference on Artificial Intelligence, 2019:3670-3676.

Qiu CY, Huang ZC, Xu WZ, et al. VGAER: Graph neural network reconstruction based community detection [C]. Proceedings of AAAI: DLGAAAI'22, 2022.

Zhou X C, Su L T, Li X J, et al. Community detection based on unsupervised attributed network embedding [J]. Expert Systems with Applications, 2023, 213: 118937.

Downloads

Published

15-06-2024

Issue

Section

Articles

How to Cite

Liu, J. (2024). Community Detection Method Based on GNN and Improved K-means. International Journal of Computer Science and Information Technology, 3(1), 127-133. https://doi.org/10.62051/ijcsit.v3n1.16

Similar Articles

1-10 of 79

You may also start an advanced similarity search for this article.