Discovering Communities in Networks: A Linear Programming Approach Using Max-Min Modularity

• Autorzy: Ferdowsi Arman , Khanteymoori Alireza

Identyfikatory

DOI

10.15439/2021F65

• Konferencja: Federated Conference on Computer Science and Information Systems (16 ; 02-05.09.2021 ; online)
• Języki publikacji: EN

Abstrakty

EN

Community detection is a fundamental challenge in network science and graph theory that aims to reveal nodes' structures. ‎While most methods consider Modularity as a community quality measure‎, ‎Max-Min Modularity improves the accuracy of the measure by penalizing the Modularity quantity when unrelated nodes are in the same community‎. ‎In this paper‎, ‎we propose a community detection approach based on linear programming using Max-Min Modularity‎. ‎The experimental results show that our algorithm has a better performance than the previously known algorithms on some well-known instances‎.

Słowa kluczowe

EN

complex networks; graph theory; linear programming; social networking

PL

złożone sieci; teoria grafów; Programowanie liniowe; sieć społecznościowa

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2021
• Tom: Vol. 25
• Strony: 329–--335
• Opis fizyczny: Bibliogr. 51 poz., wz., wykr.

Twórcy

autor

Ferdowsi Arman

• Vienna University of Technology Institute of Computer Engineering Embedded Computing Systems

autor

Khanteymoori Alireza

• University of Freiburg Department of Computer Science Bioinformatics Group

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. N. Tremblay and P. Borgnat, “Graph wavelets for multiscale community mining,” IEEE Transactions on Signal Processing, vol. 62, no. 20, pp. 5227–5239, 2014.
• 7. O. A. Linares, G. M. Botelho, F. A. Rodrigues, and J. B. Neto, “Segmentation of large images based on super-pixels and community detection in graphs,” IET Image Processing, vol. 11, no. 12, pp. 1219–1228, 2017.
• 8. L. M. Freitas and M. G. Carneiro, “Community detection to invariant pattern clustering in images,” in 2019 8th Brazilian Conference on Intelligent Systems (BRACIS). IEEE, 2019, pp. 610–615.
• 9. 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.
• 10. M. E. Newman, “Modularity and community structure in networks,” Proceedings of the national academy of sciences, vol. 103, no. 23, pp. 8577–8582, 2006.
• 11. U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner, “On modularity clustering,” IEEE transactions on knowledge and data engineering, vol. 20, no. 2, pp. 172–188, 2007.
• 12. P. Schuetz and A. Caflisch, “Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement,” Physical Review E, vol. 77, no. 4, p. 046112, 2008.
• 13. S. Cafieri, A. Costa, and P. Hansen, “Reformulation of a model for hierarchical divisive graph modularity maximization,” Annals of Operations Research, vol. 222, no. 1, pp. 213–226, 2014.
• 14. B. Rajita and S. Panda, “Community detection techniques for evolving social networks,” in 2019 9th International Conference on Cloud Computing, Data Science & Engineering (Confluence). IEEE, 2019, pp. 681–686.
• 15. A. Ferdowsi and A. Abhari, “Generating high-quality synthetic graphs for community detection in social networks,” in 2020 Spring Simulation Conference (SpringSim). IEEE, 2020, pp. 1–10.
• 16. R. Guimera and L. A. N. Amaral, “Functional cartography of complex metabolic networks,” nature, vol. 433, no. 7028, pp. 895–900, 2005.
• 17. D. Aloise, S. Cafieri, G. Caporossi, P. Hansen, S. Perron, and L. Liberti, “Column generation algorithms for exact modularity maximization in networks,” Physical Review E, vol. 82, no. 4, p. 046112, 2010.
• 18. G. Xu, S. Tsoka, and L. G. Papageorgiou, “Finding community structures in complex networks using mixed integer optimisation,” The European Physical Journal B, vol. 60, no. 2, pp. 231–239, 2007.
• 19. S. Fortunato and M. Barthelemy, “Resolution limit in community detection,” Proceedings of the national academy of sciences, vol. 104, no. 1, pp. 36–41, 2007.
• 20. 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.
• 21. 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.
• 22. J. Scripps, P.-N. Tan, and A.-H. Esfahanian, “Exploration of link structure and community-based node roles in network analysis,” in Seventh IEEE international conference on data mining (ICDM 2007). IEEE, 2007, pp. 649–654.
• 23. J. Duch and A. Arenas, “Community detection in complex networks using extremal optimization,” Physical review E, vol. 72, no. 2, p. 027104, 2005.
• 24. T. Richardson, P. J. Mucha, and M. A. Porter, “Spectral tripartitioning of networks,” Physical Review E, vol. 80, no. 3, p. 036111, 2009.
• 25. M. E. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical review E, vol. 69, no. 2, p. 026113, 2004.
• 26. V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of statistical mechanics: theory and experiment, vol. 2008, no. 10, p. P10008, 2008.
• 27. R. Guimera and L. A. N. Amaral, “Cartography of complex networks: modules and universal roles,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2005, no. 02, p. P02001, 2005.
• 28. S. Boccaletti, M. Ivanchenko, V. Latora, A. Pluchino, and A. Rapisarda, “Detecting complex network modularity by dynamical clustering,” Physical Review E, vol. 75, no. 4, p. 045102, 2007.
• 29. A. Tsitsulin, J. Palowitch, B. Perozzi, and E. Müller, “Graph clustering with graph neural networks,” arXiv preprint https://arxiv.org/abs/2006.16904, 2020.
• 30. C. Shi, Y. Liu, and P. Zhang, “Weighted community detection and data clustering using message passing,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2018, no. 3, p. 033405, 2018.
• 31. Y. Q. Niu, B. Q. Hu, W. Zhang, and M. Wang, “Detecting the community structure in complex networks based on quantum mechanics,” Physica A: Statistical Mechanics and Its Applications, vol. 387, no. 24, pp. 6215–6224, 2008.
• 32. G. Agarwal and D. Kempe, “Modularity-maximizing graph communities via mathematical programming,” The European Physical Journal B, vol. 66, no. 3, pp. 409–418, 2008.
• 33. 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.
• 34. A. Miyauchi and Y. Miyamoto, “Computing an upper bound of modularity,” The European Physical Journal B, vol. 86, no. 7, p. 302, 2013.
• 35. M. E. Newman, “Analysis of weighted networks,” Physical review E, vol. 70, no. 5, p. 056131, 2004.
• 36. A. Miyauchi and N. Sukegawa, “Redundant constraints in the standard formulation for the clique partitioning problem,” Optimization Letters, vol. 9, no. 1, pp. 199–207, 2015.
• 37. V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit, “Local search heuristics for k-median and facility location problems,” SIAM Journal on computing, vol. 33, no. 3, pp. 544–562, 2004.
• 38. A. Gupta and K. Tangwongsan, “Simpler analyses of local search algorithms for facility location,” arXiv preprint https://arxiv.org/abs/0809.2554, 2008.
• 39. 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.
• 40. J. Gil-Mendieta and S. Schmidt, “The political network in mexico,” Social Networks, vol. 18, no. 4, pp. 355–381, 1996.
• 41. 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.
• 42. 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.
• 43. 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.
• 44. 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.
• 45. N. Meghanathan, “A greedy algorithm for neighborhood overlap-based community detection,” Algorithms, vol. 9, no. 1, p. 8, 2016.
• 46. V. Batagelj and A. Mrvar, “Pajek datasets (2006),” 2009.
• 47. 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.
• 48. V. Batagelj and A. Mrvar, “Pajek.” 2014.
• 49. S. Chand and S. Mehta, “Community detection using nature inspired algorithm,” in Hybrid Intelligence for Social Networks. Springer, 2017, pp. 47–76.
• 50. 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.
• 51. B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” The Bell system technical journal, vol. 49, no. 2, pp. 291–307, 1970.

Uwagi

Track 3: Network Systems and Applications