Maximizing the Coverage of Information Propagation in Social Networks

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

Abstract

Traditional Influence Maximization (IM) focuses on "active" users who perform specific actions, often overlooking the broader "informed" audience. This paper proposes the Information Coverage Maximization (ICM) framework to account for both active and informed nodes. We prove that ICM is NP-hard yet submodular, allowing for efficient greedy approximations. Through the Lazy-Forward Greedy (LFG) algorithm and the Effective Degree Rank (EDR) heuristic, we demonstrate that accounting for informed users provides a more comprehensive measure of information spread, particularly in dense networks where informed users significantly outnumber active users.

Introduction

In viral marketing and social network analysis, the standard objective is Influence Maximization (IM): identifying a small set of "seed" nodes to trigger the maximum number of "active" nodes (adopters). However, this approach ignores a critical segment of the network: the "informed" users. For instance, in a microblogging campaign, many users may read a message without retweeting it. While these users are not "active," they are nonetheless aware of the information.

Illustration of seed, active, and informed nodes in a social network propagation model.

This paper introduces Information Coverage Maximization (ICM), defining "coverage" as the union of active and informed nodes. By treating informed users as distinct from inactive ones, ICM provides a more realistic metric for total campaign reach.

Methodology

The ICM problem is formalized under the Independent Cascade (IC) model. In this stochastic framework, active nodes have a single opportunity to activate their neighbors with a probability $p$.

Theoretical Foundations

The authors prove that maximizing information coverage is NP-hard. However, the objective function is shown to be submodular, exhibiting a "diminishing returns" property. This allows greedy algorithms to achieve a $(1 - 1/e)$ approximation of the optimal solution.

Algorithmic Solutions

  1. Lazy-Forward Greedy (LFG): An optimized greedy approach using Monte Carlo simulations. It employs a "Lazy Forward" strategy to skip redundant calculations for nodes unlikely to improve coverage, significantly reducing computational overhead.
  2. Effective Degree Rank (EDR): A fast heuristic designed for massive networks. EDR ranks nodes by out-degree but dynamically adjusts the score by subtracting neighbors likely to be covered by existing seeds.

Experimental Evaluation

The proposed methods were evaluated on three real-world datasets:

  • wiki-Vote: Wikipedia adminship voting network (7,115 nodes).
  • soc-Epinions1: Consumer review trust network (75,879 nodes).
  • weibo: A dense microblogging dataset (76,491 nodes, 9.5 million edges).

Key Insights: The Informed Majority

Empirical results highlight the disparity between active and informed nodes. In the Weibo dataset, a seed set of 20 nodes resulted in approximately 465 active nodes but over 66,000 informed nodes.

Ratio of active, informed, and other nodes across wiki-Vote, soc-Epinions1, and weibo datasets.

As shown in the figure above, the "informed" group constitutes the vast majority of the reached population. Ignoring this group leads to a significant underestimation of a campaign's true impact. Furthermore, the strategy for maximizing awareness (ICM) differs from maximizing conversion (IM), as evidenced by the low similarity between the seed sets selected by each model.

Results and Performance

  • Coverage Superiority: LFG and EDR consistently outperformed traditional IM algorithms like CELF and DegreeDiscount in total coverage across all datasets.
  • Efficiency: On the dense Weibo dataset, the EDR heuristic completed in just 23 seconds, compared to 183 hours for the greedy LFG, with minimal loss in coverage quality.
  • Robustness: The models remained effective even when informed nodes were assigned lower weights than active nodes, proving the framework's versatility for different marketing goals.

Conclusion

The ICM framework offers a more holistic view of information propagation by accounting for the silent majority of informed users. While greedy methods provide theoretical bounds, heuristics like EDR offer the scalability required for modern social networks. Future research may explore time-critical constraints and competitive propagation environments.

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{wang2015maximizing,
  author = {Zhefeng Wang and Enhong Chen and Qi Liu and Yu Yang and Yong Ge and Biao Chang},
  title = {{Maximizing the Coverage of Information Propagation in Social Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure