DT-TMP: Navigating the Invisible—Efficiently Discovering Hidden Populations in Social Networks

TL;DR

Social scientists often need to find "hidden populations"—groups like people with specific mental illnesses or covert social behaviors—who don't explicitly label themselves. Since you can't just query "depressed person" on Twitter and get accurate results, this paper proposes DT-TMP, a reinforcement learning approach that uses hierarchical Decision Trees and Thompson Sampling to "guess" which combinations of observable attributes (location, age, hashtags) will most likely lead to the hidden target group.

The "Non-Queryable" Challenge

Searching for specific groups in modern social networks is a battle against two major hurdles:

1. Non-queryable Properties: Members of hidden populations often avoid self-identifying keywords for privacy or social reasons.
2. The Combinatorial Explosion: If you try to combine attributes (e.g., Location: NY + Language: English + Hashtag: #Health), the number of possible queries grows exponentially, yet API rate limits (like Twitter's 180 calls per 15 mins) prevent you from trying them all.

Existing methods like Random Walks or Graph Crawling are often trapped by local network structures, while Query Reformulation relies too heavily on text similarity, which doesn't work for hidden traits.

Methodology: The Power of Hierarchical Bandits

The authors' core insight is that while a property like "mental illness" isn't queryable, it is often correlated with queryable facets. The DT-TMP (Decision-Tree Thompson Sampling) algorithm treats query selection as a Multi-Armed Bandit (MAB) problem but with a twist.

1. Hierarchical Organization

Instead of viewing every possible query as a flat list, DT-TMP organizes them into a tree—from the most general query (e.g., * for all attributes) to the most specific (e.g., NY + Young).

2. The Reward Function

The algorithm doesn't just look for "number of hits." It uses a sophisticated Multi-Arm Bandit reward function that accounts for:

• Uniqueness: Avoiding queries that return entities we have already seen.
• Stochastic Feedback: Recognizing that different result pages of the same query have different yields.
• Exploration-Exploitation: Using Thompson Sampling to try new query branches while doubling down on proven "high-yield" attribute paths.

Experimental Results: SOTA Performance

The researchers tested DT-TMP across three online platforms (Twitter, RateMDs, GitHub) and three offline datasets.

• Twitter Results: Identifying female users or early adopters, DT-TMP achieved a 54% improvement in throughput over standard samplers.
• Efficiency: As shown in the performance charts, DT-TMP reaches high coverage much faster than traditional methods like Lazy Slice (LS) or Content-Based (CB) search.

Critical Analysis & Insights

Why does this work? The paper demonstrates that combinatorial querying (conjoined attributes) is significantly more powerful than querying attributes individually. By exploiting the clustering effect—where certain attribute sets naturally group members of a hidden population—DT-TMP effectively "mines" the social network's underlying logic without needing access to its proprietary ranking algorithms.

Limitations

• Cold Start: The algorithm still requires an initial period to explore the "general" queries before it can effectively branch out.
• Oracle Dependency: It assumes the existence of a perfect "Oracle" (e.g., a high-accuracy classifier) to verify if a sampled entity belongs to the target population once retrieved.

Conclusion

DT-TMP represents a significant leap for digital sociology and targeted social mining. It proves that by treating the search space as a structured reinforcement learning problem, we can bypass the "black-box" limitations of modern APIs to find the needles in the social media haystack.