Logo PTI Logo FedCSIS

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

Annals of Computer Science and Information Systems, Volume 25

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

,

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 ()

Full text

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

  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.