Motivated by structural properties of the Web graph that support efficient data structures for in memory adjacency queries, we study the extent to which a large network can be compressed. Boldi and Vigna (WWW 2004), showed that Web graphs can be compressed down to three bits of storage per edge; we study the compressibility of social networks where again adjacency queries are a fundamental primitive. To this end, we propose simple combinatorial formulations that encapsulate efficient compressibility of graphs. We show that some of the problems are NP-hard yet admit effective heuristics, some of which can exploit properties of social networks such as link reciprocity. Our extensive experiments show that social networks and the Web graph exhibit vastly different compressibility characteristics. Copyright 2009 ACM.

On Compressing Social Networks / CHIERICHETTI, FLAVIO; RAVI, KUMAR; SILVIO, LATTANZI; MICHAEL, MITZENMACHER; PANCONESI, Alessandro; PRABHAKAR, RAGHAVAN. - (2009), pp. 219-227. (Intervento presentato al convegno ACM SIGKDD Conference On Knowledge Discovery and Data Mining (KDD 09) tenutosi a Paris; France nel 28 Giugno - 1 Luglio 2009) [10.1145/1557019.1557049].

On Compressing Social Networks

CHIERICHETTI, FLAVIO;PANCONESI, Alessandro;
2009

Abstract

Motivated by structural properties of the Web graph that support efficient data structures for in memory adjacency queries, we study the extent to which a large network can be compressed. Boldi and Vigna (WWW 2004), showed that Web graphs can be compressed down to three bits of storage per edge; we study the compressibility of social networks where again adjacency queries are a fundamental primitive. To this end, we propose simple combinatorial formulations that encapsulate efficient compressibility of graphs. We show that some of the problems are NP-hard yet admit effective heuristics, some of which can exploit properties of social networks such as link reciprocity. Our extensive experiments show that social networks and the Web graph exhibit vastly different compressibility characteristics. Copyright 2009 ACM.
2009
ACM SIGKDD Conference On Knowledge Discovery and Data Mining (KDD 09)
Compression; Linear arrangement; Reciprocity
Pubblicazione in atti di convegno::04b Atto di convegno in volume
On Compressing Social Networks / CHIERICHETTI, FLAVIO; RAVI, KUMAR; SILVIO, LATTANZI; MICHAEL, MITZENMACHER; PANCONESI, Alessandro; PRABHAKAR, RAGHAVAN. - (2009), pp. 219-227. (Intervento presentato al convegno ACM SIGKDD Conference On Knowledge Discovery and Data Mining (KDD 09) tenutosi a Paris; France nel 28 Giugno - 1 Luglio 2009) [10.1145/1557019.1557049].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

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/11573/194555
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 244
  • ???jsp.display-item.citation.isi??? 173
social impact