BMS: Efficiently Connecting the Dots in Hidden Social Networks

TL;DR

How can an outsider find the shortest path between a group of Facebook users without crawling the entire site? This paper presents Balanced Multiple-Subgraph (BMS), a heuristic search algorithm that exploits the "small-world" nature of social networks to find connecting subgraphs using a minimal number of API queries. It turns an NP-hard problem into a manageable task for third-party analysts.

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

In the era of privacy and API rate limits, a third-party analyst (someone who isn't the platform owner) sees the social network through a "keyhole." You can query a user to see their friends (a Local View), but you cannot see the global map.

If you want to find how a set of target users $S_0$ are connected, you face two massive hurdles:

1. Query Cost: Each "click" or API call is expensive. Brute-force crawling is too slow and will get your IP banned.
2. Computational Complexity: Finding the minimum connecting subgraph is a variation of the Steiner Tree Problem, which is notoriously NP-hard.

The authors ask: Can we use the known "physics" of social networks—like the fact that popular people (hubs) connect everyone else—to find these links faster?

Methodology: The Balanced Multiple-Subgraph (BMS) Approach

The core insight is that social networks are scale-free. High-degree vertices (hubs) act as the "glue" of the network. If we query the right hubs, disparate subgraphs will merge much faster than by chance.

The Algorithm Workflow:

1. Initialization: Query all target users to create individual, likely disjoint, "islands" (subgraphs).
2. The "Current Degree" Proxy: Since we don't know a node's true degree until we query it, we use its current degree (how many edges we've seen so far) as a heuristic.
3. Balanced Search: Instead of just growing the biggest subgraph, the algorithm picks the subgraph with the minimum "subgraph degree" (the lowest peak degree among its queried nodes). It then queries the highest-degree candidate within that specific subgraph.
4. Merging: When a query reveals a node that belongs to two different subgraphs, they merge.
5. Refinement: Once all targets are in one connected component, a standard Steiner Tree approximation (Kou et al.) is applied to trim the fat.

Figure 1: Conceptual visualization of local-view discovery where disjoint subgraphs expand and merge via high-degree candidates.

Experiments & Results: Efficiency in the Real World

The authors tested BMS on three diverse datasets: Facebook (social), Epinion (trust), and Slashdot (technology news).

Key Findings:

• Near-Optimal Size: The subgraphs found by BMS were nearly as small as those found by algorithms that could see the entire graph from the start.
• High Query Efficiency: The number of queries required was remarkably close to the size of the final subgraph. This suggests that the algorithm rarely "wasted" queries on nodes that didn't help build the bridge.
• Topology Matters: The heuristic outperformed random-graph assumptions, proving that social network "hubs" are the most effective targets for connectivity discovery.

Figure 2: Comparison of subgraph size vs. number of queries across Facebook and Epinion datasets.

Critical Analysis & Conclusion

The BMS algorithm is a pragmatic solution to a difficult graph-traversal problem. By focusing on the "weakest" subgraph and pushing it toward "stronger" hubs, it ensures a balanced expansion that prevents the search from getting stuck in local clusters.

Takeaway: If you are conducting research on OSNs with limited data access, stop crawling randomly. Leverage the inductive bias of social structures—specifically the power-law degree distribution—to guide your search.

Limitations:

• The heuristic assumes that the target users are part of the same giant component.
• It does not account for "private" profiles that might hide the very hubs needed to bridge subgraphs.

Future Work: Integrating this with machine learning to predict the degree of a node before seeing any of its edges could further reduce the query budget.