Timing is Everything: Maximizing Influence in Evolving Social Networks

TL;DR

Most influence maximization research treats social networks as static, but real-world connections are in constant flux. This paper proves that once you account for network evolution, the traditional mathematical "safety net" of submodularity disappears. The authors introduce the EvolveMaxSpread problem, showing that when you activate an influencer is just as critical as who you choose.

The "Static" Fallacy in a Dynamic World

Since the seminal work of Kempe et al. (2003), the goal of influence maximization has been to find a set of "seed" nodes that maximize the expected spread of a trend or product. This is usually solved via a Greedy algorithm, guaranteed to be effective because the spread function is submodular (the law of diminishing returns).

However, the authors of this paper argue that aggregating a week's worth of interactions into one static graph—the Union Graph—is a dangerous oversimplification. In reality:

• Edges appear and disappear (e.g., people only meet at specific times).
• Activating a node too early might waste its "infectious" potential if its neighbors aren't present yet.
• Activating a node too late might mean the "path" to the rest of the network has already dissolved.

Methodology: Transient vs. Persistent Diffusion

The paper redefines the two classic models (Independent Cascade and Linear Threshold) through an "evolving" lens, splitting them into two temporal categories:

1. Transient Models (tEIC, tELT): Influence is a "one-shot" deal. If node A is activated at time $t$, it can only affect neighbors present at that exact moment. This mimics viral content with a short shelf-life.
2. Persistent Models (pEIC, pELT): Influence accumulates. Node A stays "infectious" and will attempt to influence node B the first time they meet in the future.

The Theoretical Shock: Loss of Submodularity

The most striking finding is that for Transient IC models, the spread function is neither monotone nor submodular.

Why? Because of a phenomenon the authors call Blocking. If an influencer is activated too early, it might trigger a chain reaction that activates a "bridge" node at a time when that bridge has no further outgoing connections. If we had waited, that bridge node could have reached thousands. In this world, $Spread(A\cup B)$ can actually be less than $Spread(A)$.

Figure 1: Comparison between an evolving sequence (G1, G2, G3) and the static Union Graph (GU). Information can only flow if edges exist at the right time.

The Importance of Timing

To address this, the authors propose a Greedy-AT (Any-Time) algorithm. Unlike traditional methods that activate all seeds at $t=0$, Greedy-AT explores the optimal time-stamp for each seed.

Experiments: The Cost of Ignoring Evolution

The research tested these models on three real datasets:

• Hospital-Ward: Contact patterns of doctors and patients.
• DBLP: Co-authorship over years.
• Social-Evolution: Bluetooth-based proximity of students.

Figure 8: Performance comparison. Notice how "Greedy-AT" (Any-Time) vastly outperforms "Greedy-OT" (One-Time). In some cases, activating at the wrong time (t=0) is no better than random selection.

Key Findings:

1. The Union Graph is Optimistic: Estimating spread on a static union graph overestimates reality by up to 10x because it assumes all edges exist simultaneously.
2. Timing Trumps Topology: Even simple degree-based heuristics perform better if you are allowed to choose when to activate the node rather than being forced to start at $t=0$.
3. The Persistent Advantage: In persistent models (where influence waits for edges), submodularity is preserved (if probabilities are fixed), making them easier to optimize but less realistic for "viral" transient events.

Summary & Future Outlook

This paper serves as a wake-up call for the algorithmic social science community. We can no longer ignore the Temporal Dimension.

Takeaways for Practitioners:

• If you are running a marketing campaign on a network that changes (like a daily commute or a conference), don't blow your budget on Day 1. Spread your activations to match the network’s evolution.
• Be wary of "optimal" influencers identified by static analysis; they may be central in the aggregate but Isolated at the specific times when diffusion is actually possible.

Future Research: The next frontier involves Online Algorithms—making these activation decisions in real-time as the network evolves, without knowing the future snapshots in advance.