A new local centrality measure for detecting community cores in social networks
محورهای موضوعی : journal of Artificial Intelligence in Electrical EngineeringJafar Sheikhzadeh 1 , bagher zarei 2 , Farhad Soleimanian Gharehchopogh 3
1 - ایران، اهر، دانشگاه آزاد اسلامی، واحد اهر، دانشکده فنی و مهندسی
2 - ایران، شبستر، دانشگاه آزاد اسلامی، واحد شبستر، دانشکده فنی و مهندسی
3 - ایران، ارومیه، دانشگاه آزاد اسلامی، واحد ارومیه، دانشکده فنی و مهندسی
کلید واژه: Community Detection, Modularity, Nodes centrality, Social Network Analysis,
چکیده مقاله :
Community detection is one of the important challenges in social network analysis. This problem involves identifying the internal structures of the network and grouping nodes into communities with common characteristics. One of the effective approaches for community detection is to identify important nodes in the network and consider them as the initial cores of communities. In this study, first, a new local centrality criterion is introduced to determine the importance of nodes. Based on this criterion, important nodes are identified and considered as the cores of initial communities. Also, in this paper, a new algorithm called CDHC is presented for community detection. The new centrality criterion is used to identify exhausted initial communities. Modularity and NMI indices are used to evaluate the proposed algorithm. The results of the proposed algorithm on real and artificial networks show that the proposed algorithm is efficient compared to other algorithms.
Community detection is one of the important challenges in social network analysis. This problem involves identifying the internal structures of the network and grouping nodes into communities with common characteristics. One of the effective approaches for community detection is to identify important nodes in the network and consider them as the initial cores of communities. In this study, first, a new local centrality criterion is introduced to determine the importance of nodes. Based on this criterion, important nodes are identified and considered as the cores of initial communities. Also, in this paper, a new algorithm called CDHC is presented for community detection. The new centrality criterion is used to identify exhausted initial communities. Modularity and NMI indices are used to evaluate the proposed algorithm. The results of the proposed algorithm on real and artificial networks show that the proposed algorithm is efficient compared to other algorithms.
1. Girvan, M. and M.E. Newman, Community structure in social and biological networks. Proceedings of the national academy of sciences, 2002. 99(12): p. 7821-7826.
2. Newman, M.E. and M. Girvan, Finding and evaluating community structure in networks. Physical review E, 2004. 69(2): p. 026113.
3. Newman, M.E., Fast algorithm for detecting community structure in networks. Physical review E, 2004. 69(6): p. 066133.
4. Radicchi, F., et al., Defining and identifying communities in networks. Proceedings of the national academy of sciences, 2004. 101(9): p. 2658-2663.
5. Fortunato, S. and M. Barthelemy, Resolution limit in community detection. Proceedings of the national academy of sciences, 2007. 104(1): p. 36-41.
6. Good, B.H., Y.-A. De Montjoye, and A.J.P.r.E. Clauset, Performance of modularity maximization in practical contexts. 2010. 81(4): p. 046106.
7. Delvenne, J.-C., S.N. Yaliraki, and M.J.P.o.t.n.a.o.s. Barahona, Stability of graph communities across time scales. 2010. 107(29): p. 12755-12760.
8. Zhou, H. and R. Lipowsky. Network brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities. in Computational Science-ICCS 2004: 4th International Conference, Kraków, Poland, June 6-9, 2004, Proceedings, Part III 4. 2004. Springer.
9. Raghavan, U.N., R. Albert, and S. Kumara, Near linear time algorithm to detect community structures in large-scale networks. Physical review E, 2007. 76(3): p. 036106.
10. Fortunato, S., Community detection in graphs. Physics reports, 2010. 486(3-5): p. 75-174.
11. Kernighan, B.W. and S. Lin, An efficient heuristic procedure for partitioning graphs. The Bell system technical journal, 1970. 49(2): p. 291-307.
12. Pons, P. and M. Latapy, Computing communities in large networks using random walks. J. Graph Algorithms Appl., 2006. 10(2): p. 191-218.
13. Xi, J., W. Zhan, and Z.J.I.J.D.T.A. Wang, Hierarchical community detection algorithm based on node similarity. 2016. 9(6): p. 209-218.
14. Blondel, V.D., et al., Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008. 2008(10): p. P10008.
15. Zarandi, F.D. and M.K. Rafsanjani, Community detection in complex networks using structural similarity. Physica A: Statistical Mechanics and its Applications, 2018. 503: p. 882-891.
16. Barber, M.J. and J.W. Clark, Detecting network communities by propagating labels under constraints. Physical Review E, 2009. 80(2): p. 026129.
17. Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4), 1118-1123.
18. Sheykhzadeh, J., Zarei, B., & Gharehchopogh, F. S. (2024). Community detection in social networks using a local approach based on node ranking. IEEE Access.
19. Liu, X. and T. Murata, Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A: Statistical Mechanics and its Applications, 2010. 389(7): p. 1493-1500.
20. Ding, X., J. Zhang, and J. Yang, A robust two-stage algorithm for local community detection. Knowledge-Based Systems, 2018. 152: p. 188-199.
21. Wang, T., L. Yin, and X. Wang, A community detection method based on local similarity and degree clustering information. Physica A: Statistical Mechanics and its Applications, 2018. 490: p. 1344-1354.
22. Pan, X., et al., A Novel Community Detection Algorithm Based on Local Similarity of Clustering Coefficient in Social Networks. IEEE Access, 2019. 7: p. 121586-121598.
23. You, X., Y. Ma, and Z. Liu, A three-stage algorithm on community detection in social networks. Knowledge-Based Systems, 2020. 187: p. 104822.
24. Torkaman, A., et al., A Four-Stage Algorithm for Community Detection Based on Label Propagation and Game Theory in Social Networks. AI, 2023. 4(1): p. 255-269.
25. Shang, R., et al., Local community detection algorithm based on alternating strategy of strong fusion and weak fusion. IEEE Transactions on Cybernetics, 2022.
26. Shang, R., et al., Local community detection based on higher-order structure and edge information. Physica A: Statistical Mechanics and its Applications, 2022. 587: p. 126513.
27. Wang, S., et al., A local community detection algorithm based on potential community exploration. Frontiers in Physics, 2023. 11: p. 58.
28. Zarei, B. and M.R. Meybodi, Detecting community structure in complex networks using genetic algorithm based on object migrating automata. Computational Intelligence, 2020. 36(2): p. 824-860.
29. Zarei, B., M.R. Meybodi, and B. Masoumi, Chaotic memetic algorithm and its application for detecting community structure in complex networks. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2020. 30(1).
30. Zarei, B., M.R. Meybodi, and B. Masoumi, Detecting community structure in signed and unsigned social networks by using weighted label propagation. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2020. 30(10).
31. Zarei, B., M.R. Meybodi, and B. Masoumi, A new evolutionary model based on cellular learning automata and chaos theory. New Generation Computing,
2022. 40(1): p. 285-310.
32. Leicht, E.A., P. Holme, and M.E. Newman, Vertex similarity in networks. Physical Review E, 2006. 73(2): p. 026120.
33. Rodriguez, A. and A. Laio, Clustering by fast search and find of density peaks. Science, 2014. 344(6191): p. 1492-1496.
34. Fortunato, S. and D. Hric, Community detection in networks: A user guide. Physics reports, 2016. 659: p. 1-44.
35. Lancichinetti, A., S. Fortunato, and F. Radicchi, Benchmark graphs for testing community detection algorithms. Physical review E, 2008. 78(4): p. 046110.
36. Zachary, W.W., An information flow model for conflict and fission in small groups. Journal of anthropological research, 1977. 33(4): p. 452-473.
37. Lusseau, D., et al., The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 2003. 54(4): p. 396-405.
38. (Unpublished)., V.K.h.w.o.c.
39. Watts, D.J. and S.H.J.n. Strogatz, Collective dynamics of ‘small-world’networks. 1998. 393(6684): p. 440-442.
40. Guimera, R., et al., Self-similar community structure in a network of human interactions. Physical review E, 2003. 68(6): p. 065103.
41. Newman, M.E., The structure of scientific collaboration networks. Proceedings of the national academy of sciences, 2001. 98(2): p. 404-409.
42. Boguná, M., et al., Models of social networks based on social distance attachment. Physical review E, 2004. 70(5): p. 056122.
43. Leskovec, J., J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. in Proceedings of the
eleventh ACM SIGKDD international conference on Knowledge discovery in data mining. 2005.
44. Yang, J. and J. Leskovec, Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 2015. 42(1): p. 181-213.
45. Lancichinetti, A. and S. Fortunato, Limits of modularity maximization in community detection. Physical review E, 2011. 84(6): p. 066122.
46. Amelio, A. and C. Pizzuti. Is normalized mutual information a fair measure for comparing community detection methods? in Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining 2015. 2015.
