Hossein Maserrat
ABSTRACT
Compressing social networks can substantially facilitate mining and advanced analysis of large social networks. Preferably, social networks should be compressed in a way that they still can be queried efficiently without decompression. Arguably, neighbor queries, which search for all neighbors of a query vertex, are the most essential operations on social networks. Can we compress social networks effectively in a neighbor query friendly manner, that is, neighbor queries still can be answered in sublinear time using the compression? In this paper, we develop an effective social network compression approach achieved by a novel Eulerian data structure using multi-position linearizations of directed graphs. Our method comes with a nontrivial theoretical bound on the compression rate. To the best of our knowledge, our approach is the first that can answer both out-neighbor and in-neighbor queries in sublinear time. An extensive empirical study on more than a dozen benchmark real data sets verifies our design.
Supplemental Material
- M. Adler and M. Mitzenmacher. Towards compressing web graphs. In Data Compression Conference, 2001. Google Scholar
Digital Library
- A. Apostolico and G. Drovandi. Graph compression by BFS. Algorithms, 2(3):1031--1044, 2009.Google ScholarCross Ref
- P. Boldi, M. Santini, and S. Vigna. Permuting web graphs. In Proceedings of the 6th International Workshop on Algorithms and Models for the Web-Graph (WAW'09), Berlin, Heidelberg, 2009. Springer-Verlag. Google ScholarDigital Library
- P. Boldi and S. Vigna. The webgraph framework I: compression techniques. In WWW, 2004. Google ScholarDigital Library
- P. Boldi and S. Vigna. The webgraph framework II: Codes for the world-wide web. In Data Compression Conference, 2004. Google ScholarDigital Library
- A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher. Min-wise independent permutations. J. Comput. Syst. Sci., 60(3):630--659, 2000. Google ScholarDigital Library
- G. Buehrer and K. Chellapilla. A scalable pattern mining approach to web graph compression with communities. In WSDM, 2008. Google ScholarDigital Library
- F. Chierichetti, R. Kumar, S. Lattanzi, M. Mitzenmacher, A. Panconesi, and P. Raghavan. On compressing social networks. In KDD, 2009. Google ScholarDigital Library
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2nd edition, 2001. Google ScholarDigital Library
- J. D'ıaz, J. Petit, and M. J. Serna. A survey of graph layout problems. ACM Comput. Surv., 34(3):313--356, 2002. Google ScholarDigital Library
- C. H. Papadimitriou. The NP-completeness of the bandwidth minimization problem. Computing, 16(3):263--270, 1976.Google ScholarCross Ref
- S. Raghavan and H. Garcia-Molina. Representing web graphs. In ICDE, 2003.Google Scholar
- K. H. Randall, R. Stata, J. L. Wiener, and R. Wickremesinghe. The link database: Fast access to graphs of the web. In DCC, 2002. Google ScholarDigital Library
- K. F. Stanley Wasserman. Social networks analysis: Methods and Applications. Cambridge Press, 1994.Google ScholarCross Ref
- T. Suel and J. Yuan. Compressing the graph structure of the web. In Data Compression Conference, 2001. Google ScholarDigital Library
- D. J. Watts and S. H. Strogatz. Collective dynamics of 'small world' networks. Nature, 393(6684):440--442, 1998.Google ScholarCross Ref
Index Terms
- Neighbor query friendly compression of social networks
Recommendations
On compressing social networks
KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data miningMotivated 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 ...
Community Preserving Lossy Compression of Social Networks
ICDM '12: Proceedings of the 2012 IEEE 12th International Conference on Data MiningCompression plays an important role in social network analysis from both practical and theoretical points of view. Although there are a few pioneering studies on social network compression, they mainly focus on lossless approaches. In this paper, we ...
Query Processing in Location-Based Social Networks
WWW '17 Companion: Proceedings of the 26th International Conference on World Wide Web CompanionThe widespread proliferation of location-acquisition techniques and GPS-embedded mobile devices resulted in the generation of geo-tagged data at unprecedented scale and have essentially enhanced the user experience in location-based services associated ...
Comments