Beyond Positive Vibes: Maximizing Negative Influence in Signed Social Networks

TL;DR

Most social network models assume everyone is a friend, but the real world is filled with "foes" and "distrust." This paper introduces the IC-P (Polarity Independent Cascade) model and two algorithms, CELF_NIM and MIA_NIM, to efficiently solve the problem of maximizing negative influence in signed networks. By acknowledging that not all interactions are positive, the authors provide a more realistic framework for viral marketing and opinion dynamics, achieving speeds up to 700x faster than traditional greedy approaches.

The "Friend-Only" Blind Spot

For years, Influence Maximization (IM) has been the "holy grail" of viral marketing. The logic was simple: find $k$ influential people to start a trend. However, these models (like the standard IC or LT models) viewed social graphs through rose-colored glasses, assuming only positive links exist.

In reality, social networks are signed graphs. A "negative" link—representing distrust or opposition—can completely flip the script. If you ignore these, you over-estimate positive reach and fail to account for how negative sentiment cascades. The challenge is that calculating this "Polarity" reach is computationally exhausting.

Methodology: The IC-P Model and Scalable Algorithms

1. The IC-P Diffusion Logic

The authors introduce a Quality Factor ($q$). When a node is activated:

• It becomes Positive with probability $q$.
• It becomes Negative with probability $1-q$.

If a node is "negatively activated," it exclusively spreads negative influence. This creates a more nuanced "tug-of-war" between brand advocates and critics.

2. CELF_NIM: Exploiting Submodularity

The authors prove that the negative influence function is submodular. This is a mathematical "cheat code": it means the marginal gain of adding a seed node decreases as the set grows. The CELF (Cost-Effective Lazy Forward) algorithm uses this property to skip calculating the influence of thousands of nodes that couldn't possibly be the "best" choice in a given round.

3. MIA_NIM: Trees instead of Graphs

For massive datasets, even CELF is too slow. The authors adapt the Maximum Influence Arborescence (MIA) heuristic. Instead of simulating the whole graph, they build local tree structures (arborescences) around nodes to approximate their reach.

The complexity of calculating activation probability (Equation 8) increases when $q<1$, requiring dynamic programming to account for the timing of neighbor activations.

Experiments: Performance & Real-world Intuition

The researchers tested their algorithms on the Slashdot (16K nodes) and Digg (12K nodes) datasets.

• Accuracy: CELF_NIM matched the performance of the brute-force Greedy algorithm perfectly.
• Efficiency: MIA_NIM and CELF-NIM provided orders of magnitude improvements in execution time.
• The Quality Factor: A fascinating takeaway was the linear relationship between product quality ($q$) and influence spread.

Fig 1: As seed size increases, the influence spread grows, but CELF-NIM accounts for the realistic dampening effects of negative polarity.

Final Insights

This paper serves as a vital reminder for Technical Product Managers and Data Scientists: Distrust is as contagious as trust.

While traditional models suggest that simply picking "popular" nodes is enough, ignoring the "signed" nature of relationships leads to significant errors. The shift from global graph simulations to local arborescence (MIA_NIM) provides the necessary bridge to apply these complex sociological theories to millions of users in real-time.

Limitations: The model assumes $q$ is uniform across the network. Future work should explore how $q$ varies by individual user "skepticism" levels.