A fast overlapping community detection algorithm based on label propagation and social network graph clustering coefficient

Journal of Computer Science and Cybernetics - Tập 38 Số 1 - Trang 31--46 - 2022
Nguyen Hien Trinh1, Doan Van Ban2, Vu Vinh Quang1, Cap Thanh Tung3
1Thai Nguyen University of Information and Communication Technology, Z115 Street, Quyet Thang Ward, Thai Nguyen, Viet Nam
2Institute of Information Technology, Vietnam Academy of Science and Technology, 18 Hoang Quoc Viet Street, Cau Giay District, Ha Noi, Viet Nam
3Thai Nguyen University of Education, 20 Luong Ngoc Quyen Street, Quang Trung Ward, Thai Nguyen City, Thai Nguyen Province, Viet Nam

Tóm tắt

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.

Từ khóa

#Social network graph #overlapping communities #label propagation #clustering coefficient #belonging coefficient.

Tài liệu tham khảo

[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.

Thông tin
Thông tin xuất bản

Journal of Computer Science and Cybernetics

Tập 38 Số 1

31--46

Thông tin tác giả