document: Neighbor query friendly compression of social networks 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 .
doc_bio_tags: O O O B O B I O B I O O O O O O O O O B I O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O B I O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O