Signed-PageRank: Leveraging Friends and Foes for Optimal Information Diffusion

TL;DR

In social networks, we don't just have friends; we have rivals, critics, and foes. While traditional viral marketing treats all links as positive conduits, this paper introduces Signed-PageRank (SPR)—a framework that acknowledges that a recommendation from a "foe" might actually turn you off a product. By mathematically modeling these negative influences, SPR selects seed nodes that propagate information 20% more effectively than traditional unsigned methods.

Contextual Positioning

Influence Maximization (IM) has been a SOTA battleground since Kempe et al. proved it NP-hard in 2003. Most work focuses on "Infection" (unsigned). This paper moves the needle into the Signed Social Network (SSN) domain, where edges carry a +1 or -1 polarity. It sits at the intersection of PageRank-style graph centrality and DeGroot-style opinion dynamics.

The "Parallel Recommendation" Bottleneck

Previous attempts at SSN influence often failed because they couldn't handle the "Parallel Recommendation" dilemma: If two friends tell you to buy a phone, but one enemy tells you it's great, what do you do?

Existing models either ignored the enemy or simply subtracted the influence. The authors' insight is that your internal Belief ($x_{i,t}$) is a dynamic variable influenced by your Embeddedness—the ratio of friends to foes in your local neighborhood.

Methodology: The SPR Architecture

The framework consists of two core components: a dynamic belief update rule and a global ranking algorithm.

1. Belief Update with Polarization

Instead of a simple binary state (Infected/Susceptible), users have a belief score in $[0,1]$.

• Positive Update: Belief moves toward the friend's opinion.
• Negative Update: Belief moves away from the foe's opinion.

The intensity of this shift is governed by ${\alpha }_i$ (positive embeddedness) and ${\beta }_i$ (negative embeddedness).

2. The Signed-PageRank (SPR) Algorithm

Traditional PageRank relies on a transition matrix $F$. SPR replaces this with a Signed-Adjacency Matrix $Y$, derived from the Hadamard product of weights $W$ and labels $L$: $\mathbf{Y}=d\cdot (\tilde{\mathbf{W}}\ast \mathbf{L})$

Figure 1: The dual-nature of propagation where red nodes (seeds) affect neighbors based on signed edges.

Experimental Performance

The authors tested SPR against five benchmarks (including weighted degree and personalized ranking) on synthetic networks and real datasets like Epinions (20k nodes).

Key Findings:

• Superior Coverage: SPR consistently reached more "infected" users. Even if it starts slower in the first few rounds, its growth curve is significantly steeper.
• Computational Efficiency: Because SPR relies on matrix operations rather than the recursive simulations used in Greedy algorithms, it is highly scalable.

Figure 2: SPR (Red line) showing higher infection counts across different seed sizes (k) compared to P+, SRWR, and SVIM.

Critical Insight: Why Foes Matter

The most striking takeaway is that "well-connected" users are not always good seeds. In a signed network, a user with 1,000 links might be a "villain" (900 negative links). Traditional PageRank would mistakenly rank them as highly influential. SPR corrects this by devaluing nodes whose influence is primarily negative, ensuring the initial energy of the marketing campaign isn't "canceled out" by social friction.

Conclusion & Future Work

The SPR framework proves that in the real world—where digital polarization is high—ignoring negative sentiment is a recipe for inefficient marketing.

Limitations: The model assumes edge signs are static. In reality, a persistent recommendation from a foe might eventually "wear down" a user's resistance or even flip the sign of the relationship. Integrating Signed Link Evolution with Influence Maximization is the logical next frontier for this research.