Random graph generator for leader and community detection in networks
Francisco J. Matos-Junior
Departamento de Estatística, CASTLab, Universidade Federal de Pernambuco, Cidade Universitária, Recife/PE, 50740-540 Brazil
Search for more papers by this authorCorresponding Author
Raydonal Ospina
Departamento de Estatística, CASTLab, Universidade Federal de Pernambuco, Cidade Universitária, Recife/PE, 50740-540 Brazil
Corresponding Author.
Search for more papers by this authorGeiza Silva
Departamento de Estatística, CASTLab, Universidade Federal de Pernambuco, Cidade Universitária, Recife/PE, 50740-540 Brazil
Universidade Federal do ABC, Centro de Matemática, Computação e Cognição, Av. dos Estados 5001, St André, SP, 09210-580 Brazil
Search for more papers by this authorFrancisco J. Matos-Junior
Departamento de Estatística, CASTLab, Universidade Federal de Pernambuco, Cidade Universitária, Recife/PE, 50740-540 Brazil
Search for more papers by this authorCorresponding Author
Raydonal Ospina
Departamento de Estatística, CASTLab, Universidade Federal de Pernambuco, Cidade Universitária, Recife/PE, 50740-540 Brazil
Corresponding Author.
Search for more papers by this authorGeiza Silva
Departamento de Estatística, CASTLab, Universidade Federal de Pernambuco, Cidade Universitária, Recife/PE, 50740-540 Brazil
Universidade Federal do ABC, Centro de Matemática, Computação e Cognição, Av. dos Estados 5001, St André, SP, 09210-580 Brazil
Search for more papers by this authorAbstract
In complex network analyses, mainly in social networks, the detection of communities is an important source of information for revealing an internal organization of nodes. On the other hand, if the network reveals a leadership structure, it is possible to understand the mechanisms of information dissemination on it. The detection of leaders and communities is a big challenge depending on the complexity level of the network. In the literature, there are some metaheuristic algorithms for detecting leaders and communities based on pattern recognition on the graph associated with the network. In this paper, we developed a random graph system to generate a synthetic network instance with leader and community structures that define a ground truth. We compare this ground truth to determine the performance of the algorithms LCDA 1 and LCDA 2 for detecting leaders and communities. The results corroborate that the benchmarking system would help in selecting useful configurations for practical applications.
References
- Ahajjam, S., Badir, H., 2022. Community detection in social networks. In A. Biswas, R. Patgiri, B. Biswas (eds) Principles of Social Networking. Springer, Singapore, pp. 91–107.
10.1007/978-981-16-3398-0_5 Google Scholar
- Ahajjam, S., Badir, H., El Haddad, M., 2015a. Towards a new approach for community detection algorithm in social networks. In International Conference in Big Data, Cloud and Applications, Tétouan, Morocco, pp. 23–28.
- Ahajjam, S., El Haddad, M., Badir, H., 2015b. LeadersRank: Towards a new approach for community detection in social networks. In 2015 IEEE/ACS 12th International Conference of Computer Systems and Applications (AICCSA), IEEE, Piscataway, NJ, pp. 1–8.
- Ahajjam, S., El Haddad, M., Badir, H., 2018. A new scalable leader-community detection approach for community detection in social networks. Social Networks 54, 41–49.
- Albert, R., Jeong, H., Barabási, A.L., 2000. Error and attack tolerance of complex networks. Nature 406, 6794, 378.
- Alcalá-Corona, S.A., Velázquez-Caldelas, T.E., Espinal-Enríquez, J., Hernández-Lemus, E., 2016. Community structure reveals biologically functional modules in mef2c transcriptional regulatory network. Frontiers in Physiology 7, 184.
- Alessandro, V., Guido, C., 2007. Large Scale Structure and Dynamics of Complex Networks: From Information Technology to Finance and Natural Science, Vol. 2. World Scientific, Singapore.
- Atay, Y., Koc, I., Babaoglu, I., Kodaz, H., 2017. Community detection from biological and social networks: A comparative analysis of metaheuristic algorithms. Applied Soft Computing 50, 194–211.
- Barabási, A.L., Bonabeau, E., 2003. Scale-free networks. Scientific American 288, 5, 60–69.
- Bliss, C.A., Frank, M.R., Danforth, C.M., Dodds, P.S., 2014. An evolutionary algorithm approach to link prediction in dynamic social networks. Journal of Computational Science 5, 5, 750–764.
- Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E., 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 10, P10008.
- Bonacich, P., Lloyd, P., 2001. Eigenvector-like measures of centrality for asymmetric relations. Social Networks 23, 3, 191–201.
- Broido, A.D., Clauset, A., 2019. Scale-free networks are rare. Nature Communications 10, 1, 1–10.
- Chakrabarti, D., Zhan, Y., Faloutsos, C., 2004. R-MAT: a recursive model for graph mining. In Proceedings of the 2004 SIAM International Conference on Data Mining, SIAM, Philadelphia, PA, pp. 442–446.
- Clauset, A., Newman, M.E., Moore, C., 2004. Finding community structure in very large networks. Physical Review E 70, 6, 066111.
- Clauset, A., Shalizi, C.R., Newman, M.E., 2009. Power-law distributions in empirical data. SIAM Review 51, 4, 661–703.
- Cohen, R., Erez, K., Ben-Avraham, D., Havlin, S., 2000. Resilience of the internet to random breakdowns. Physical Review Letters 85, 21, 4626.
- Faust, K., Wasserman, S., 1992. Blockmodels: interpretation and evaluation. Social Networks 14, 1–2, 5–61.
- Funke, D., Lamm, S., Sanders, P., Schultz, C., Strash, D., von Looz, M., 2018. Communication-free massively distributed graph generation. In IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, Piscataway, NJ, pp. 336–347.
- Girvan, M., Newman, M.E., 2002. Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 12, 7821–7826.
- Guimera, R., Danon, L., Diaz-Guilera, A., Giralt, F., Arenas, A., 2003. Self-similar community structure in a network of human interactions. Physical Review E 68, 6, 065103.
- Kamiński, B., Prałat, P., Théberge, F., 2021. Artificial benchmark for community detection (abcd)–fast random graph model with community structure. Network Science 9, 2, 153–178.
- Lancichinetti, A., Fortunato, S., Kertesz, J., 2009. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics 11, 3, 033015.
- Lancichinetti, A., Fortunato, S., Radicchi, F., 2008. Benchmark graphs for testing community detection algorithms. Physical Review E 78, 4, 046110.
- Largeron, C., Mougel, P.N., Rabbany, R., Zaïane, O.R., 2015. Generating attributed networks with communities. PLoS One 10, 4, e0122777.
- Lee, C., Wilkinson, D.J., 2019. A review of stochastic block models and extensions for graph clustering. Applied Network Science 4, 1, 1–50.
10.1007/s41109-019-0232-2 Google Scholar
- Levorato, V., Petermann, C., 2011. Detection of communities in directed networks based on strongly p-connected components. In 2011 IEEE International Conference on Computational Aspects of Social Networks (CASoN), IEEE, Piscataway, NJ, pp. 211–216.
- Liu, X., Cheng, H.M., Zhang, Z.Y., 2019. Evaluation of community detection methods. IEEE Transactions on Knowledge and Data Engineering 32, 9, 1736–1746.
- Lu, D.D., 2021. Leader-based community detection algorithm in attributed networks. IEEE Access 9, 119666–119674.
- Malhotra, D., Chug, A., 2021. A modified label propagation algorithm for community detection in attributed networks. International Journal of Information Management Data Insights 1, 2, 100030.
10.1016/j.jjimei.2021.100030 Google Scholar
- Mester, A., Pop, A., Mursa, B.E.M., Greblă, H., Dioşan, L., Chira, C., et al.2021. Network analysis based on important node selection and community detection. Mathematics 9, 18, 2294.
- Newman, M.E., 2003. The structure and function of complex networks. SIAM Review 45, 2, 167–256.
- Palla, G., Derényi, I., Farkas, I., Vicsek, T., 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 7043, 814.
- Pastor-Satorras, R., Vespignani, A., 2001. Epidemic spreading in scale-free networks. Physical Review Letters 86, 14, 3200.
- Prokhorenkova, L.O., Prałat, P., Raigorodskii, A., 2017. Modularity of complex networks models. Internet Mathematics, Preprint arXiv:1701.03141.
- R Core Team, 2018. R: a language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria.
- Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D., 2004. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences 101, 9, 2658–2663.
- Serafino, M., Cimini, G., Maritan, A., Rinaldo, A., Suweis, S., Banavar, J.R., Caldarelli, G., 2021. True scale-free networks hidden by finite size effects. Proceedings of the National Academy of Sciences 118, 2, e2013825118.
- Seshadhri, C., Kolda, T.G., Pinar, A., 2012. Community structure and scale-free collections of erdös-rényi graphs. Physical Review E 85, 056109.
- Slota, G.M., Berry, J.W., Hammond, S.D., Olivier, S.L., Phillips, C.A., Rajamanickam, S., 2019. Scalable generation of graphs for benchmarking HPC community-detection algorithms. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1–14.
- Traag, V.A., Waltman, L., Van Eck, N.J., 2019. From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports 9, 1, 1–12.
- Wang, Y., Di, Z., Fan, Y., 2011. Detecting important nodes to community structure using the spectrum of the graph. PLoS One 6, 11.
- Xia, Y., Ren, X., Peng, Z., Zhang, J., She, L., 2016. Effectively identifying the influential spreaders in large-scale social networks. Multimedia Tools and Applications 75, 15, 8829–8841.
