BigFoP: Scaling Social Network Discovery with MapReduce

TL;DR

In the era of big social data, understanding who follows whom is a goldmine for both users and businesses. This paper introduces BigFoP, a MapReduce-based distributed solution that mines frequent "following" patterns—essentially identifying the "influencer bundles" that people subscribe to. By moving away from serial processing, BigFoP handles millions of connections with an 8x speedup over previous benchmarks.

Background: Friendship vs. Following

Most social network analysis focuses on undirected relationships (e.g., Facebook friendship). However, the "Following" model (Twitter/Weibo) is directional ($DoE$), creating a more complex graph.

• Complexity: In an undirected graph of $V$ entities, there are $V(V-1)/2$ possible edges; in a directional graph, this doubles to $V(V-1)$.
• Physical Intuition: Because $A$ following $B$ doesn't imply $B$ follows $A$, the data storage and mining search space increase drastically.

Methodology: The BigFoP Framework

The core innovation is a multi-pass MapReduce strategy that mimics the "Apriori" principle for distributed environments.

1. The Strategy of Pruning

BigFoP operates on a simple but powerful intuition: if a single entity is not frequently followed, any group containing that entity cannot be frequent either. This allows the system to prune millions of irrelevant combinations before they are even processed.

2. Multi-Stage Pipeline

The architecture proceeds through $k$ iterations to find $k$-tuplets:

• Phase 1 (Individual Followees): Maps edges to count followers per individual. If counts exceed the min_frequency, they are promoted.
• Phase 2 (Pairs): Uses the survivors of Phase 1 to generate pairs.
• Phase k (Groups): Iteratively builds larger groups ($k=3,4,...$) until no more frequent patterns are found.

Figure 1: Illustration of a social graph used to demonstrate directional following relationships.

Experiments and Performance

The researchers tested BigFoP against FoP-miner (a serial algorithm) using the Amazon EC2 cluster and SNAP datasets.

• The Datasets:
  • Facebook: ~88k connections.
  • Twitter: ~1.77 million connections.
• The Benchmark: As shown in the performance charts, BigFoP maintains a competitive edge as the "interestingness" threshold (frequency) changes.

Figure 2: Performance comparison showing the speedup of BigFoP over serial competitors.

Critical Insight: Why MapReduce?

The beauty of BigFoP’s MapReduce implementation is its divide-and-conquer nature. Once the network is partitioned (e.g., partitioning by followers of entity A vs. entity B), each processor can operate independently. This minimizes the "shuffling" overhead—a common bottleneck in distributed systems—because the data required for higher-order pattern mining (triplets, quadruplets) naturally flows from the local data emitted in previous stages.

Conclusion & Future Outlook

BigFoP effectively translates social behavior into actionable data. For a newcomer on Twitter, these patterns suggest "bundles" of accounts to follow. For a business, it reveals which niche interests overlap (e.g., "People who follow Marvel also follow a specific indie comic artist").

Limitations: While effective, the iterative nature of the MapReduce passes can introduce overhead for very deep patterns. Future research might explore Stateful Stream Processing or Graph Neural Networks (GNNs) to capture these patterns in a single pass.