Link Discovery: Hunting for Connections in Hidden Social Graphs

TL;DR

Most algorithms predict who you will follow next. But what if the follow-graph is secret, and you have to pay a price to check if two people are friends? This paper formalizes the Link Discovery problem—a strategic hunt for edges in hidden networks. By combining classic graph theory metrics with supervised learning (Random Forests), the authors demonstrate that we can find "hidden" friends up to 400% more efficiently than random searching.

Background: Prediction vs. Discovery

In the academic coordinate system, this paper sits at the intersection of Graph Mining and Explorative Search.

• Link Prediction (The Standard): You have a graph $G$ at time $t$, and you predict $G$ at $t+1$.
• Link Discovery (This Work): The graph $G$ exists, but it's "invisible." You must pick two nodes and ask, "Are they connected?" This is a budget-constrained search problem.

The motivation is grounded in real-world constraints: privacy-preserving social apps where you can't see the whole network, or IoT/Mobile scenarios where testing for a connection (e.g., via a Bluetooth handshake or a complex database query) is slow and expensive.

The Hurdle: Why is Discovery Hard?

The primary challenge is the sparsity of social networks. In a graph with thousands of nodes, the number of potential pairs is astronomical, but the number of actual edges is tiny. If you guess randomly, your success rate is near zero. To solve this, the authors suggest we need an "exploit" strategy—using the tiny bit of information from previous successful (and failed) tests to find the next edge.

Methodology: Intelligent Edge Probing

The authors propose a multi-stage framework for discovery:

1. Metric-Based Scoring: They adapt classic neighborhood-based metrics to score "candidate" pairs who haven't been tested yet.

   • Common Neighbors: If Node A and B both know Node C, they might know each other.
   • Adamic-Adar: Similar to common neighbors, but weighs "niche" mutual friends more heavily.
   • Preferential Attachment: High-degree nodes (social butterflies) are more likely to form new links.

2. Supervised Learning Pipeline: They treat discovery as a classification problem. They use the scores from the metrics above as features and the results of previous edge tests as training labels.

   • Models: They compare Random Forest (RF), Multi-Layer Perceptrons (MLP), and Naive Bayes.
   • Retraining: The model is periodically retrained every few thousand tests to incorporate new "ground truth" discovered during the search.

Experiments: Real Music and Moving Objects

The researchers tested their approach on two distinct datasets:

1. Last.fm: A real music social network where "links" represent musical compatibility between users.
2. Synthetic Distributed Objects: A simulation of mobile objects moving through space, where link opportunities only occur when objects are physically close.

Key Performance Insights

• The Power of RF: Random Forest consistently yielded the highest success rates, particularly in sparse scenarios.
• Mobile Constraints: In the "Moving Objects" experiment, geographic proximity acts as a natural filter. Within this filtered pool, the supervised learning model effectively identifies actual links among many "near-miss" candidates.
• The Success Multiplier: While discovery is inherently harder than prediction, the proposed methods achieved a success rate significantly higher than the random baseline.

Critical Analysis & Conclusion

The Takeaway: Link Discovery is effectively a "search" problem on a graph manifold. This paper proves that we don't need a full view of a social network to start mapping it intelligently; we just need a few successful probes to train a model that targets the rest.

Limitations: The current study focuses heavily on "Exploitation" (finding what's likely there). In a true discovery scenario, a "Reinforcement Learning" approach that balances Exploration (testing unlikely areas to learn more about graph topology) and Exploitation might perform even better in the long run.

Future Outlook: As decentralized social networks (like Mastodon or Farcaster) and privacy-first "local" social apps grow, the ability to discover connections without a central "God-view" of the graph will become a critical technical requirement.