IncInf: Accelerating Influence Maximization in Evolving Social Networks

TL;DR

Social networks are not static; they are living, breathing entities that change every second. Traditional Influence Maximization (IM) algorithms struggle with this volatility because they usually start from scratch. IncInf changes the game by using an incremental approach. By focusing only on local changes and leveraging the "rich-get-richer" nature of social links, it achieves a 21x speedup over top heuristics without losing influence accuracy.

Background: Static Algorithms in a Dynamic World

Most IM research focuses on finding the $K$ most influential nodes in a fixed snapshot of a network. In reality, Twitter adds a million accounts a day, and Facebook's connection graph is constantly mutating. Running a static algorithm every time an edge is added is like re-reading an entire book just because one sentence was edited—it is inefficient and slow.

The challenge is twofold:

1. Complexity: Even a single edge change can theoretically affect the influence spread of thousands of nodes.
2. Search Space: In a network with millions of users, how do we know which subset of nodes has a chance to join the top-K after an update?

The "Rich-Get-Richer" Insight

The authors began by analyzing real-world traces from Facebook and Flickr. They confirmed two critical properties:

• Preferential Attachment: New edges aren't random; they tend to connect to nodes that already have high degrees.
• Influence-Degree Correlation: Highly influential nodes are almost always found among the top 1% of high-degree nodes.

These insights allowed them to design a Pruning Strategy that ignores 95%+ of the network, focusing only on nodes experiencing major "surges" in connectivity or those who are already "celebrities" in the network structure.

Methodology: The Localization Strategy

The core of IncInf is its ability to quantify change. Instead of global simulation, it uses the Maximum Influence Path (MIP) and a threshold $heta$ to localize the impact of a change.

How it handles an Edge Addition (addEdge):

If a new edge $(u,v)$ is added:

1. It checks if the new path's probability is higher than the existing MIP between two nodes.
2. If it is, it only updates the "Influence Spread Change" ($\Delta Inf$) for nodes within a specific local range (where propagation probability $>heta$).
3. It updates the potential influence of node $i$ by calculating how much more likely it is to reach node $j$ via the new link.

(Note: Refer to Algorithm 1 and 2 in the paper for the specific iterative logic and pruning set selection.)

Experimental Results: Efficiency Meets Accuracy

The authors tested IncInf against MixGreedy, ESMCE, and MIA (a popular heuristic).

1. Massive Speedups

On the Flickr dataset (2.5M nodes, 33M edges), IncInf was the clear winner. While MIA took over 45 minutes to process, IncInf finished in a fraction of that time, reaching a 20.65x speedup on average.

2. Matching Influence Performance

Speed is useless if the chosen nodes aren't actually influential. In all three datasets, IncInf provided an influence spread nearly identical to the state-of-the-art MIA and closely trailed the computationally expensive MixGreedy (within a ~5% margin).

Critical Insight & Conclusion

The brilliance of IncInf lies in its Inductive Bias. By assuming that social networks evolve according to power laws, the authors moved the IM problem from a "pure math" graph challenge to a "socially aware" optimization task.

Takeaway: If you are building a viral marketing engine or a recommendation system for a platform that grows daily, Stop recalculating. Use incremental localization to focus on where the "energy" of the graph is shifting.

Limitations: The algorithm heavily relies on the Independent Cascade (IC) model. Future work could explore if these preferential attachment assumptions hold in more complex models like the Linear Threshold (LT) model or in networks with negative influence (like rumor blocking).