DTIM: Enhancing Social Engagement through Topology-Driven Diversity

Executive Summary

TL;DR: The paper introduces Diversity-sensitive Targeted Influence Maximization (DTIM), a framework that optimizes for both "Capital" (target activation) and structural "Diversity." By focusing on how seeds are positioned relative to target users in the network topology, DTIM effectively solves the "lurker engagement" problem, outperforming traditional IM algorithms by up to 59%.

Academic Context: This work moves beyond the "volume-only" approach of SOTA methods like TIM+ and KB-TIM. It sits at the intersection of Influence Maximization and Social Science theories such as Boundary Spanning and Social Embeddedness, proving that structure alone can serve as a powerful proxy for seed diversity.

Problem & Motivation: Why Volume Isn't Enough

Standard Influence Maximization (IM) acts like a blunt instrument: it finds the most "viral" nodes to reach the largest audience. However, in Targeted IM, the goal is often to engage specific groups, such as "lurkers" (users who consume but don't produce content).

The authors argue that a seed's effectiveness isn't just about their reach, but their diversity. If all seeds come from the same social cluster, they bring redundant perspectives and fail to "trigger" engagement in diverse target groups. Most existing solutions require user profiles (age, interest) to measure diversity, which are often unavailable due to privacy or data sparsity.

Methodology: The Core of DTIM

1. The Objective Function

The authors propose a new metric: Diversity-sensitive Capital (DIC). $DIC=\alpha \cdot C(\mu (S))+(1-\alpha )\cdot D(S)$

• Capital ($C$): The cumulative status/weight of activated target nodes.
• Diversity ($D$): Measures how "diverse" the seeds are relative to the target set using topological properties.

2. Topology-Driven Diversity

The breakthrough lies in measuring diversity without side-data. The authors define Target-Specific Diffusion Subgraphs and identify Boundary Sets—nodes that receive influence from outside the current diffusion path.

• Local Diversity (L-DTIM): Computed incrementally as the diffusion subgraph expands. It favors nodes that increase the likelihood of reaching the target through varied paths.
• Global Diversity (G-DTIM): Evaluates the fully unfolded subgraph, emphasizing Boundary Spanning—the ability of a node to bridge external influence into the target’s neighborhood.

Figure 1: Conceptual example where an unsupervised "diversity-aware" method picks seeds u1/u2 over seed 'a' because they bridge multiple network components.

Experiments & Results

The authors tested DTIM on three real-world datasets: FriendFeed, GooglePlus, and Instagram.

Performance Gains

• Superior Capital: DTIM methods consistently provided higher capital than TIM+ and KB-TIM. For example, on FriendFeed, the gain over KB-TIM ranged from 35% to 59%.
• Seed Divergence: The overlap between seed sets produced by L-DTIM and G-DTIM was often below 50%, illustrating that "Local" and "Global" diversity capture fundamentally different structural properties.

Figure 2: Expected Capital on GooglePlus, showing that increasing diversity (lowering alpha) significantly shifts the seed selection and resulting engagement probabilities.

Efficiency vs. Accuracy

While DTIM provides higher accuracy in engagement, the greedy shortest-path approach is slower than RIS-based (Reverse Influence Sampling) methods. Recognizing this, the authors provided a RIS-based formulation of DTIM in the latter half of the paper, paving the way for SOTA efficiency in future implementations.

Critical Analysis & Conclusion

Takeaways: DTIM proves that the "quality" of influence (diversity) is as important as the "quantity." By using boundary spanning principles, marketers and community managers can engage "silent" users more effectively.

Limitations:

1. Computational Complexity: The initial greedy algorithms are computationally expensive for massive graphs compared to sampling methods.
2. Model Dependency: The results are highly dependent on the choice of the underlying diffusion model (Linear Threshold).

Future Work: The transition to RIS-DTIM is the most promising path, potentially offering the performance of DTIM with the sub-linear time complexity required for modern big-data social platforms.