TIFIM: Balancing Efficiency and Accuracy in Social Network Influence Maximization

TL;DR

Influence Maximization (IM) helps identify the most "infectious" nodes in a network to maximize information spread. While greedy algorithms are accurate but slow, and heuristics are fast but often inaccurate, the TIFIM (Two-stage Iterative Framework for Influence Maximization) provides a much-needed middle ground. By iterating through a two-hop benefit measure and stripping away "Apical Dominance" (overlapping influence), TIFIM outperforms SOTA benchmarks like IMM and RIS in both spread and speed.

The Problem: The Efficiency-Accuracy Trade-off

Identifying the $k$ most influential nodes is an NP-hard problem.

• Greedy Algorithms: Provide a $1-1/e$ approximation but are computationally prohibitive for networks with millions of edges.
• Heuristic Algorithms: (e.g., PageRank, Degree centrality) are lightning-fast but ignore the "influence overlap" problem—where two influential nodes reach the same audience, wasting resources.

The authors of TIFIM argue that a framework must account for the local "spread benefit" of a node within its immediate neighborhood while iteratively refining the global ranking to maintain stability.

Methodology: The Two-Stage Approach

Stage 1: Candidate Selection via FLAS

Instead of calculating global spread (which requires costly Monte Carlo simulations), TIFIM uses the First-Last Allocating Strategy (FLAS). It focuses on the Two-Hop Measure. Social science research suggests influence dissipates rapidly beyond three hops; thus, a two-hop evaluation captures the bulk of a node's power.

TIFIM iteratively updates the "spread benefit" of each node based on the ranking of the previous iteration. This process is proven to converge to a stable ordering within finite iterations.

Stage 2: Refining Seeds via RAD

Even among top-tier candidates, redundancy exists. The paper introduces the concept of Apical Dominance: a phenomenon where a node's influence is masked or "dominated" because its potential audience is already covered by another chosen seed.

The Removal of Apical Dominance (RAD) algorithm iteratively swaps the "minimum-gain" node in the current seed set with a higher-gain candidate from the pool until the total spread benefit no longer increases.

Experimental Performance

The researchers tested TIFIM across eight diverse datasets, ranging from small scientific collaboration networks (Netscience) to larger social graphs like Bitcoin OTC and Chess.

1. Influence Spread

Under both Independent Cascade (IC) and Linear Threshold (LT) models, TIFIM consistently produced a larger influence spread than IMM, RIS, and CoFIM. The iterative refinement allows TIFIM to find those "hidden gems"—nodes that aren't necessarily high-degree but are strategically positioned.

2. Running Time

Efficiency is where TIFIM shines. While PageRank is the fastest (due to its simplicity), it yields poor spread. TIFIM achieves its superior spread while being significantly faster than the complex Martingale-based IMM algorithm.

• vs. IMM: ~22.6% faster on average.
• vs. RIS: ~51.3% faster on average.

Future Outlook: Beyond Ad Clicks

The TIFIM framework isn't just for marketing. The authors suggest extending this iterative logic to Opinion Formation and Recommendation Systems. By understanding how influence overlaps and decays within two hops, we can better model how public opinion shifts or how new products diffuse through tight-knit communities.

Key Limitation: The current iteration count ($T_I$) and the candidate scaling factor ($\lambda$) are hyperparameters that may need tuning for hyper-scale graphs (billions of nodes). However, the mathematical proof of convergence provided in the appendix gives strong confidence in the framework's stability.

Conclusion

TIFIM proves that you don't need to sacrifice performance for speed. By replacing global simulations with iterative local benefit calculations and smart overlap removal, TIFIM sets a new standard for practical, large-scale influence maximization.