Information Coverage Maximization in Social Networks

Zhefeng Wang, Enhong Chen, Qi Liu, Yu Yang, Yong Ge, Biao Chang

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.

Distinction between seed, active, and informed nodes in the proposed Information Coverage Maximization framework.

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:

  1. 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.
  2. 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

Abstract

Social networks, due to their popularity, have been studied extensively these years. A rich body of these studies is related to influence maximization, which aims to select a set of seed nodes for maximizing the expected number of active nodes at the end of the process. However, the set of active nodes can not fully represent the true coverage of information propagation. A node may be informed of the information when any of its neighbours become active and try to activate it, though this node (namely informed node) is still inactive. Therefore, we need to consider both active nodes and informed nodes that are aware of the information when we study the coverage of information propagation in a network. Along this line, in this paper we propose a new problem called Information Coverage Maximization that aims to maximize the expected number of both active nodes and informed ones. After we prove that this problem is NP-hard and submodular in the independent cascade model and the linear threshold model, we design two algorithms to solve it. Extensive experiments on three real-world data sets demonstrate the performance of the proposed algorithms.
BibTeX
@inproceedings{wang2015information,
  author = {Zhefeng Wang and Enhong Chen and Qi Liu and Yu Yang and Yong Ge and Biao Chang},
  title = {{Information Coverage Maximization in Social Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure