Overlapping communities detection through weighted graph community games

Stefano Benati; Justo Puerto; Antonio M Rodríguez-Chía; Francisco Temprano

doi:10.1371/journal.pone.0283857

Overlapping communities detection through weighted graph community games

PLoS One. 2023 Apr 4;18(4):e0283857. doi: 10.1371/journal.pone.0283857. eCollection 2023.

Authors

Stefano Benati¹, Justo Puerto², Antonio M Rodríguez-Chía³, Francisco Temprano²

Affiliations

¹ Dipartimento di Sociologia e Ricerca Sociale, Università di Trento, Trento, Italy.
² IMUS, Universidad de Sevilla, Sevilla, Spain.
³ Faculty of Sciences, Universidad de Cádiz, Puerto Real (Cádiz), Spain.

Abstract

We propose a new model to detect the overlapping communities of a network that is based on cooperative games and mathematical programming. More specifically, communities are defined as stable coalitions of a weighted graph community game and they are revealed as the optimal solution of a mixed-integer linear programming problem. Exact optimal solutions are obtained for small and medium sized instances and it is shown that they provide useful information about the network structure, improving on previous contributions. Next, a heuristic algorithm is developed to solve the largest instances and used to compare two variations of the objective function.

Copyright: © 2023 Benati et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms*
Heuristics
Programming, Linear*

Grants and funding

The authors of this research Stefano Benati, Antonio Manuel Rodríguez-Chía, Justo Puerto and Francisco Temprano acknowledge financial support by the Spanish Ministerio de Ciencia y Tecnología, Agencia Estatal de Investigación and Fondos Europeos de Desarrollo Regional (FEDER) with grant number: PID2020-114594GB-C21, and Junta de Andalucía with grant number: P18-FR-1422. The authors Stefano Benati, Antonio Manuel Rodríguez-Chía and Justo Puerto also acknowledge partial support from: NetmeetData: Ayudas Fundación BBVA a equipos de investigación científica 2019 with reference "COMPLEX NETWORK". The author Antonio Manuel Rodríguez-Chía also acknowledges the European Regional Development Fund via projects with grant numbers: FEDER-UCA18-106895 and TED2021-130875B-I00; and the Spanish Ministerio de Ciencia y Tecnología, Agencia Estatal de Investigación with grant number: PID2020-114594GB-C22. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.