On compressing social networks

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.

REFERENCES

• 1: Micah Adler , Michael Mitzenmacher, Towards Compressing Web Graphs, Proceedings of the Data Compression Conference, p.203, March 27-29, 2001
• 2: R. Albert and A.-L. Barabasi. Emergence of scaling in random networks. Science, 286:509--512, 1999.
• 3: Christoph Ambuhl , Monaldo Mastrolilli , Ola Svensson, Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.329-337, October 21-23, 2007 [doi>10.1109/FOCS.2007.32]
• 4: Dan Blandford , Guy Blelloch, Index Compression through Document Reordering, Proceedings of the Data Compression Conference, p.342, April 02-04, 2002
• 5: Paolo Boldi , Massimo Santini , Sebastiano Vigna, Permuting Web Graphs, Proceedings of the 6th International Workshop on Algorithms and Models for the Web-Graph, February 12-13, 2009, Barcelona, Spain [doi>10.1007/978-3-540-95995-3_10]
• 6: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 7: Paolo Boldi , Sebastiano Vigna, The WebGraph Framework II: Codes For The World-Wide Web, Proceedings of the Conference on Data Compression, p.528, March 23-25, 2004
• 8: B. Bollobas and O. Riordan. Mathematical results on scale-free random graphs. In S. Bornholdt and H. Schuster, editors, Handbook of Graphs and Networks, pages 1--37. Wiley-WCH, 2002.
• 9: Béla Bollobás , Oliver Riordan , Joel Spencer , Gábor Tusnády, The degree sequence of a scale-free random graph process, Random Structures & Algorithms, v.18 n.3, p.279-290, May 2001 [doi>10.1002/rsa.1009]
• 10: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 11: Gregory Buehrer , Kumar Chellapilla, A scalable pattern mining approach to web graph compression with communities, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341547]
• 12: A. Flaxman, A. M. Frieze, and T. I. Fenner. High degree vertices and eigenvalues in the preferential attachment graph. Internet Mathematics, 2(1), 2005.
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. TCS, pages 237--267, 1976.
• 15: David Gibson , Ravi Kumar , Andrew Tomkins, Discovering large dense subgraphs in massive graphs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 16: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 17: Ravi Kumar , Jasmine Novak , Andrew Tomkins, Structure and evolution of online social networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150476]
• 18: D. Liben-Nowell, J. Novak, R. Kumar, P. Raghavan, and A. Tomkins. Geographic routing in social networks. PNAS, 102(33):11623--11628, 2005.
• 19: Christopher D. Manning , Prabhakar Raghavan , Hinrich Schtze, Introduction to Information Retrieval, Cambridge University Press, New York, NY, 2008
• 20: Colin McDiarmid, Concentration for Independent Permutations, Combinatorics, Probability and Computing, v.11 n.2, p.163-178, March 2002 [doi>10.1017/S0963548301005089]
• 21: S. Raghavan and H. Garcia-Molina. Representing web graphs. In Proc. 19th ICDE, pages 405--416, 2003.
• 22: Keith H. Randall , Raymie Stata , Janet L. Wiener , Rajiv G. Wickremesinghe, The Link Database: Fast Access to Graphs of the Web, Proceedings of the Data Compression Conference, p.122, April 02-04, 2002
• 23: Satish Rao , Andréa W. Richa, New Approximation Techniques for Some Linear Ordering Problems, SIAM Journal on Computing, v.34 n.2, p.388-404, 2005 [doi>10.1137/S0097539702413197]
• 24: Wann-Yun Shieh , Tien-Fu Chen , Jean Jyh-Jiun Shann , Chung-Ping Chung, Inverted file compression through document identifier reassignment, Information Processing and Management: an International Journal, v.39 n.1, p.117-131, January 2003 [doi>10.1016/S0306-4573(02)00020-1]
• 25: F. Silvestri. Sorting out the document identifier assignment problem. In Proc. 29th ECIR, pages 101--112, 2007.
• 26: Fabrizio Silvestri , Raffaele Perego , Salvatore Orlando, Assigning document identifiers to enhance compressibility of Web Search Engines indexes, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968024]
• 27: Torsten Suel , Jun Yuan, Compressing the Graph Structure of the Web, Proceedings of the Data Compression Conference, p.213, March 27-29, 2001
• 28: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Experimentation, Measurement, Theory

Keywords:
compression, linear arrangement, reciprocity, social networks