A FAST OVERLAPPING COMMUNITY DETECTION ALGORITHM BASED ON LABEL PROPAGATION AND SOCIAL NETWORK GRAPH CLUSTERING COEFFICIENT

Authors

  • Nguyen Hien Trinh Thai Nguyen University of Information and Communication Technology, Viet Nam
  • Doan Van Ban Institute of Information Technology - Viet Nam Academy of Science and Technology
  • Vu Vinh Quang Thai Nguyen University of Information and Communication Technology, Viet Nam
  • Cap Thanh Tung Thai Nguyen University of Education, Viet Nam

DOI:

https://doi.org/10.15625/1813-9663/38/1/16537

Abstract

Detecting community structure on social network has been an important and interesting issue on which many researchers have paid much attention and developed applications. Many graph clustering algorithms have been applied to find disjoint communities, i.e each node belongs to a single community. However, for social network in particular, public communication network in general, most of communities are not completely detached but they may be embedding, overlapping or crossing, that means certain nodes can belong to more than one community. Overlapping node plays a role of interface between communities and it is really interesting to study the community establishment of these nodes because it reflects dynamic behaviuor of participants.
This article introduces the algorithm to find overlapping communities on huge social network. The proposed COPACN algorithm has been developed on the basis of label propagation, using advanced clustering coefficient to find overlapping communities on social network. Exprermental results on a set of popular, standard social networks and certain real network have shown the high speed and high effiency in finding overlapping structures.

References

[1] Network repository. [Online]. Available: https://networkrepository.com/

[2] C. M. A. Clauset, M. E Newman, “Finding community structure in very large networks,” Physical Review E, 066111, vol. 70, no. 6, 2004.

[3] J. K. A. Lancichinetti, S. Fortunato, “Detecting the overlapping and hierarchical community structure in complex networks,” New Journal of Physics, vol. 11, no. 3, Article ID 033015, 2009.

[4] M. Arab and M. Hasheminezhad, “Efficient community detection algorithm with label propagation using node importance and link weight,” International Journal of Advanced Computer Science and Applications, vol. 9, no. 5, pp. 510–518, 2018.

[5] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proc. Natl Acad. Sci. USA., vol. 99, no. 12, pp. 7821–7826, 2002.

[6] S. Gregory, “A fast algorithm to find overlapping communities in networks,” Lect. Notes Comput. Sci. 5211 408, 2008.

[7] ——, “Finding overlapping communities in networks by label propagation,” New Journal of Physics, 103018., vol. 12, no. 10, 2010.

[8] J. Leskovec and Krevl. Datasets stanford large network dataset collection. [Online]. Available: https://snap.stanford.edu

[9] M. Needham and A. E. Hodler, Graph Algorithms. Oreilly, 2019.

[10] C. S. Saradha and D. P. Arul, “An optimized overlapping and disjoint community detection techniques using improved community overlap propagation algorithm in complex networks,” Advance Scientific Research JCR, vol. 7, no. 4, pp. 782–790, 2020.

[11] T. Schank and D. Wagner, “Approximating clustering coefficient and transitivity,” Journal of Graph Algorithms and Applications, vol. 9, no. 2, pp. 265–275, 2005.

[12] L. Tang and H. Liu, “Graph mining applications to social network analysis,” Managing and Mining Graph Data, Advances in Database Systems, vol. 40, pp. 487–513, 2010.

[13] R. A. U. N. Raghavan and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Phys. Rev. E 036106, vol. 76, 2007.

[14] H. L. J. P. Xuegang Hu, Wei He, “Role-based label propagation algorithm for community detection,” Social and Information Networks, 2016.

Downloads

Published

2022-03-20

Issue

Section

Articles