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

### Arman Ferdowsi, Alireza Khanteymoori

DOI: http://dx.doi.org/10.15439/2021F65

Citation: Proceedings of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 25, pages 329–335 (2021)

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

### References

- 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.
- 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.
- 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.
- D. Krioukov, M. Kitsak, R. S. Sinkovits, D. Rideout, D. Meyer, and M. Boguñá, “Network cosmology,” Scientific reports, vol. 2, p. 793, 2012.
- 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.
- N. Tremblay and P. Borgnat, “Graph wavelets for multiscale community mining,” IEEE Transactions on Signal Processing, vol. 62, no. 20, pp. 5227–5239, 2014.
- 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.
- 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.
- 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.
- M. E. Newman, “Modularity and community structure in networks,” Proceedings of the national academy of sciences, vol. 103, no. 23, pp. 8577–8582, 2006.
- 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.
- 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.
- 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.
- 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.
- 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.
- R. Guimera and L. A. N. Amaral, “Functional cartography of complex metabolic networks,” nature, vol. 433, no. 7028, pp. 895–900, 2005.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- J. Duch and A. Arenas, “Community detection in complex networks using extremal optimization,” Physical review E, vol. 72, no. 2, p. 027104, 2005.
- T. Richardson, P. J. Mucha, and M. A. Porter, “Spectral tripartitioning of networks,” Physical Review E, vol. 80, no. 3, p. 036111, 2009.
- M. E. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical review E, vol. 69, no. 2, p. 026113, 2004.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- A. Miyauchi and Y. Miyamoto, “Computing an upper bound of modularity,” The European Physical Journal B, vol. 86, no. 7, p. 302, 2013.
- M. E. Newman, “Analysis of weighted networks,” Physical review E, vol. 70, no. 5, p. 056131, 2004.
- 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.
- 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.
- A. Gupta and K. Tangwongsan, “Simpler analyses of local search algorithms for facility location,” arXiv preprint https://arxiv.org/abs/0809.2554, 2008.
- 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.
- J. Gil-Mendieta and S. Schmidt, “The political network in mexico,” Social Networks, vol. 18, no. 4, pp. 355–381, 1996.
- 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.
- 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.
- 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.
- 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.
- N. Meghanathan, “A greedy algorithm for neighborhood overlap-based community detection,” Algorithms, vol. 9, no. 1, p. 8, 2016.
- V. Batagelj and A. Mrvar, “Pajek datasets (2006),” 2009.
- 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.
- V. Batagelj and A. Mrvar, “Pajek.” 2014.
- S. Chand and S. Mehta, “Community detection using nature inspired algorithm,” in Hybrid Intelligence for Social Networks. Springer, 2017, pp. 47–76.
- 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.
- 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.