Proceedings of the 18th Conference on Computer Science and Intelligence Systems

DOI: http://dx.doi.org/10.15439/2023F2832

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 111–117 (2023)

Full text

Abstract. ‎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‎.

References

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.