Abstract
Social networks have become a primary medium for information diffusion. Traditional studies focus on Influence Maximization (IM), which seeks to maximize the number of "active" nodes—those who adopt or propagate information. However, IM ignores "informed" nodes—those aware of the information but not yet active. This paper introduces Information Coverage Maximization (ICM), a framework that optimizes for both active and informed nodes. We prove ICM is NP-hard and submodular under standard diffusion models and propose two efficient algorithms. Experiments on real-world datasets demonstrate the effectiveness of our approach.
Introduction
In viral marketing and public health campaigns, the goal is often broader than just triggering a chain reaction of adoptions. While traditional Influence Maximization (IM) focuses on "active" users (e.g., those who retweet or purchase), it overlooks the "silent majority" who are exposed to the message but do not immediately act. For applications like brand awareness or emergency alerts, simply being "informed" carries significant value. This paper addresses this gap by proposing a model that accounts for the total reach of information propagation.
Problem Definition
The authors propose a new objective: Information Coverage Maximization. Unlike traditional models that treat non-adopters as failures, this framework distinguishes between nodes that are active and those that are merely informed.
As illustrated in the network above, a node becomes informed when any of its neighbors become active and attempt to activate it, even if the node itself remains inactive. The objective function, Weighted Information Coverage, calculates the expected number of active nodes plus a weighted fraction ($\lambda$) of informed nodes. By adjusting $\lambda$, practitioners can prioritize either deep engagement ($\lambda=0$) or broad awareness ($\lambda=1$).
Theoretical Analysis
The transition from counting only active nodes to including informed nodes introduces significant complexity. The authors provide several key theoretical proofs:
- Complexity: Finding the optimal seed set is NP-hard, and calculating exact coverage is #P-hard under both Independent Cascade (IC) and Linear Threshold (LT) models.
- Submodularity: Crucially, the objective function is proven to be submodular. This "law of diminishing returns" property is vital for optimization because it ensures that a greedy approach can achieve a solution within a guaranteed bound (at least 63%) of the optimal result.
Proposed Algorithms
To address the computational challenges of large-scale networks, two algorithms are introduced:
- Lazy-Forward Greedy Algorithm: This optimizes the standard greedy search by using "lazy evaluation" to skip redundant calculations. It maintains high-quality results and theoretical guarantees while significantly improving speed over standard Monte Carlo simulations.
- Effective Degree Rank Algorithm: A faster heuristic designed for massive networks. It selects seeds based on their "effective" out-degree, dynamically updating as neighbors become informed to minimize redundant coverage and avoid "over-covering" the same clusters.
Experimental Evaluation
The algorithms were evaluated using three real-world datasets representing diverse social interactions. The results indicate that:
- Performance: The proposed algorithms consistently outperform traditional IM techniques when the goal includes awareness. Using traditional IM algorithms for awareness-based campaigns was shown to be sub-optimal.
- Efficiency: While the Lazy-Forward approach provides high-quality results, the Effective Degree Rank algorithm scales linearly with network size ($O(k(n+m))$), making it highly suitable for massive social graphs.
Conclusion
By distinguishing between active and informed states, this research provides a more nuanced metric for information reach. The Information Coverage Maximization framework allows for a flexible trade-off between action and awareness, offering a more realistic model for modern communication strategies. Future work may explore multi-level awareness or temporal decay in information spread, as well as methods for practitioners to determine the optimal weight for awareness in specific business contexts.
Summary updated