InfoMR: Scaling Social Community Discovery via Information Compression and MapReduce

TL;DR

As social networks explode to millions of nodes, traditional mining algorithms have hit a computational "wall." This paper presents InfoMR, an innovative approach that treats community detection as a data compression problem. By using MapReduce to parallelize a 2-level Huffman coding scheme, the authors demonstrate a method that is not only faster but also more accurate than classic modularity-based benchmarks.

Background & Motivation: The Complexity Trap

In the era of "Big Data," social platforms like Facebook and Twitter have rendered $O(n^2)$ algorithms obsolete. The core challenge is two-fold:

1. Computational Cost: Algorithms like GN (Girvan-Newman) are too slow for networks exceeding a few thousand nodes.
2. Accuracy Limits: Many greedy algorithms use "Modularity" as an objective function, which suffers from a resolution limit—essentially "missing" small communities in large networks.

The authors' insight is to shift the perspective from topology to information flow. If a network has a clear community structure, a "random walker" will spend a lot of time within a community before jumping out. We can compress the description of this walk if we know the community boundaries.

Methodology: The Map Equation Meets Parallelism

1. The Information Compression Model

The authors use a 2-layer Huffman coding scheme. Imagine an address: rather than giving every house in the world a unique 100-digit ID, we use "City + Street + House Number."

• Layer 1: Identifies the community.
• Layer 2: Identifies the node within that community.

The goal of community mining is transformed into finding a division $M$ that minimizes the average description length $L(M)$ of a random walk: $L(M)=qH(Q)+{\sum }_{i=1}^m{p}^{i}H(P^i)$ where $H(Q)$ is the entropy of jumping between communities and $H(P^i)$ is the entropy of movement within community $i$.

2. The InfoMR Framework

To handle big data, the algorithm is split into two MapReduce stages:

• ParP (Parallel Probability): A MapReduce implementation of PageRank to calculate the steady-state visit frequency ($p_i$) for every node.
• ParS (Parallel Search): The network is split into subsets. Each Reducer independently optimizes the local community structure using the information compression formula, then results are merged globally.

Figure: The parallel computing pipeline for node accessing probabilities.

Experiments & Results

The authors tested InfoMR against Fast GN and PDST using LFR benchmark datasets and real-world networks like LiveJournal (3.9M nodes).

High Accuracy

Even as the network structure becomes "fuzzy" (high mixing parameter $u$), InfoMR maintains a high Normalized Mutual Information (NMI). Unlike Fast GN, which loses accuracy quickly, InfoMR's information-theoretic objective is sensitive to both small and large structures.

Figure: Accuracy comparison on different datasets. InfoMR consistently stays at the top.

Linear Scalability

One of the most impressive results is the performance on the D2 dataset (10M nodes, 200M edges). The execution time decreases almost linearly as more reducers are added, eventually hitting a "Long Tail" plateau due to MapReduce's fixed startup overhead.

Critical Analysis & Future Outlook

While InfoMR is powerful, it has a few constraints:

• Data Locality: The performance depends on how the graph is partitioned. If communities are split across too many map tasks, some accuracy might be lost (though the authors argue this is negligible in sparse real-world graphs).
• Non-Overlapping Communities: The current model assumes a node belongs to only one community. Future work could extend the information coding to allow for multiple memberships.

Conclusion: InfoMR proves that the "Map Equation" is not just a theoretical curiosity but a practical tool for industrial-scale graph analysis. By moving from purely structural metrics to information-theoretic ones, we can find more meaningful patterns in the noise of big data.