Given a graph and a set of query vertices, the community-search problem requires to find a connected subgraph that contains all query vertices and maximizes the minimum degree. For this problem many different optimal solution subgraphs (of very different size) may exist. In this thesis we highlight, for the first time, a major drawback of the state-of-the-art methods for community search: they all tend to return solutions with extremely large number of vertices, so large that they are useless in most applications. In order to overcome this limitation, we propose a general framework based on the core decomposition of the input graph, which is precomputed once, and stored in a clever way to allow efficient retrieval. At query time, we retrieve, from the precomputed information, a subgraph that defines the search space where to build the final solution. We instantiate this general framework with two different ways of organizing the core decomposition (one is more compact, while the other one offers more efficient retrieval), and two heuristics for the final phase (one faster, while the other one more accurate). Extensive experiments on large real-world graphs confirm that our methods are more efficient than the state-of-the-art methods and produce communities that are much more cohesive: smaller in size and denser.

Dato un grafo e un insieme di nodi query, il problema di community-search richiede di trovare un sottografo connesso che contiene tutti i nodi query e massimizza il minimo grado. Per questo problema possono esistere molteplici sottografi (di dimensioni molto differenti) che risolvono il problema in maniera ottimale. In questa tesi evidenziamo, per la prima volta, un importante limite dei metodi di community search presenti allo stato dell'arte: tendono tutti a restituire soluzioni con un elevato numero di nodi, così elevato da risultare inutili nella maggior parte delle applicazioni. Per superare questa limitazione, proponiamo un framework basato sulla core decomposition del grafo in input, che è precalcolata una volta e salvata in modo intelligente in modo tale da consentire un efficiente recupero dell'informazione. In fase di query, recuperiamo, dall'informazione precalcolata, un sottografo che definisce lo spazio di ricerca in cui cercare la soluzione finale. Questo framework presenta due differenti modi di organizzare la core decomposition (uno è più compatto, mentre l'altro offre un recupero dell'informazione più efficiente) e due euristiche per la fase finale (una più veloce e una più accurata). Approfonditi esperimenti su grafi di elevate dimensioni confermano che i nostri metodi sono più efficienti di quelli presenti allo stato dell'arte e producono comunità che sono molto più coese: più piccole per dimensione e più dense.

Denser, smaller, faster community search

GALIMBERTI, EDOARDO
2013/2014

Abstract

Given a graph and a set of query vertices, the community-search problem requires to find a connected subgraph that contains all query vertices and maximizes the minimum degree. For this problem many different optimal solution subgraphs (of very different size) may exist. In this thesis we highlight, for the first time, a major drawback of the state-of-the-art methods for community search: they all tend to return solutions with extremely large number of vertices, so large that they are useless in most applications. In order to overcome this limitation, we propose a general framework based on the core decomposition of the input graph, which is precomputed once, and stored in a clever way to allow efficient retrieval. At query time, we retrieve, from the precomputed information, a subgraph that defines the search space where to build the final solution. We instantiate this general framework with two different ways of organizing the core decomposition (one is more compact, while the other one offers more efficient retrieval), and two heuristics for the final phase (one faster, while the other one more accurate). Extensive experiments on large real-world graphs confirm that our methods are more efficient than the state-of-the-art methods and produce communities that are much more cohesive: smaller in size and denser.
BONCHI, FRANCESCO
ING - Scuola di Ingegneria Industriale e dell'Informazione
3-ott-2014
2013/2014
Dato un grafo e un insieme di nodi query, il problema di community-search richiede di trovare un sottografo connesso che contiene tutti i nodi query e massimizza il minimo grado. Per questo problema possono esistere molteplici sottografi (di dimensioni molto differenti) che risolvono il problema in maniera ottimale. In questa tesi evidenziamo, per la prima volta, un importante limite dei metodi di community search presenti allo stato dell'arte: tendono tutti a restituire soluzioni con un elevato numero di nodi, così elevato da risultare inutili nella maggior parte delle applicazioni. Per superare questa limitazione, proponiamo un framework basato sulla core decomposition del grafo in input, che è precalcolata una volta e salvata in modo intelligente in modo tale da consentire un efficiente recupero dell'informazione. In fase di query, recuperiamo, dall'informazione precalcolata, un sottografo che definisce lo spazio di ricerca in cui cercare la soluzione finale. Questo framework presenta due differenti modi di organizzare la core decomposition (uno è più compatto, mentre l'altro offre un recupero dell'informazione più efficiente) e due euristiche per la fase finale (una più veloce e una più accurata). Approfonditi esperimenti su grafi di elevate dimensioni confermano che i nostri metodi sono più efficienti di quelli presenti allo stato dell'arte e producono comunità che sono molto più coese: più piccole per dimensione e più dense.
Tesi di laurea Magistrale
File allegati
File Dimensione Formato  
2014_10_Galimberti.pdf

non accessibile

Descrizione: Testo della tesi
Dimensione 1.1 MB
Formato Adobe PDF
1.1 MB Adobe PDF   Visualizza/Apri

I documenti in POLITesi 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/10589/97821