[WWW] Expansion Sampling: Finding the 1% Most Influential People by Just Crawling

TL;DR

How do you find the most influential people in a massive social network if you can only see a tiny fraction of the links? This paper proposes Expansion Sampling (XS), an online crawling strategy that ignores the "popular" nodes to focus on "expansion" nodes. By simply picking nodes that reveal the most new connections, the algorithm identifies top-ranked individuals (Betweenness, Closeness, PageRank) with only 1% of the total network data.

Problem & Motivation: The "Blind" Crawler's Dilemma

In the era of massive graphs like the Web or Facebook, performing global calculations like PageRank or Betweenness Centrality is often impossible. The network might be too large for memory, or the API might limit your view to just the immediate "friends" of a node (a local crawl).

Prior works like Breadth-First Search (BFS) or Random Walks (RW) have a major flaw: they get "trapped" in dense clusters or biased towards high-degree nodes that might not actually be the most important "bridges" in the network. The challenge is: How can we decide who to crawl next using only local info to find the most influential nodes globally?

Methodology: The Power of Expansion

The authors suggest a shift in perspective. Instead of following the most popular nodes, they look for Expansion.

The Expansion Heuristic

At each step of the crawl, the algorithm looks at the neighbors of the current sample. It chooses the node $v$ that provides the maximum number of new neighbors not already seen by the sample. Mathematically: $v^{\ast }=ext{argmax}_{v\in N(S)}|N(\{v\})-(N(S)\cup S)|$

The Intuition:

• Betweenness: Nodes that expand the sample are likely "brokers" between clusters.
• Closeness: A sample with high expansion is, by definition, one hop away from a larger portion of the total network.

Experiments & Results: Winning Across the Board

The researchers tested XS against standard methods (BFS, DFS, Random Walk) and Web-crawling specific algorithms (OPIC, Backlink Count) across four datasets including the Enron email network and Slashdot.

Key Findings:

1. Betweenness Domination: XS significantly outperformed all others in finding nodes with high betweenness. BFS and OPIC were surprisingly poor in this category.
2. The "One Percent" Miracle: In most datasets, crawling just 1% of the nodes using XS was enough to capture a large portion of the Top-50 most influential people.
3. Surpassing Domain-Specific Crawlers: Even for PageRank, XS outperformed algorithms like OPIC which were specifically built for PageRank computation.

Figure (a): XS (Solid line) consistently maintains the highest Jaccard similarity for Betweenness Centrality across datasets.

Figure 2: Analysis of Kendall's Tau shows that even with small samples, the relative ranking of nodes remains highly consistent with the ground truth.

Critical Analysis & Conclusion

This work demonstrates that Expansion Sampling is an incredibly robust "swiss-army knife" for social network analysis. Unlike other methods that specialize in one type of influence, XS identifies nodes that are central in diverse ways.

Limitations:

• The algorithm assumes we can "peek" at the degree/neighborhood size of a node before fully exploring it, which might be restricted by some platform APIs.
• It is a greedy approach; while efficient, it doesn't guarantee a globally optimal expander graph.

Future Outlook: This approach has massive implications for Viral Marketing and Epidemiology. If you can identify the "superspreaders" or "information brokers" by only surveying 1% of a population, you can design much more efficient intervention strategies for everything from product launches to disease control.