TIC: Boosting Influence Spread by Merging Viral Marketing with Direct Selling

TL;DR

Classic influence maximization models often get stuck in "stubborn" clusters of a social network. This paper proposes the Target-selecting Independent Cascade (TIC) model, which allows active nodes to dynamically skip difficult neighbors and target "friends of friends" directly. This shift from rigid viral marketing to a "direct selling" approach yields a measurable boost in total influence spread.

Problem & Motivation: The Rigid Edge Fallacy

In traditional models like the Independent Cascade (IC), influence spreads like a virus: you can only infect your immediate neighbors. However, real-world marketing isn't just viral; it’s also direct. A salesperson might see a friend who is unlikely to buy a product (a "victim") but knows that friend's acquaintance (a "destination") would be a perfect fit.

The pain point of prior work is the topological constraint. By forcing influence to flow strictly through every edge, the propagation often dies out at "bottleneck" nodes who have low activation probability. The authors ask: What if we could redistribute our influence attempts for better ROI?

Methodology: The TIC Model

The core innovation is the Target-selecting Mechanism. During each propagation step, an active node $u$ performs two actions:

1. Hiding Links: It identifies a subset of neighbors with low potential (Victims) and chooses not to spend effort on them.
2. Adding Virtual Links: It identifies nodes in its 2-hop neighborhood (Destinations) and creates a direct virtual link to them.

Architecture & Logic

The authors propose the Between Probability heuristic as the most effective strategy. Instead of looking at how "influential" a neighbor is (Degree), it looks at how easy they are to activate based on attribute similarity (Jaccard Coefficient).

The logic is simple: Maximize the probability of the next jump. If a neighbor-of-a-neighbor shares 80% of your interests, they are a better target than a direct neighbor who shares only 10%.

Experiments & Results

The researchers tested TIC on a DBLP co-authorship network (22k+ nodes). They compared three strategies for selecting the targets to skip or jump to:

• Degree Discount: Select based on connectivity.
• Outward Probability: Select based on the neighbor's average ability to influence others.
• Between Probability: Select based on the direct similarity between the active node and the target.

Key Findings

As shown in the charts below, the Between Probability method (the red bars) consistently outperformed other heuristics.

Furthermore, the Selecting Ratio (the percentage of links modified) is a critical lever. As the ratio increases, the "Boost" in influence becomes more pronounced, suggesting that traditional models significantly underestimate the potential spread reachable via "direct selling" shortcuts.

Critical Analysis & Conclusion

Takeaway

The TIC model proves that who you skip is as important as who you target. By allowing nodes to bypass "dead-end" neighbors, the total reach of a campaign can be optimized without increasing the initial seed budget.

Limitations & Future Work

• Submodularity: The paper briefly mentions ongoing work regarding the submodular property. If TIC lacks submodularity, the standard greedy approach for seed selection may not provide the 1-1/e approximation guarantee.
• Attribute Dependency: The "Between Probability" relies heavily on high-quality node attributes (labels/interests). In networks with sparse metadata, this strategy might degrade.
• Computational Cost: Dynamically calculating similarities for 2-hop neighbors during cascades could be expensive for billion-scale graphs.

In conclusion, this work bridges the gap between passive viral spread and active marketing strategy, offering a more flexible framework for influence maximization in the real world.