OSSUM±: Turning Foes into Followers in Competitive Signed Networks

TL;DR

In a world of "friends" and "foes," traditional marketing strategies fail. This paper presents OSSUM±, a mathematical framework that calculates how two competing opinions spread across signed networks. By strategically seeding both the "Red" and "Blue" opinions, this method maximizes influence in highly polarized environments better than any current SOTA baseline.

Problem & Motivation: The Logic of Distrust

Most social influence research assumes a "follower" mentality: if your friend buys a product, you might too. But what if your enemy buys it? Social science suggests you might actively avoid it.

Existing Influence Maximization (IM) algorithms typically ignore these negative edges (distrust). However, real-world networks like Epinions and Slashdot are rife with them. The authors identify two critical gaps:

1. Competing Cascades: Multiple products or ideologies spread at once.
2. Sign Interaction: Negative links aren't just "weak" links; they are "inverting" links. An enemy's adoption of Opinion A may push a node toward Opinion B.

The technical challenge is that in signed networks, the influence function is non-monotonic. Adding more seeds doesn't always increase spread—a unique hurdle that breaks traditional greedy approximation guarantees.

Methodology: The Math of "Reverse Psychology"

The authors extend the Unified Model (UM) of influence into a signed, competitive context.

1. Analytical Solution over Simulation

Instead of running 10,000 Monte Carlo simulations (which is #P-hard), they derived a recurrence relation to calculate the probability of a node $u$ being infected by Cascade+ (Red) or Cascade- (Blue) at any time $t$.

The key insight is the modification of Collective Influence:

• Positive Edge ($v\stackrel{+}{\to }u$): $v$ attempts to infect $u$ with its own color.
• Negative Edge ($v\stackrel{-}{\to }u$): $v$ attempts to infect $u$ with the opposite color.

2. The OSSUM± Heuristic

The algorithm, Online Seed-set Selection using Unified Model on Signed Networks (OSSUM±), iteratively selects the best (node, color) pair. Unlike previous work, it allows the algorithm to start with both colors to maximize the eventual spread of just one favored color.

Figure 1: Conceptual overview of competing cascades where infections flip polarity across dashed (negative) edges.

Experiments & Results

The authors tested OSSUM± against baselines like Positive Degree Discount and Effective Degree on large datasets (Epinions and Slashdot).

Key Findings:

• Distrust Dominance: In networks where negative links exceed 50%, OSSUM± outperforms competitors by a massive margin.
• Seed Diversity: As the fraction of negative links increases, the optimal strategy shifts from seeding "Red" nodes to seeding "Blue" nodes (counter-intuitively) to trigger "Red" infections further down the line.
• Scalability: The complexity remains linear with respect to edges and vertices, $O(m(|V|+|E|))$, allowing it to process networks with hundreds of thousands of nodes in seconds.

Figure 2: Performance comparison showing OSSUM± (red line) consistently achieving higher spread as seed set size $m$ increases in flipped (negative-dominated) networks.

Critical Analysis & Conclusion

Takeaway

The paper proves that in complex social networks, the "seed set portfolio" must be diversified. To maximize your reach, you must understand who your target distrusts and potentially leverage those negative relationships to your advantage.

Limitations

• Progressive Model: The assumption that nodes cannot change their mind (once infected, always infected) is a simplified view of social dynamics.
• Sign Knowledge: The model assumes we know which links are positive or negative, which is often "hidden" data in private networks.

Future Outlook

This work paves the way for "adversarial marketing" and better epidemiological models for interacting diseases where one virus might effectively "block" or "facilitate" another through complex biological signaling analogous to signed social links.