Negative-Aware Influence Maximization on Social Networks

Yipeng Chen, Hongyan Li, Qiang QuAAAI 2018 · DOI

Abstract

Traditional Influence Maximization (IM) aims to maximize the total number of influenced nodes in a social network. However, this approach often overlooks the potential negative impact of certain nodes, such as critics or non-contributing users. This paper proposes the Negative-aware Influence Maximization (NIM) framework, which seeks to maximize positive influence while actively minimizing negative reach. We introduce the RIS-NIM algorithm, which leverages Reverse Influence Sampling and iterative optimization to handle the non-submodular nature of the NIM objective. Experimental results on large-scale real-world datasets demonstrate that RIS-NIM significantly outperforms existing state-of-the-art IM algorithms, achieving up to a 70% improvement in net expected influence.

Introduction

Influence Maximization (IM) is a fundamental problem in social network analysis, primarily used for viral marketing to identify a small set of seed nodes that trigger the largest cascade of information or adoption. Conventional IM models assume all influenced nodes provide equal positive value. In reality, marketing campaigns often encounter "negative" nodes—users who might spread misinformation, possess poor credit, or consume resources without providing returns.

Accounting for these negative nodes transforms the optimization objective. Instead of a simple monotone submodular function, the NIM objective becomes the difference between two submodular functions. This loss of submodularity makes the problem NP-hard and renders standard greedy algorithms ineffective, as they cannot account for the penalties associated with negative influence.

Methodology

The authors propose RIS-NIM (Reverse Influence Set based algorithm for NIM) to address the computational challenges of the NIM problem.

Reverse Influence Sampling (RIS)

To efficiently estimate expected influence in large networks, RIS-NIM utilizes Reverse Influence Sampling. Instead of computationally expensive forward simulations, the algorithm samples random nodes and traverses the network backward to identify potential seed sets that could influence them.

Optimization via Modular-Modular Procedure

The NIM objective function is non-submodular, specifically represented as the difference between two submodular functions ($f(S) - g(S)$). To optimize this, the authors employ an iterative Modular-Modular procedure. By constructing tight upper and lower bounds for the submodular components, the algorithm iteratively refines the seed set $S$ to maximize the expected net influence. This approach allows the algorithm to navigate the complex search space where traditional greedy methods fail.

Experimental Setup

The performance of RIS-NIM was evaluated on four diverse real-world datasets from the Stanford Network Analysis Project (SNAP), ranging from small friendship networks to massive video-sharing platforms.

Table 1: Characteristics of the social network datasets used in the evaluation.

To simulate the NIM scenario, 50% of the nodes in each dataset were randomly assigned a "negative" label. The algorithms were tested under the Triggering Model, which generalizes the Independent Cascade and Linear Threshold models.

Results and Discussion

The RIS-NIM algorithm was compared against two prominent baselines: IMM (Influence Maximization via Martingales) and Degree Discount Greedy.

Figure 1: Comparison of expected net influence across four datasets for varying seed set sizes (k).

As shown in Figure 1, RIS-NIM consistently achieves the highest expected influence across all datasets. Notably, in the Hamsterster and BlogCatalog networks, the Degree baseline results in negative net influence as $k$ increases, indicating that it inadvertently targets a disproportionate number of negative nodes. While IMM maintains positive influence, it is significantly outperformed by RIS-NIM, which effectively avoids "negative traps" in the network topology. On average, RIS-NIM provides a 70% improvement in net influence over its competitors.

Furthermore, the results on the YouTube dataset (containing over 1 million nodes) demonstrate that RIS-NIM is highly scalable and suitable for industrial-scale social networks.

Conclusion

The Negative-aware Influence Maximization framework addresses a critical gap in social network strategy by prioritizing the quality of influence over mere quantity. By treating the objective as a difference of submodular functions and employing RIS-based optimization, the RIS-NIM algorithm provides a robust solution for complex, real-world marketing scenarios. Future work will focus on establishing tighter theoretical approximation bounds and exploring dynamic node labeling where user sentiment may evolve during the diffusion process.

Summary updated

BibTeX
@inproceedings{chen2018negative,
  author = {Yipeng Chen and Hongyan Li and Qiang Qu},
  title = {{Negative-Aware Influence Maximization on Social Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12149},
}
Figure