SN-UCB1: Balancing Exploration and Exploitation in Social Network Crawling

TL;DR

Social network (SN) querying—finding specific profiles via targeted crawling—is often limited by the efficiency of selecting the next node. While existing methods use "best-first" heuristics, they frequently get stuck in local optima. This paper introduces SN-UCB1, a framework that treats social networks as a Volatile Multi-Armed Bandit (VMAB) problem. By balancing the urge to exploit known high-utility clusters with the need to explore new topological regions, SN-UCB1 achieves SOTA recall with significantly fewer requests.

Problem & Motivation: The Short-Sightedness of Pure Exploitation

Traditional SN crawlers use heuristics like "Known Degree" (KD) or "Homophily," assuming that nodes similar to target profiles are likely to be targets themselves.

In academic terms, this is pure exploitation. These methods overlook the Exploration-Exploitation Tradeoff:

1. Exploitation: Acquiring a profile that likely matches the query.
2. Exploration: Acquiring a profile to reveal its "List of Friends" (LOF), potentially uncovering a whole new cluster of relevant nodes.

The authors argue that without a principled way to sample the unknown parts of the graph, crawlers become inefficient as they scale.

Methodology: Social Network as a Volatile Bandit

The core innovation lies in mapping the graph topology to a bandit framework.

1. Structural Equivalence Classes (SECs)

Instead of treating every node as an arm (which would be computationally impossible), the authors group nodes into Structural Equivalence Classes (SECs). A SEC consists of frontier nodes that share the exact same set of known neighbors. Topologically, these nodes are indistinguishable, so their expected utility is identical.

2. The Volatile Multi-Armed Bandit (VMAB)

Unlike standard bandits, the sets of "arms" in a social network are not static:

• Appear: New SECs are discovered as we crawl.
• Disappear: All nodes in a SEC are exhausted.
• Split: Acquiring a node reveals new edges that break the equivalence of its former peers.

To handle this, the authors developed VUCB1, a policy that adjusts the standard Upper Confidence Bound (UCB) by accounting for the "turn" the arm appeared and the non-stationary nature of sampling without replacement.

Figure 1: Illustration of how SECs (arms) evolve—appearing, disappearing, and splitting during the crawl.

Experiments & Results: Efficiency Gains

The authors tested SN-UCB1 against BysP, the previous SOTA heuristic for the TONIC (Target Oriented Network Intelligence Collection) domain.

• Domain: 211K profiles from Google+ and the DBLP co-authorship network.
• Performance: SN-UCB1 consistently hit recall targets faster than BysP. For example, in DBLP, it reached 98% recall with ~6,500 acquisitions, while BysP required over 7,500.

Figure 2: Performance comparison—SN-UCB1 (blue line) tracks closer to the "Optimal Arm" oracle than the traditional BysP heuristic.

The "Virtual Acquisition" Trick

A standout feature of the implementation is the use of Virtual Acquisitions. To prevent the crawler from "over-exploring" every single new SEC (which would be slow), the authors initialize new SECs with a "prior" utility based on existing heuristics. This hybridizes the strength of principled bandit theory with domain-specific knowledge.

Critical Analysis & Conclusion

SN-UCB1 is a powerful shift from "blindly following the path" to "mapping the terrain." By providing provable performance guarantees (logarithmic regret), it moves SN querying from an ad-hoc engineering problem to a robust algorithmic one.

Limitations: The current approach assumes the utility function can be evaluated immediately upon node acquisition. In real-world scenarios where data cleaning or complex NLP is required, the "reward" might be delayed, suggesting a potential future extension into Delayed Reward Bandits.

Takeaway for Practitioners: If you are building a crawler for OSINT, marketing, or research, don't just follow the "best" lookalike. Dedicate a budget to exploring unique topological "arms" early in the process—it pays off in the long run.