Bi-objective model for community detection in weighted complex networks
Non overlap multiobjective k_core community detection
DOI:
https://doi.org/10.4108/eetinis.v11i4.4059Keywords:
complex networks, k_core, multi-objective, NSGAII, MOSAAbstract
In this study, we introduce an innovative approach that utilizes complex networks and the k_core method to address community detection in weighted networks. Our proposed bi-objective model aims to simultaneously discover non-overlapping communities while ensuring that the degree of similarity remains below a critical threshold to prevent network degradation. We leverage the k_core structure to detect tightly interconnected node groups, a concept particularly valuable in edge-weighted networks where different edge weights indicate the strength or importance of node relationships. Beyond maximizing the count of k_core communities, our model seeks a homogeneous weight distribution across edges within these communities, promoting stronger cohesion. To tackle this challenge, we implement two multi-target algorithms: Non-dominated Sorting Genetic Algorithm II (NSGAII) and a Multi-Objective Simulated Annealing (MOSA) algorithm. Both algorithms efficiently identify non-overlapping communities with a specified degree 'k'. The results of our experiments reveal a trade-off between maximizing the number of k_core communities and enhancing the homogeneity of these communities in terms of their minimum weighted interconnections. Notably, the MOSA algorithm outperforms NSGAII in both small and large instances, demonstrating its effectiveness in achieving this balance. This approach sheds light on effective strategies for resolving conflicting goals in community detection within weighted networks.
Downloads
References
[1] Newman, M. (2018) Networks (Oxford: university press). DOI: https://doi.org/10.1093/oso/9780198805090.001.0001
[2] Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Publ. math 5(1): 17–60.
[3] Watts, D.J. and Strogatz, S.H. (1998) Collective dynamics of ‘small-world’networks. nature 393(6684): 440–442. DOI: https://doi.org/10.1038/30918
[4] Barabási, A.L. and Albert, R. (1999) Emergence of scaling in random networks. science 286(5439): 509–512. DOI: https://doi.org/10.1126/science.286.5439.509
[5] Blondel, V.D., Guillaume, J.L., Lambiotte, R. and Lefebvre, E. (2008) Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008: 10.
[6] Borgatti, S.P., Mehra, A., Brass, D.J. and Labianca, G.(2009) Network analysis in the social sciences. science 323(5916): 892–895. DOI: https://doi.org/10.1126/science.1165821
[7] Fortunato, S. (2010) Community detection in graphs. Physics reports 486(3-5): 75–174. DOI: https://doi.org/10.1016/j.physrep.2009.11.002
[8] Krishnamurthy, B. and Wang, J.. August). In Proceedings, I. [ed.] On network-aware clustering of web clients (Technologies, Architectures, and Protocols for Computer Communication: of the conference on Applications): 97–110.
[9] Rossi, M.E.G., Malliaros, F.D. and Vazirgiannis, M.. May). In Spread it good (spread it fast: Identification of influential nodes in social networks. In Proceedings of the 24th International Conference on World Wide Web): 101–102.[10]
[10] Funk, S., Bansal, S., Bauch, C.T., Eames, K.T., Edmunds, W.J. Galvani, A.P. and Klepac, P. (2015) Nine challenges in incorporating the dynamics of behaviour in infectious diseases models. Epidemics 10: 21–25. DOI: https://doi.org/10.1016/j.epidem.2014.09.005
[11] Csermely, P. (2008) Creative elements: network-based predictions of active centres in proteins and cellular and social networks. Trends in biochemical sciences 33(12): 569–576. DOI: https://doi.org/10.1016/j.tibs.2008.09.006
[12] Seidman, S.B. (1983) Network structure and minimum degree. Social networks 5(3): 269–287. DOI: https://doi.org/10.1016/0378-8733(83)90028-X
[13] Girvan, M. and Newman, M.E. (2002) Community structure in social and biological networks. In Proceed-ings of the national academy of sciences (99(12): 7821–7826. DOI: https://doi.org/10.1073/pnas.122653799
[14] Clauset, A., Newman, M.E. and Moore, C. (2004) Finding community structure in very large networks. Physical review E 70(6): 066111. DOI: https://doi.org/10.1103/PhysRevE.70.066111
[15] Pons, P. and Latapy, M. (2005) Computing communi-ties in large networks using random walks. In Computer and Information Sciences-ISCIS 2005: 20th International Symposium, Istanbul, Turkey, October 26-28, 2005. Pro-ceedings 20 (Springer): 284–293. DOI: https://doi.org/10.1007/11569596_31
[16] Newman, M.E. (2006) Modularity and community structure in networks. Proceedings of the national academy of sciences 103(23): 8577–8582. DOI: https://doi.org/10.1073/pnas.0601602103
[17] Newman, M.E. (2016) Community detection in net-works: Modularity optimization and maximum likeli-hood are equivalent. arXiv preprint arXiv:1606.02319 .
[18] Duch, J. and Arenas, A. (2005) Community detection in complex networks using extremal optimization. Physical review E 72(2): 027104.
[19] Pizzuti, C. (2008) Ga-net: A genetic algorithm for community detection in social networks. In International conference on parallel problem solving from nature (Springer): 1081–1090. DOI: https://doi.org/10.1007/978-3-540-87700-4_107
[20] Sun, Y., Sun, X., Liu, Z., Cao, Y. and Yang, J. (2023) Core node knowledge based multi-objective particle swarm optimization for dynamic community detection. Computers & Industrial Engineering 175(10884): 3. DOI: https://doi.org/10.1016/j.cie.2022.108843
[21] Rossi, R.A. and Ahmed, N.K. (2014) Role discovery in networks. IEEE Transactions on Knowledge and Data Engineering 27(4): 1112–1131. DOI: https://doi.org/10.1109/TKDE.2014.2349913
[22] Henderson, K., Gallagher, B., Eliassi-Rad, T., Tong, H., Basu, S., Akoglu, L., Koutra, D. et al. (2012) Rolx: structural role extraction & mining in large graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining: 1231–1239. DOI: https://doi.org/10.1145/2339530.2339723
[23] Chen, W., Liu, Z., Sun, X. and Wang, Y. (2010) A game-theoretic framework to identify overlapping communities in social networks. Data Mining and Knowledge Discovery 21: 224–240. DOI: https://doi.org/10.1007/s10618-010-0186-6
[24] Song, X., Jiang, W., Liu, X., Lu, H., Tian, Z. and Du, X. (2020) A survey of game theory as applied to social networks. Tsinghua Science and Technology 25(6): 734–742. DOI: https://doi.org/10.26599/TST.2020.9010005
[25] Newman, M.E. (2013) Spectral methods for community detection and graph partitioning. Physical Review E 88(4): 042822. DOI: https://doi.org/10.1103/PhysRevE.88.042822
[26] Stephan, L. and Massoulié, L. (2019) Robustness of spectral methods for community detection. In Conference on Learning Theory (PMLR): 2831–2860.
[27] Newman, M.E. and Girvan, M. (2004) Finding and evaluating community structure in networks. Physical review E 69(2): 026113. DOI: https://doi.org/10.1103/PhysRevE.69.026113
[28] Guimera, R. and Nunes Amaral, L.A. (2005) Functional cartography of complex metabolic networks. nature 433(7028): 895–900. DOI: https://doi.org/10.1038/nature03288
[29] Shi, C., Yan, Z., Cai, Y. and Wu, B. (2012) Multi-objective community detection in complex networks. Applied Soft Computing 12(2): 850–859. DOI: https://doi.org/10.1016/j.asoc.2011.10.005
[30] Amiri, B., Hossain, L., Crawford, J.W. and Wigand, R.T. (2013) Community detection in complex networks: Multi–objective enhanced firefly algorithm. Knowledge-Based Systems 46: 1–11. DOI: https://doi.org/10.1016/j.knosys.2013.01.004
[31] Wen, X., Chen, W.N., Lin, Y., Gu, T., Zhang, H. and Li, Y. ... & zhang, j. (2016). a maximal clique based multiobjective evolutionary algorithm for overlapping community detection. IEEE Transactions on Evolutionary Computation 21(3): 363–377. DOI: https://doi.org/10.1109/TEVC.2016.2605501
[32] Tian, Y., Yang, S. and Zhang, X. (2019) An evolutionary multiobjective optimization based fuzzy method for overlapping community detection. IEEE Transactions on Fuzzy Systems 28(11): 2841–2855. DOI: https://doi.org/10.1109/TFUZZ.2019.2945241
[33] Bara’a, A.A., Abbood, A.D., Hasan, A.A., Pizzuti, C., Al-Ani, M., Özdemir, S. and Al-Dabbagh, R.D.(2021) A review of heuristics and metaheuristics for community detection in complex networks: Current usage, emerging development and future directions. Swarm and Evolutionary Computation 63: 100885. DOI: https://doi.org/10.1016/j.swevo.2021.100885
[34] Qing, H. (2023) Estimating the number of communities in weighted networks. Entropy 25(4): 551. DOI: https://doi.org/10.3390/e25040551
[35] Li, C. (2023) Multi-objective optimization overlapping community detection algorithm based on subgraph structure. Frontiers in Computing and Intelligent Systems 3(3): 110–112. DOI: https://doi.org/10.54097/fcis.v3i3.8580
[36] Zhu, W., Li, H. and Wei, W. (2023) A two-stage multi-objective evolutionary algorithm for community detection in complex networks. Mathematics 11(12): 2702. DOI: https://doi.org/10.3390/math11122702
[37] Zhang, L., Yang, H., Yang, S. and Zhang, X. (2023) A macro-micro population-based co-evolutionary multi-objective algorithm for community detection in complex networks [research frontier]. IEEE Computational Intelligence Magazine 18(3): 69–86. DOI: https://doi.org/10.1109/MCI.2023.3277773
[38] Das, I. and Dennis, J.E. (1997) A closer look at drawbacks of minimizing weighted sums of objectives for pareto set generation in multicriteria optimization problems. Structural optimization 14: 63–69. DOI: https://doi.org/10.1007/BF01197559
[39] Das, I. and Dennis, J.E. (1998) Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems. SIAM journal on optimization 8(3): 631–657. DOI: https://doi.org/10.1137/S1052623496307510
[40] Lancichinetti, A. and Fortunato, S. (2009) Bench-marks for testing community detection algorithms on directed and weighted graphs with overlapping com-munities. Physical Review E 80(1): 016118. DOI: https://doi.org/10.1103/PhysRevE.80.016118
[41] Lancichinetti, A., Fortunato, S. and Radicchi, F.(2008) Benchmark graphs for testing community detection algorithms. Physical review E 78(4): 046110. DOI: https://doi.org/10.1103/PhysRevE.78.046110
[42] García, C. and S., A. (2020) (On the Use of Scalarizing Functionsto Solve Many-ObjectiveOptimization Prob-lems= Uso de formulaciones para resolverproblemas de optimización conmuchos objetivos).
[43] Gupta, S.K. and Singh, D.P. (2023) Cbla: A clique based louvain algorithm for detecting overlapping community. Procedia Computer Science 218: 2201–2209. DOI: https://doi.org/10.1016/j.procs.2023.01.196
[44] Ferreira, L.N. and Zhao, L. (2015) A time series clustering technique based on community detection in networks. Procedia Computer Science 53: 183–190. DOI: https://doi.org/10.1016/j.procs.2015.07.293
[45] Gul, H., Al-Obeidat, F., Amin, A., Tahir, M. and Moreira, F. (2022) A systematic analysis of community detection in complex networks. Procedia Computer Science 201: 343–350.
[46] Blondel, V.D., Guillaume, J.L., Lambiotte, R. and Lefebvre, E. (2008) Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008: 10. DOI: https://doi.org/10.1088/1742-5468/2008/10/P10008
[47] Ding, J., Wang, T., Cheng, R., Jiao, L., Wu, J. and Bai, J. (2023) Community evolution prediction based on a self-adaptive timeframe in social networks. Knowledge-Based Systems 275(11068): 7. DOI: https://doi.org/10.1016/j.knosys.2023.110687
[48] Jia, G., Cai, Z., Musolesi, M., Wang, Y., Tennant, D.A. and Weber, R.J. (2012) ... & he, s. (2012). community detection in social and biological networks using differential evolution. In Learning and Intelligent Optimization: 6th International Conference, LION 6, Paris, France, January Revised Selected Papers (pp. 71-85). Heidelberg (Berlin: Springer), 16–20. DOI: https://doi.org/10.1007/978-3-642-34413-8_6
[49] Li, J.Y., Teng, J. and Wang, H. (2023) Integrating bipartite network modelling and overlapping commu-nity detection: A new method to evaluate transit line coordination. Physica A: Statistical Mechanics and its Applications 129169. DOI: https://doi.org/10.1016/j.physa.2023.129169
[50] Ghasemian, A., Hosseinmardi, H. and Clauset, A.(2019) Evaluating overfit and underfit in models of network community structure. IEEE Transactions on Knowledge and Data Engineering 32(9): 1722–1735. DOI: https://doi.org/10.1109/TKDE.2019.2911585
[51] Alotaibi, N. and Rhouma, D. (2022) A review on community structures detection in time evolving social networks. Journal of King Saud University-Computer and Information Sciences 34(8): 5646–5662. DOI: https://doi.org/10.1016/j.jksuci.2021.08.016
[52] Srivastava, V. and Biswas, B. (2023) An optimization based framework for region wise optimal clusters in mr images using hybrid objective. Neurocomputing 541(12628): 6. DOI: https://doi.org/10.1016/j.neucom.2023.126286
[53] Asmi, K. and Abarda, A. (2022) An efficient local algorithm for overlapping community detection in social networks. Procedia Computer Science 201: 789–794. DOI: https://doi.org/10.1016/j.procs.2022.03.108
[54] Atay, Y., Koc, I., Babaoglu, I. and Kodaz, H. (2017) Community detection from biological and social networks: A comparative analysis of metaheuristic algorithms. Applied Soft Computing 50: 194–211. DOI: https://doi.org/10.1016/j.asoc.2016.11.025
[55] Bai, M., Tan, Y., Wang, X., Zhu, B. and Li, G. (2021) Optimized algorithm for skyline community discovery in multi-valued networks. IEEE Access 9: 37574–37589. DOI: https://doi.org/10.1109/ACCESS.2021.3063317
[56] Berrou, Y. and Soulier, E. (2023) A methodology to analyze the development of local energy communities based on socio-energetic nodes and actor-network theory. Procedia Computer Science 219: 439–446. DOI: https://doi.org/10.1016/j.procs.2023.01.310
[57] Lusseau, D., Schneider, K., Boisseau, O.J., Haase, P., Slooten, E. and Dawson, S.M. (2003) The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: can geographic isolation explain this unique trait? Behavioral Ecology and Sociobiology 54: 396–405. DOI: https://doi.org/10.1007/s00265-003-0651-y
[58] Boudia, D.M., Haddad, M. and Benamar, A. (2023) Comparative study between quality measurement functions of a community distribution in a complex network. Procedia Computer Science 220: 632–638. DOI: https://doi.org/10.1016/j.procs.2023.03.080
[59] Cai, Q., Ma, L., Gong, M. and Tian, D. (2016) A survey on network community detection based on evolutionary computation. International Journal of Bio-Inspired Computation 8(2): 84–98. DOI: https://doi.org/10.1504/IJBIC.2016.076329
[60] Cerdá-Alabern, L., Iuhasz, G. and Gemmi, G. (2023) Anomaly detection for fault detection in wireless com-munity networks using machine learning. Computer Communications 202: 191–203. DOI: https://doi.org/10.1016/j.comcom.2023.02.019
[61] Chejara, P. and Godfrey, W.W.. (2017) November). comparative analysis of community detection algo-rithms. In InConference on Information and Communication Technology (CICT) (IEEE): 1–5. DOI: https://doi.org/10.1109/INFOCOMTECH.2017.8340627
[62] Jr, C., A., E. and Amancio, D.R. (2019) Word sense induction using word embeddings and community detection in complex networks. Physica A: Statistical Mechanics and its Applications 523: 180–190. DOI: https://doi.org/10.1016/j.physa.2019.02.032
[63] Costa, A.R. and Ralha, C.G. (2023) Ac2cd: An actor–critic architecture for community detection in dynamic social networks. Knowledge-Based Systems 261(11020): 2. DOI: https://doi.org/10.1016/j.knosys.2022.110202
[64] Duch, J. and Arenas, A. (2005) Community detection in complex networks using extremal optimization. Physical review E 72(2): 027104. DOI: https://doi.org/10.1103/PhysRevE.72.027104
[65] Ferreyra, N.E.D., Hecking, T., A"ımeur, E., Heisel, M. and Hoppe, H.U. (2022) Community detection for access-control decisions: Analysing the role of homophily and information diffusion in online social networks. Online Social Networks and Media 29(10020): 3. DOI: https://doi.org/10.1016/j.osnem.2022.100203
[66] Fortunato, S. and Hric, D. (2016) Community detection in networks: A user guide. Physics reports 659: 1–44. DOI: https://doi.org/10.1016/j.physrep.2016.09.002
[67] F., G. and A., D.J..F. (2022) A social network perspective on involvement in community energy initiatives: The role of direct and extended social ties to initiators. Energy Policy 171: 1132. DOI: https://doi.org/10.1016/j.enpol.2022.113260
[68] Gong, M., Ma, L., Zhang, Q. and Jiao, L. (2012) Com-munity detection in networks by using multiobjective evolutionary algorithm with decomposition. Physica A: Statistical Mechanics and its Applications 391(15): 4050–4060. DOI: https://doi.org/10.1016/j.physa.2012.03.021
[69] Gul, H., Al-Obeidat, F., Amin, A., Tahir, M. and Moreira, F. (2022) A systematic analysis of community detection in complex networks. Procedia Computer Science 201: 343–350. DOI: https://doi.org/10.1016/j.procs.2022.03.046
[70] Guo, W., Zhang, J., Sui, X., Hu, X., Lei, G. and Zhou, Y. ... & qi, l. (2022). Compartment niche and bamboo variety influence the diversity, composition, network and potential keystone taxa functions of rhizobacterial communities 24: 10059. DOI: https://doi.org/10.1016/j.rhisph.2022.100593
[71] Gupta, S. and Singh, D.P. (2020) Recent trends on community detection algorithms: A survey. Modern Physics Letters B 34(35): 2050408. DOI: https://doi.org/10.1142/S0217984920504084
[72] Gurov, A., Evmenova, E. and Chunaev, P. (2022) Supervised community detection in multiplex net-works based on layers convex flattening and modularity optimization. Procedia Computer Science 212: 181–190. DOI: https://doi.org/10.1016/j.procs.2022.11.002
Downloads
Published
How to Cite
Issue
Section
Categories
License
Copyright (c) 2024 EAI Endorsed Transactions on Industrial Networks and Intelligent Systems
This work is licensed under a Creative Commons Attribution 3.0 Unported License.
This is an open-access article distributed under the terms of the Creative Commons Attribution CC BY 3.0 license, which permits unlimited use, distribution, and reproduction in any medium so long as the original work is properly cited.
