TB-GA: Scaling Positive Social Influence through Two-Hop Connectivity

TL;DR

Researchers have developed TB-GA, a high-efficiency greedy algorithm that identifies the most influential "positive leaders" in a social network. Unlike previous methods that struggle with large data, TB-GA uses a two-hop coverage strategy to select nodes, making it nearly 300x faster than traditional greedy approaches on large-scale datasets like Facebook, while ensuring the group of influencers remains fully connected for better coordination.

The "Majority Influence" Problem

In social psychology, the "word-of-mouth" effect isn't just about knowing one person who does something; it's about the environmental threshold. If more than half of your friends quit smoking, you are statistically far more likely to quit too. In graph theory, this is modeled as a Positive Influence Dominating Set (PIDS)—a subset where every node in the graph has at least 50% of its neighbors inside the set.

However, identifying the smallest such set while ensuring all chosen leaders can communicate with each other (Connected PIDS) is an NP-hard challenge. Previous SOTA algorithms were either too slow for modern social media scales or produced "influencer sets" that were so large they included almost the entire population, defeating the purpose of targeted intervention.

Methodology: The Three-Phase TB-GA

The core insight of the Two-hop Based Greedy Algorithm (TB-GA) is that node influence is local. By limiting the greedy search to a 2-hop radius, the algorithm can process multiple "influence zones" simultaneously.

1. Greedy PIDS Construction

The algorithm defines coverage(u) as the number of neighbors of u that are not yet satisfied by the 50% rule. It selects nodes with the highest 2-hop coverage as dominators. Caption: The iterative process of selecting dominators (black/red) to satisfy the neighbors (yellow).

2. Improved Steiner Tree Connection

Once the PIDS is formed, it often exists as "islands" of nodes. TB-GA connects these using a Steiner Tree variation, choosing bridging nodes that connect the maximum number of independent components.

3. Redundancy Removal

Finally, the algorithm prunes the set. If removing a node doesn't break the 50% rule for its neighbors and doesn't disconnect the graph, it is demoted.

Experimental Breakthroughs

The authors tested TB-GA against Wang-Greedy, Self-Stabilizing Algorithms (SSA), and Learning Automata (LAA) across synthetic (Scale-free, Small-world) and real networks (Karate Club, Facebook, Enron Email).

Performance vs. Time

The speed difference is staggering. On the Ego-Facebook dataset:

• Wang-Greedy: 3,205 seconds
• SSA: 108.9 seconds
• TB-GA (Proposed): 10.79 seconds

Caption: Comparison of solution set sizes. TB-GA consistently finds smaller or comparable sets to SOTA while being orders of magnitude faster.

Critical Insight: Why Two-Hops?

The paper proves theoretically (Theorem 1) that in a PIDS, the distance between any two components is no greater than 3. This justifies why a 2-hop search is the "sweet spot"—it is wide enough to see potential connections but narrow enough to maintain a low computational overhead of $O(n^3)$ in the absolute worst case, and much closer to linear in practice.

Conclusion & Future Work

TB-GA solves the scalability bottleneck for CPIDS. It moves social influence research from theoretical "toy" networks to real-world application. The next frontier? Extending this to dynamic networks where friendships evolve over time, requiring the CPIDS to update in real-time without re-running the entire three-phase pipeline.

Takeaway: If you want to change a community, you don't need everyone—you just need a connected 50% threshold, and now we finally have the algorithm to find them instantly.