Beyond URLs: The Science of Compressing the Social Fabric

TL;DR

Compressing social networks is fundamentally harder than compressing the Web. While the Web graph can be squeezed into ~2 bits per edge using URL proximity, social networks lack a natural "address." This paper introduces the BL (Backlinks) scheme and Shingle Ordering—a combinatorial approach that uses link reciprocity and neighborhood similarity to achieve state-of-the-art compression on massive networks like Flickr and LiveJournal.

The Motivation: Why Social Graphs Are Stubborn

In the mid-2000s, Boldi and Vigna revolutionized Web compression by showing that if you sort pages by their URLs, neighbors tend to be close to each other (locality) and have similar outgoing links (similarity).

Social networks present a crisis: humans don't have URLs. If we sort users by their "join date" or "random ID," we lose the structural patterns needed for compression. The authors ask: Can we mathematically "discover" an ordering that makes a social network compressible?

The Methodology: Reciprocity and Shingles

1. The BL (Backlinks) Scheme

Social interactions are often mutual. If $A$ follows $B$, there is a high probability $B$ follows $A$. The authors' BL Scheme exploits this by:

• Encoding reciprocal links separately using just one bit.
• Using "copying lists" where a node's neighbors are described as "the same as User X, plus/minus these few changes."

2. Shingle Ordering: The "Fingerprint" Strategy

To solve the ordering problem, the authors use Shingles (MinHash).

• The Intuition: If two users share many friends, their "shingle" (the minimum friend ID under a random permutation) will likely be the same.
• By sorting users by these shingles, nodes with similar neighborhoods are physically moved closer in the data structure, creating the "locality" that compression algorithms crave.

Theoretical Rigor: M-LOGA and M-LOGGAPA

The paper doesn't just provide heuristics; it formalizes the "Minimum Logarithmic Arrangement" (M-LOGA) problem. This seeks a permutation $\pi$ that minimizes $\sum \lg |\pi (u)-\pi (v)|$.

• The Verdict: The authors prove this is NP-hard.
• The Insight: This confirms that finding the "perfect" compression order is computationally infeasible, justifying the use of the Shingle heuristic.

Experiments: How Do We Compare to the Web?

The authors tested their methods on snapshots of Flickr (25M nodes) and LiveJournal (5.3M nodes).

Key Findings:

1. Reciprocity is King: The BL scheme significantly outperformed the BV scheme because it treats "mutual follows" as a first-class optimization target.
2. The "Social vs. Web" Gap: Even with optimal ordering, social networks require ~10 bits/link, whereas the Web graph takes ~2-3 bits.
3. The Cause of Incompressibility: The authors analyzed k-cores (densely connected sub-kernels). They found that the "dense core" of a social network is highly compressible, but the "fringe" (low-degree users) acts like random noise, driving up the average storage cost.

Critical Analysis & Conclusion

This work is a seminal bridge between Web science and Social Network Analysis (SNA).

Takeaway: If you are building an in-memory graph database for a social application, do not rely on crawl order. Implement Shingle-based reordering and explicitly handle reciprocal edges.

Limitations:

• Query Latency: While compression is great, following "prototype chains" (copying from other nodes) can slow down adjacency queries if the chains become too long.
• Dynamic Graphs: Shingle ordering is static. Re-sorting the entire graph every time a new user joins is a significant engineering hurdle that remains an open challenge for real-time systems.

In the end, this paper teaches us that the "randomness" of human interaction makes social networks physically more expensive to store than the structured, hierarchical pages of the World Wide Web.