Beyond the Snapshot: Maximizing Distinct Influence in Evolving Networks

TL;DR

In the world of viral marketing, social networks are never static. While most research focuses on "who is influential now," this paper introduces the Distinct Influence Maximization (DIM) problem. Instead of chasing the latest trends by constantly changing influencers, the goal is to find a stable set of seeds that reaches the maximum number of unique users over a period of time. To make this computationally feasible, the authors developed HCS and VCS, two graph compression strategies that slashed memory usage by 1000x compared to existing SOTA methods.

The Problem: The High Cost of "Keeping Up"

Traditional Influence Maximization (IM) assumes a static graph. In reality, friendships form and dissolve daily. Previous "dynamic" solutions suggested updating the seed set (the influencers) every time the network changed. However, this has three major flaws:

1. Redundancy: You might influence the same "popular" group of people repeatedly while ignoring the wider audience.
2. Operational Overhead: Redesigning personalized ads for new influencers every few hours is impractical.
3. Missed Frequency: Marketing requires a specific exposure level to be effective; constantly swapping seeds prevents building that "effective frequency."

The authors argue for a fixed seed set that performs optimally across a time window (e.g., a week of snapshots).

Methodology: Compressing Chaos

The core challenge of DIM is the "Distinct" part. You have to track reachability across multiple snapshots and multiple Monte Carlo simulations. Doing this naively requires astronomical amounts of memory.

1. Horizontal vs. Vertical Compression

The authors propose two ways to view the data:

• HCS (Horizontal-Compression-Based Strategy): Compresses subgraphs from different snapshots of the same time-step. It’s effective when snapshots overlap significantly.
• VCS (Vertical-Compression-Based Strategy): Compresses subgraphs generated from the same snapshot. This is generally the "winner" because edge overlaps are much higher within the same snapshot’s simulation trial.

2. The Bitset Magic

How do they merge thousands of graphs into one? Bitsets. Every node and edge in the compressed graph carries a "Containment Bitset" ($B_c$). If the $i$-th bit is 1, it means that edge exists in the $i$-th subgraph. During the search (BFS), they use "Traversal Bitsets" to track which "worlds" (subgraphs) are currently exploring that branch, allowing them to calculate reachability for hundreds of scenarios in a single pass.

Fig 1: Example of three subgraphs being merged into a single horizontally compressed graph with bitsets.

Experiments: Performance at Scale

The researchers tested their methods against giants like IMM and PMC on massive datasets like LiveJournal (5.2M nodes, 49M edges).

Memory Efficiency

VCS proved to be an absolute specialist in memory management. In the IM problem, it used 3 orders of magnitude less memory than PMC and IMM. This is a game-changer for deploying these algorithms on standard server hardware rather than high-RAM clusters.

Fig 2: Memory consumption comparison—VCS (our method) remains consistently low compared to other approximation methods.

Influence and Speed

Despite the compression, there is no "lossy" trade-off. The influence spread achieved by VCS and HCS matched the top-tier approximation methods (IMM/PMC) and significantly outperformed heuristic methods like EasyIM. For the DIM problem specifically, these strategies were roughly 1000x faster than CELF, the classic simulation baseline.

Fig 3: Distinct influence spread across multiple snapshots. The methods track almost perfectly with the ground truth (MC simulations).

Critical Insight & Conclusion

The genius of this paper lies in the dual-use of VCS. While designed for temporal (DIM) problems, it actually serves as a superior engine for the traditional IM problem by exploiting the redundancies in Monte Carlo simulations.

Takeaway: If you are working with social graphs that evolve over time (which is almost all of them), stop looking at snapshots in isolation. The "Temporal Influential User" is not the one who is loudest for five minutes, but the one whose influence persists across the network's evolution.

Limitations: The method still assumes we can predict some periodic patterns or have historical snapshots. If a network undergoes a completely "black swan" structural shift, the fixed seed set might lose its edge.