Neighbor query friendly compression of social networks
Lists
Only you see this
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.
BibTeX
@inproceedings{maserrat2010neighbor,
author = {Hossein Maserrat and Jian Pei},
title = {{Neighbor query friendly compression of social networks}},
booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
year = {2010},
doi = {10.1145/1835804.1835873},
}Loading related content...