Beyond Connectivity: Maximizing Influence via Trust and User Similarity in Social Networks

TL;DR

This research moves influence maximization (IM) from abstract graph theory into the realm of human psychology. By introducing the Independent Cascade with Trust (ICT) model, the authors prove that influence isn't just about "who you know" but "how much you trust them." They provide a high-efficiency algorithmic duo—RSG and PPCN—that maintains high accuracy even when the traditional mathematical safety nets of sub-modularity and monotonicity fail.

The Problem: The "Constant Probability" Fallacy

Most SOTA influence maximization research treats the probability of "node A activating node B" as a fixed constant or a simple degree-based ratio. In reality, your friend's recommendation carries more weight if you share similar tastes (User Similarity) and many mutual friends (Social Relationship).

Current methods like CELF fail here because they rely on sub-modularity (the law of diminishing returns). The authors demonstrate that once trust and intimacy are factored in, adding a new seed node can sometimes have a non-linear, unpredictable impact on the total spread, breaking the mathematical assumptions of previous greedy approaches.

Methodology: Engineering Trust into Algorithms

1. The ICT Model: Defining Trust

The authors define the propagation probability $p_{u,v}$ as a hybrid metric:

• Social Relationship ($p_{u,v}^S$): Based on the Jaccard similarity of mutual neighbors.
• User Similarity ($sim(i,f)$): Calculated via ranking behavior on products, using an exponential decay function to weights ranks.

2. RSG Algorithm: Pruning the Search Space

Because the ICT model is non-submodular, we cannot use traditional fast-greedy methods. The Relationship Select Greedy (RSG) algorithm uses:

• Snapshots: Generating sub-graphs to predict spreads.
• Dynamic Pruning: Utilizing "Ubound" techniques to skip nodes that mathematically cannot exceed the current maximum marginal gain.

3. PPCN: The Strategy of Path Propagation

The Path Propagation finding Crucial Nodes (PPCN) algorithm is the "secret sauce" for efficiency. Instead of expensive Monte Carlo simulations, it uses a BFS-like traversal to estimate activation probabilities based on propagation paths, capped at 6 hops (the "Six Degrees of Separation" theory).

Fig 1: Identifying crucial bottleneck edges in a social network where information flow is restricted.

Experimental Insights: Performance vs. Reality

The researchers tested their approach against Benchmarks like CELF, Simulated Annealing (SA), and Simple Greedy on Epinions (a trust-based network) and Wikipedia (a voting network).

Key Findings:

• Effectiveness: RSG+PPCN achieved influence spreads nearly identical to Brute-force Monte Carlo but at a fraction of the cost.
• Robustness: In the ICT model, CELF and SA performed poorly because they couldn't adapt to the non-submodular nature of trust-based probabilities.
• Efficiency: The time complexity is brought down to linear time relative to the number of nodes, $O(K|V|)$.

Fig 2: Effectiveness of PPCN compared to Monte Carlo simulations across different seed counts.

Depth Insight: Why It Matters

The most striking takeaway is the discovery of Crucial Nodes. The PPCN algorithm identifies nodes that act as "terminal points" for paths where influence typically fails to pass. By focusing on these bottlenecks, the algorithm ensures that the selected seed set isn't just a cluster of popular users, but a strategic group capable of bridging "trust gaps" in the network.

Conclusion

The paper successfully bridges the gap between social psychology and combinatorial optimization. By acknowledging that propagation probability is dynamic and trust-dependent, the ICT model provides a more realistic framework for viral marketing and information dissemination. While the loss of sub-modularity makes the math "messier," the proposed RSG+PPCN framework proves that efficiency doesn't have to be sacrificed for accuracy.

Future Work: Integrating real-time temporal decay—how trust changes over time—could be the next frontier for this model.