Community detection in graphs aims at identifying modules within a network and, possibly, their hierarchical organization by only using the information encoded in the graph modeling the network. Generally speaking, a community in a network is a subset of its nodes showing higher degree of interconnection with each other than to the remaining nodes. This is an informal characterization and different formal definitions of communities have been proposed in the literature, also in relation to the available information. For most such definitions, the problem of detecting a proper partition of the given network into a prefixed number of community is NP-hard.In this paper, we consider the case in which a weight is associated to each edge of the graph, measuring the amount of interconnection between the corresponding pair of nodes. Under this hypothesis, we introduce and explore a new definition of community, that is, min-max communities, to model highly connected sets of nodes: a min-max community is a set of vertices such that the weakest (minimal) relation inside the community is stronger than the strongest (maximal) relation outside. By analyzing the structural properties induced by this definition, we prove that the problem of partitioning a complete weighted graph into k>. 0 communities is tractable. We also show that a slight modification to this framework results into an NP-complete problem.

Di Ianni, M., Gambosi, G., Rossi, G., & Vocca, P. (2016). Min-max communities in graphs: Complexity and computational properties. THEORETICAL COMPUTER SCIENCE, 613, 94-114 [10.1016/j.tcs.2015.11.034].

Min-max communities in graphs: Complexity and computational properties

DI IANNI, MIRIAM;GAMBOSI, GIORGIO;ROSSI, GIANLUCA;VOCCA, PAOLA
2016

Abstract

Community detection in graphs aims at identifying modules within a network and, possibly, their hierarchical organization by only using the information encoded in the graph modeling the network. Generally speaking, a community in a network is a subset of its nodes showing higher degree of interconnection with each other than to the remaining nodes. This is an informal characterization and different formal definitions of communities have been proposed in the literature, also in relation to the available information. For most such definitions, the problem of detecting a proper partition of the given network into a prefixed number of community is NP-hard.In this paper, we consider the case in which a weight is associated to each edge of the graph, measuring the amount of interconnection between the corresponding pair of nodes. Under this hypothesis, we introduce and explore a new definition of community, that is, min-max communities, to model highly connected sets of nodes: a min-max community is a set of vertices such that the weakest (minimal) relation inside the community is stronger than the strongest (maximal) relation outside. By analyzing the structural properties induced by this definition, we prove that the problem of partitioning a complete weighted graph into k>. 0 communities is tractable. We also show that a slight modification to this framework results into an NP-complete problem.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - Informatica
English
Community discovery; Graph partitioning; Graph theory; Theoretical Computer Science; Computer Science (all)
http://www.journals.elsevier.com/theoretical-computer-science/
Di Ianni, M., Gambosi, G., Rossi, G., & Vocca, P. (2016). Min-max communities in graphs: Complexity and computational properties. THEORETICAL COMPUTER SCIENCE, 613, 94-114 [10.1016/j.tcs.2015.11.034].
DI IANNI, M; Gambosi, G; Rossi, G; Vocca, P
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
communities2ndRevision.pdf

non disponibili

Descrizione: Articolo principale
Licenza: Non specificato
Dimensione 452.24 kB
Formato Adobe PDF
452.24 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: http://hdl.handle.net/2108/185795
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact