Email this article THE PROPOSED RESULTS OF ALGORITHM TO DETECT THE COMMUNITY ON SOCIAL NETWORK
About this article
Received: 17/06/20 Revised: 31/08/20 Published: 31/08/20Authors
1. Nguyen Hien Trinh, TNU - University of Information Technology and Communication2. Vu Vinh Quang
, TNU - University of Information Technology and Communication3. Cap Thanh Tung, TNU - University of Education
Abstract
Nowadays, community detecting on social network has been an orientation which draws attention of many researchers. Numerous algorithms have been proposed, but one of the problems that need to be solved for social networks is the fact that the number of vertices and edges of the graph is extremely large. As a result, the volume of calculations in the algorithms could be significantly large, and thus it is difficult to meet with practical requirements. In this article, we introduce a new approach based on certain attributes of special vertex on network and then propose the algorithm of merging vertices of the same centrality to reduce input vertices/ edges of network, and develop in conjunction with label propagation techniques, build a heuristic function to speed up community detection algorithms. Experimental results on the standard data sets showed that, compared to the original label propagation method LPA, the average processing time was reduced down to only 85.5%, while the quality of the community is increased by an average of 1.145 times, thereby confirming the effectiveness of the proposed algorithm.
Keywords
Full Text:
PDF (Tiếng Việt)References
[1]. G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee, “Self organization and identification of web communities,” Computer, vol. 35, no. 3, pp. 66-70, 2002.
[2]. F. Radicchi, and F. Castellano, “Defining and identifying communities in network,” Proceedings of the National Academy of Sciences of the United States of America, 2004.
[3]. M. Girvan, and M. E. Newman, “Community structure in social and biological networks,” Physical review E, vol. 99, pp. 7821-7826, 2002.
[4]. J. R. Tyler, and D. M. Wilkinson, “Automated discovery of community structure within organization,” Physical review E, vol. 15, pp. 723-739, 2003.
[5]. J. W. Pinney, and D. R. Westhead, Betweenness-based decomposition methods for social and biological network. Leeds University Press, 2006.[6]. M. J. Rattigan, M. Maier, and D. Jensen, “Graph clustering with network structure indices,” Proceedings of the 24th international conference on Machine learning, 2007.[7]. S. Gregory, An algorithm to find overlapping community structure in network. Springer Heidelberg, 2007.
[8]. S. Fortunato, Community Detection in Graphs, Physics Reports, 2010.
[9]. U. Brandes, “A faster algorithm for betweenness centrality,” Journal of Mathematical sociology, vol. 25, no. 2, pp. 163-177, 2001.
[10]. M. E. Newman, and M Girvan, “Finding and evaluating community structure in networks,” Phys Rev E Stat Nonlin Soft Matter Phys, vol. 76, pp. 106-119, 2004.[11]. X. Liu, H. M. Cheng, and Z. Y.Zhang, “Evaluation of community detection methods,” IEEE Transactions on Knowledge and Data Engineering, vol. 32, no. 9, pp. 1736-1746, 2019.
[12]. U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale network,” Physics Reports, vol. 23, pp. 306-323, 2007.
[13]. Sara E. Garza, and S. E. Schaeffer, “Community detection with the Label Propagation Algorithm,” Elsevier B.V, vol. 534, pp. 1024-1059, 2019.
[14]. Z. Wu, A. Efros, and S. X. Yu, “Improving generalization via scalable neighborhood component analysis,” In Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, Proceedings, Part VII, 2018, pp. 712-728.
[15]. Meilian, Zh. Zhang, Zh. Qu, and Yukang, “Overlapping Community Detection Using Label Propagation in Large-Scale Complex Networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 31, pp. 1736- 1749, 2019.
[16]. A. Zhang, G. Ren, and Y. Lin, “Detecting community structures in network by label propagation with prediction of percolation transition,” The Scientific word Journal, vol. 14, pp. 315-336, 2014.
[17]. T. Wu, Y. Guo, and L. Chen, “Integrated structure investigation in complex networks by label propagation,” Physica A: Statistical Mechanics and its Applications, vol. 448, pp. 68-80, 2016.
[18]. P. Bonacich, Introduction to Mathematical Sociology. Princeton University Press, 2013.
[19]. L. C. Freeman, “Maintaining the Duality Closeness and Betweenness Centrality,” Social Network, vol. 44, pp. 153-159, 2016.
[20]. J. Leskovec, and Krevl, “A. SNAP Datasets Stanford large network dataset collection,” 2014. [Online]. Available: https://snap.stanford.edu. [Accessed Feb. 26, 2020].
Refbacks
- There are currently no refbacks.