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