2009 OnCompressingSocialNetworks

• (Chierichetti et al., 2009) ⇒ Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Panconesi, and Prabhakar Raghavan. (2009). “On Compressing Social Networks.” In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2009). doi:10.1145/1557019.1557049

Subject Headings:

Notes

• Categories and Subject Descriptors: H.2.8 Information Systems: Database Applications — Data Mining; G.2.2 Mathematics of Computing: Graph Theory — Graph algorithms
• General Terms: Algorithms, Experimentation, Measurement, Theory

Cited By

• http://scholar.google.com/scholar?q=%22On+compressing+social+networks%22+2009
• http://portal.acm.org/citation.cfm?doid=1557019.1557049&preflayout=flat#citedby

Quotes

Author Keywords

Compression, Social Networks, Linear Arrangement, Reciprocity

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 graph 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.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 OnCompressingSocialNetworks	Flavio Chierichetti Prabhakar Raghavan Michael Mitzenmacher Alessandro Panconesi Ravi Kumar Silvio Lattanzi			On Compressing Social Networks		KDD-2009 Proceedings		10.1145/1557019.1557049		2009