Name
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 fundamen- tal primitive. To this end, we propose simple combinatorial for- mulations 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1557019.1557049 | KDD |
Keywords | Field | DocType |
web graph,efficient compressibility,social networks,adjacency query,effective heuristics,linear arrangement,social network,efficient data structure,different compressibility characteristic,memory adjacency query,extensive experiment,compression,web graph exhibit,data structure,reciprocity | Compressibility,Adjacency list,Data mining,Social network,Computer science,Theoretical computer science,Heuristics,Complex network,Artificial intelligence,Data structure,Evolving networks,Exploit,Machine learning | Conference |
Citations | PageRank | References |
105 | 4.17 | 22 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Flavio Chierichetti | 1 | 626 | 39.42 |
| Ravi Kumar | 2 | 13932 | 1642.48 |
| Silvio Lattanzi | 3 | 720 | 46.77 |
| Michael Mitzenmacher | 4 | 7386 | 730.89 |
| Alessandro Panconesi | 5 | 1584 | 124.00 |
| Prabhakar Raghavan | 6 | 13351 | 2776.61 |