Beyond Seeding: Boosting Social Influence via Strategic Edge Addition

TL;DR

While most research focuses on who to pick as influencers (nodes), this paper asks: Which connections should we build? The authors introduce Boosted Influence Maximization (BIM), proving that adding just a few strategic edges can significantly amplify the reach of existing seeds. They tackle a complex, non-submodular optimization problem with a clever "restricted path" approximation and a high-speed pruning algorithm.

Problem & Motivation: The Network is Not Static

In viral marketing, companies usually spend their budget on "seeds"—influencers who get free samples to spark word-of-mouth. However, the authors observe that it's often cheaper to encourage new connections (e.g., via coupons for "friending" or shared interest recommendations) than to acquire new high-tier influencers.

The technical challenge is that adding edges changes the network topology. Unlike traditional influence maximization, where the marginal gain of adding a seed node decreases (submodularity), adding an edge can create synergistic effects that increase the marginal gain of other edges. This makes the math much harder, as the standard greedy guarantees fall apart.

Methodology: Restoring Submodularity

The core innovation lies in how the authors handle the complexity of the Independent Cascade (IC) model on a modified graph.

1. The Restricted MIA Model

To handle the NP-hard nature of influence estimation, the authors use an arborescence-based approach (MIA). To solve the non-submodularity of edge addition, they introduce a Restricted Form:

• Influence is only calculated along paths that contain at most one new added edge.
• Physical Intuition: Long paths with multiple "artificial" edges are statistically unlikely to successfully propagate influence compared to shorter, more direct paths.
• This restriction makes the function submodular, allowing for a (1 - 1/e) approximation guarantee.

2. The IGA Algorithm

Computing the gain for every possible candidate edge in every iteration is computationally suicidal for large graphs. The Improved Greedy Algorithm (IGA) uses two key insights:

• Reachability Pruning: If a candidate edge's start node cannot be reached by the seeds, adding the edge provides zero gain.
• Lazy Evaluations: Borrowing from CELF-style logic, if an edge's previous marginal gain is already lower than the current best-found gain, it can be skipped because its gain can only decrease (or stay the same) in a submodular setting.

Figure 1: Conceptual illustration of BIM. Dotted lines represent candidate edges that bridge existing communities to the seed set.

Experiments & Results: Performance at Scale

The authors tested their approach on four datasets, ranging from 1,000 nodes (Email) to 109,000 nodes (Web).

• Effectiveness: Adding edges via IGA consistently outperformed heuristics like adding edges to high-degree nodes (LOD) or edges with high activation probabilities (LAP).
• Efficiency: IGA proved to be orders of magnitude faster than a naive greedy approach (SGA), particularly on sparse networks where the reachability pruning is most effective.
• Impact of Density: Interestingly, the algorithm is slower on "dense" graphs like Google compared to "sparse" collaboration networks (NetHEPT), as pruning becomes harder when everyone is more connected.

Figure 2: The increased influence spread vs. number of added edges across different network types.

Critical Analysis & Conclusion

Takeaway

BIM represents a paradigm shift from "who you know" to "how you are connected." By demonstrating that the influence spread function—while technically non-submodular—can be effectively approximated via restricted paths, the authors provide a scalable way to optimize network structures for information flow.

Limitations

1. Candidate Set Selection: The paper assumes a predefined candidate set $C$. In real-world scenarios, how we generate these candidates (e.g., only between "similar" users) is just as critical as selecting from them.
2. Cost Dynamics: The model assumes all edges have equal cost. In reality, connecting a celebrity to a common user is much harder than connecting two similar peers.

Future Outlook

The next logical step is Co-Optimization: designing algorithms that split a fixed budget between node-level seeds and edge-level reinforcements simultaneously.