Toward an Optimal Solution to the Network Partitioning Problem

• Autorzy: Ferdowsi Arman , Chenary Maryam Dehghan

Identyfikatory

DOI

10.15439/2023F2832

• Języki publikacji: EN

Abstrakty

EN

This paper delves into the realm of community detection in network science and graph theory‎ ‎with the overarching objective of unraveling the underlying structures between nodes within a network‎. ‎In this pursuit‎, ‎we put forth a novel and comprehensive approach to ascertain the optimal solution to maximizing the renowned community quality metric known as Max-Min Modularity‎. ‎Through a series of experiments encompassing diverse case studies‎, ‎we substantiate the efficacy and validity of our proposed approach‎, ‎further bolstering its credibility‎.

Słowa kluczowe

EN

graph partitioning; community detection; mathematical programming; exact method

PL

podział grafu; detekcja społeczności; programowanie matematyczne; metoda dokładna

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 111--117
• Opis fizyczny: Bibliogr. 29 poz., wz., wykr.

Twórcy

autor

Ferdowsi Arman

• K. N. Toosi University of Technology Department of Mathematics

autor

Chenary Maryam Dehghan

• University of Vienna Institute of Business Decisions and Analytics

Bibliografia

• 1. L. Jiang, L. Shi, L. Liu, J. Yao, and M. A. Yousuf, “User interest community detection on social media using collaborative filtering,” Wireless Networks, pp. 1–7, 2019.
• 2. M. Wang, C. Wang, J. X. Yu, and J. Zhang, “Community detection in social networks: an in-depth benchmarking study with a procedure-oriented framework,” Proceedings of the VLDB Endowment, vol. 8, no. 10, pp. 998–1009, 2015.
• 3. Y. Atay, I. Koc, I. Babaoglu, and H. Kodaz, “Community detection from biological and social networks: A comparative analysis of metaheuristic algorithms,” Applied Soft Computing, vol. 50, pp. 194–211, 2017.
• 4. D. Krioukov, M. Kitsak, R. S. Sinkovits, D. Rideout, D. Meyer, and M. Boguñá, “Network cosmology,” Scientific reports, vol. 2, p. 793, 2012.
• 5. S. Aparicio, J. Villazón-Terrazas, and G. Álvarez, “A model for scale-free networks: application to twitter,” Entropy, vol. 17, no. 8, pp. 5848–5867, 2015.
• 6. P. Hui, E. Yoneki, S. Y. Chan, and J. Crowcroft, “Distributed community detection in delay tolerant networks,” in Proceedings of 2nd ACM/IEEE international workshop on Mobility in the evolving internet architecture, 2007, pp. 1–8.
• 7. N. Tremblay and P. Borgnat, “Graph wavelets for multiscale community mining,” IEEE Transactions on Signal Processing, vol. 62, no. 20, pp. 5227–5239, 2014.
• 8. F. D. Malliaros and M. Vazirgiannis, “Clustering and community detection in directed networks: A survey,” Physics Reports, vol. 533, no. 4, pp. 95–142, 2013.
• 9. T. Chakraborty, A. Dalmia, A. Mukherjee, and N. Ganguly, “Metrics for community analysis: A survey,” ACM Computing Surveys (CSUR), vol. 50, no. 4, pp. 1–37, 2017.
• 10. A. Ferdowsi, M. Dehghan Chenary, and A. Khanteymoori, “Tscda: a dynamic two-stage community discovery approach,” Social Network Analysis and Mining, vol. 12, no. 1, p. 46, 2022.
• 11. M. E. Newman, “Modularity and community structure in networks,” Proceedings of the national academy of sciences, vol. 103, no. 23, pp. 8577–8582, 2006.
• 12. A. Ferdowsi, “An integer programming approach reinforced by a message-passing procedure for detecting dense attributed subgraphs,” in 2022 17th Conference on Computer Science and Intelligence Systems (FedCSIS). IEEE, 2022, pp. 569–576.
• 13. J. Chen, O. R. Zaïane, and R. Goebel, “Detecting communities in social networks using max-min modularity,” in Proceedings of the 2009 SIAM international conference on data mining. SIAM, 2009, pp. 978–989.
• 14. A. Ferdowsi and A. Khanteymoori, “Discovering communities in networks: A linear programming approach using max-min modularity,” in 2021 16th Conference on Computer Science and Intelligence Systems (FedCSIS). IEEE, 2021, pp. 329–335.
• 15. T. N. Dinh and M. T. Thai, “Finding community structure with performance guarantees in complex networks,” arXiv preprint https://arxiv.org/abs/1108.4034, 2011.
• 16. A. Miyauchi and Y. Miyamoto, “Computing an upper bound of modularity,” The European Physical Journal B, vol. 86, no. 7, p. 302, 2013.
• 17. M. E. Newman, “Analysis of weighted networks,” Physical review E, vol. 70, no. 5, p. 056131, 2004.
• 18. W. W. Zachary, “An information flow model for conflict and fission in small groups,” Journal of anthropological research, vol. 33, no. 4, pp. 452–473, 1977.
• 19. J. Gil-Mendieta and S. Schmidt, “The political network in mexico,” Social Networks, vol. 18, no. 4, pp. 355–381, 1996.
• 20. D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, “The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations,” Behavioral Ecology and Sociobiology, vol. 54, no. 4, pp. 396–405, 2003.
• 21. R. Guimera, L. Danon, A. Diaz-Guilera, F. Giralt, and A. Arenas, “Self-similar community structure in a network of human interactions,” Physical review E, vol. 68, no. 6, p. 065103, 2003.
• 22. A. Mahajan and M. Kaur, “Various approaches of community detection in complex networks: a glance,” International Journal of Information Technology and Computer Science (IJITCS), vol. 8, no. 35, 2016.
• 23. M. Girvan and M. E. Newman, “Community structure in social and biological networks,” Proceedings of the national academy of sciences, vol. 99, no. 12, pp. 7821–7826, 2002.
• 24. N. Meghanathan, “A greedy algorithm for neighborhood overlap-based community detection,” Algorithms, vol. 9, no. 1, p. 8, 2016.
• 25. V. Batagelj and A. Mrvar, “Pajek datasets (2006),” 2009.
• 26. A. Cangelosi and D. Parisi, “A neural network model of caenorhabditis elegans: the circuit of touch sensitivity,” Neural processing letters, vol. 6, no. 3, pp. 91–98, 1997.
• 27. A. Mrvar and V. Batagelj, Pajek: Programs for Analysis and Visualization of Very Large Networks: Reference Manual: List of Commands with Short Explanation Version 5.10. A. Mrvar, 2020.
• 28. S. Chand and S. Mehta, “Community detection using nature inspired algorithm,” in Hybrid Intelligence for Social Networks. Springer, 2017, pp. 47–76.
• 29. L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas, “Comparing community structure identification,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2005, no. 09, p. P09008, 2005.

Uwagi

1. Main Track Regular Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).