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.

Overlapping communities detection through weighted graph community games / Benati, Stefano; Puerto, Justo; Rodríguez-Chía, Antonio M.; Temprano, Francisco. - In: PLOS ONE. - ISSN 1932-6203. - STAMPA. - 18:4(2023). [10.1371/journal.pone.0283857]

Overlapping communities detection through weighted graph community games

Benati, Stefano
Primo
;
2023-01-01

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.
2023
4
Benati, Stefano; Puerto, Justo; Rodríguez-Chía, Antonio M.; Temprano, Francisco
Overlapping communities detection through weighted graph community games / Benati, Stefano; Puerto, Justo; Rodríguez-Chía, Antonio M.; Temprano, Francisco. - In: PLOS ONE. - ISSN 1932-6203. - STAMPA. - 18:4(2023). [10.1371/journal.pone.0283857]
File in questo prodotto:
File Dimensione Formato  
Temprano_CommunityThroughGraphGames.pdf

accesso aperto

Descrizione: articolo
Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Creative commons
Dimensione 3.06 MB
Formato Adobe PDF
3.06 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/395729
Citazioni
  • ???jsp.display-item.citation.pmc??? 0
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact