Compression of Web and Social Graphs supporting Neighbor and Community Queries
Cecilia Hernández and Gonzalo Navarro
Motivated by the needs of mining and advanced analysis of large Web graphs and
social networks, we study graph patterns that simultaneously provide
compression and query opportunities, so that the compressed representation
provides efficient support for search and mining queries.
We first analyze patterns used for Web graph compression while supporting
Our results show that composing edge-reducing patterns with other
methods achieves new space/time tradeoffs, in particular breaking the
smallest known space barrier for Web graphs when supporting neighbor queries.
Second, we propose a novel graph compression method based on representing
communities with compact data structures. These offer competitive support
for neighbor queries, but excel especially at
answering community queries. As far as we know, ours is the first graph
compression method supporting such a wide range of community queries.