Source-linked AI summary
Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships
Yanhua Li, Wei Chen, Yajun Wang, Zhi-Li Zhang
TL;DR
Existing influence-diffusion research largely ignores foe relationships in online social networks. This paper extends the voter model to signed networks, characterizes short- and long-term opinion dynamics, and applies the analysis to influence maximization. The resulting algorithms are evaluated on synthetic and real-world networks, while convergence remains open for some graph classes.
Problem
Existing studies focus on friendship relations even though online social networks also contain foe, spite, or distrust relationships.
Method
The paper extends the voter model to weighted signed digraphs, analyzes short- and long-term dynamics, and develops algorithms for short- and long-term influence maximization.
Results
Steady-state opinion distributions depend on balanced, anti-balanced, and strictly unbalanced graph structures, while simulations demonstrate algorithmic efficacy over heuristic algorithms.
Takeaways & Limitations
Signed voter-model analysis supports influence maximization that accounts for both friend and foe relationships in social networks.
Takeaways & Limitations
Convergence time remains open for strictly unbalanced ergodic digraphs and more general weakly connected signed digraphs.
Abstract
from arXiv · showhide
Influence diffusion and influence maximization in large-scale online social networks (OSNs) have been extensively studied, because of their impacts on enabling effective online viral marketing. Existing studies focus on social networks with only friendship relations, whereas the foe or enemy relations that commonly exist in many OSNs, e.g., Epinions and Slashdot, are completely ignored. In this paper, we make the first attempt to investigate the influence diffusion and influence maximization in OSNs with both friend and foe relations, which are modeled using positive and negative edges on signed networks. In particular, we extend the classic voter model to signed networks and analyze the dynamics of influence diffusion of two opposite opinions. We first provide systematic characterization of both short-term and long-term dynamics of influence diffusion in this model, and illustrate that the steady state behaviors of the dynamics depend on three types of graph structures, which we refer to as balanced graphs, anti-balanced graphs, and strictly unbalanced graphs. We then apply our results to solve the influence maximization problem and develop efficient algorithms to select initial seeds of one opinion that maximize either its short-term influence coverage or long-term steady state influence coverage. Extensive simulation results on both synthetic and real-world networks, such as Epinions and Slashdot, confirm our theoretical analysis on influence diffusion dynamics, and demonstrate the efficacy of our influence maximization algorithm over other heuristic algorithms.
1 Introduction
The paper addresses influence diffusion and maximization in social networks containing both friend and foe relationships, extending voter-model analysis beyond positive ties. It characterizes short- and long-term dynamics, develops influence-maximization algorithms, and evaluates them on synthetic and real-world networks.
- 1 Introduction: Existing influence-maximization studies model positive relationships but omit foe, spite, and distrust ties present in networks such as Epinions and Slashdot.The paper frames signed networks as a way to represent both relationship types.
- 1 Introduction: The paper extends the classic voter model to signed networks, where two opposite opinions diffuse through friend and foe relationships.The voter model captures opinions that may switch based on interactions with other people.
- 1 Introduction: Steady-state opinion distributions depend on balanced, anti-balanced, or strictly unbalanced graph structures.The paper identifies anti-balanced graphs as a new class not previously covered by social balance theory.
- 1 Introduction: Influence maximization selects at most k initial white nodes to maximize expected white-node influence in either the short or long term.This models one opinion attempting to win supporters from an initially dominant alternative opinion.
- 1 Introduction: The study provides efficient influence-maximization algorithms and reports that they perform much better than other heuristic algorithms in simulations.Simulations cover both synthetic and real-world networks.
- 1 Introduction: The paper presents its signed-network voter-model study as the first to analyze influence diffusion and maximization with both friend and foe relations.It also claims to provide efficient algorithms for this setting.
2 Voter model for signed networks
The signed voter model represents trust and distrust with positive and negative weighted edges, using edge signs to determine whether opinions are copied or inverted. Its analysis assumes ergodic strongly connected components and extends long-term study to weakly connected or disconnected graphs with ergodic sink components.
- 2 Voter model for signed networks: A weighted digraph G = (V, E, A) uses adjacency entries Aij to encode directed-edge weights, with nodes holding black or white opinions.At each step, a node chooses an outgoing neighbor with probability proportional to the absolute edge weight.
- 2 Voter model for signed networks: Positive edges represent friendship or trust, while negative edges represent foe or distrust relationships; |Aij| measures relationship strength.The signed adjacency matrix decomposes as A = A+ − A−.
- 2 Voter model for signed networks: A node copies its selected neighbor’s opinion across a positive edge but adopts the opposite opinion across a negative edge.The neighbor is selected with probability proportional to |Aij|.
- 2 Voter model for signed networks: In the signed random-walk interpretation, an even number of negative edges preserves the starting opinion, whereas an odd number reverses it.This links opinion propagation to the parity of negative edges along the walk.
- 2 Voter model for signed networks: For long-term analysis, the paper assumes signed strongly connected components are ergodic, then considers ergodic graphs and weakly connected or disconnected graphs with ergodic sink components.A sink component has no outgoing edges to nodes outside the component.
3 Analysis of voter model dynamics on signed digraphs
The section derives short-term and long-term voter-model dynamics on signed digraphs, showing that convergence depends on structural balance and sink-component structure.
- 3.1 Short-term dynamics: The signed transition matrix provides the framework for analyzing opinion distributions at each step and their long-term limits.The analysis uses P = D^-1A and relates long-term behavior to limits of powers of P and their cumulative sums.
- 3.2 Structural balance: Signed digraphs are classified as balanced, anti-balanced, or strictly unbalanced according to the signs within and across a node partition.Balanced graphs have positive within-partition and negative cross-partition edges; anti-balanced graphs reverse these signs; the remaining graphs are strictly unbalanced.
- 3.2 Convergence: For ergodic signed digraphs, P^t converges in balanced and strictly unbalanced graphs, while its odd and even subsequences converge to opposite matrices in anti-balanced graphs.For strictly unbalanced graphs, the limiting matrix is zero, whereas anti-balanced graphs exhibit alternating long-term behavior.
- 3.3 Long-term dynamics: Balanced ergodic graphs converge with probability 1 to one of two polarized states, with each partition assigned opposite opinions.The probability of reaching a polarized state is determined by the signed stationary distribution and the initial white-color distribution.
- 3.3 Long-term dynamics: Anti-balanced graphs eventually oscillate between polarized states, whereas strictly unbalanced graphs give every node equal steady-state probabilities of black and white.For anti-balanced graphs, the even-step distribution matches the balanced counterpart and odd steps switch to its opposite.
- 3.3 Long-term dynamics: With one sink component, non-sink connectivity affects the final steady-state distribution even though the sink retains the polarized behavior of the ergodic case.Theorem 3 decomposes the long-term distribution into sink and non-sink components, whose contributions depend on the sink's balance structure.
4 Influence maximization
The paper formulates influence maximization for signed voter-model networks, distinguishing short-term instant and average objectives from long-term influence. It derives linear influence contributions and develops optimal seed-selection rules and SVIM algorithms whose long-term behavior depends on graph structure.
- Short-term objectives: Short-term objectives include instant influence at step t and average influence over the first t steps, capturing different application needs.Instant influence matches opinions counted at a specific time, whereas average influence reflects sustained influence over multiple steps.
- Influence contribution: Influence contribution subtracts the graph’s ground influence from the influence achieved by a selected white seed set.On signed digraphs, influence can be nonzero even without white seeds, so seed contribution excludes this baseline.
- Short-term maximization: Linearity makes optimal instant seed selection choose up to k nodes with the highest positive individual influence contributions.If fewer than k nodes have positive contributions, the optimal solution uses fewer seeds.
- Short-term maximization: SVIM-S computes short-term influence contributions using t vector-matrix multiplications and runs in O(t · |E|) time.The algorithm selects the top eligible nodes for instant or average influence maximization.
- Long-term maximization: For ergodic signed digraphs, long-term influence contribution is nonzero for balanced graphs but zero for anti-balanced and strictly unbalanced graphs.In balanced graphs, the contribution depends on the bipartition and stationary influence weights.
- Long-term maximization: Anti-balanced dynamics oscillate between odd and even steps, yet seed selection can maximize oscillation strength despite zero long-term influence contribution.For weakly connected graphs with a single anti-balanced sink component, the long-term average influence is |V|/2 and is invariant to initial seeds.
- General case and SVIM-L: In weakly connected graphs, balanced sink components require influence contributions for each sink node because connectivity to non-sink nodes complicates seed selection.SVIM-L addresses general aperiodic signed digraphs, with computation and selection depending on balance and connectedness.
5 Evaluation
Synthetic and real-network evaluations compare SVIM-S and SVIM-L with four heuristics, showing stronger short- and long-term influence results, including when edge signs are used.
- Synthetic datasets: The evaluation uses synthetic signed digraphs spanning balanced, anti-balanced, strictly unbalanced, weakly connected, and disconnected structures.The synthetic graphs are generated with unit-weight edges and multiple component configurations.
- Synthetic datasets: SVIM-L achieves the highest long-term influence on balanced ergodic graphs and outperforms heuristics on weakly connected and disconnected graphs.The comparisons use an influence budget of k = 500 and track average white nodes over time.
- Synthetic datasets: In strictly unbalanced graphs, all algorithms converge to 4750 = |V|/2, while anti-balanced graphs exhibit oscillating influence and equal average influence across algorithms.The strictly unbalanced result matches the stated theoretical steady-state characterization.
- Real datasets: SVIM-S consistently outperforms heuristics on Epinions and Slashdot for instant and average influence, with 16%–145% more influence at step 1 in one Epinions case.The Epinions evaluations use budgets of 500 and 6000 seeds, while the reported Slashdot results use k = 6000.
- Impacts of signed information: Considering edge signs improves influence over unsigned seed selection by 5%–16% in balanced synthetic graphs and 11.7%–58% in weakly connected synthetic graphs for t ≥6.On Epinions, sign-aware selection improves short-term influence by up to 38% on the full dataset and 21% on its largest SCC, while long-term influence is unchanged.
6 Conclusion
The paper studies voter-model dynamics and influence maximization on signed digraphs, characterizing short- and long-term behavior and developing efficient algorithms. It identifies anti-balanced digraphs as a distinct class with oscillating steady-state behavior, while convergence time remains open for strictly unbalanced and more general weakly connected graphs.
- The paper proposes voter-model dynamics on signed digraphs and applies them to short-term and long-term influence maximization.
- It provides rigorous mathematical characterizations of diffusion dynamics and efficient algorithms for both influence-maximization objectives.
- Anti-balanced digraphs form a newly identified class with oscillating steady-state behavior.
- Convergence time remains open for strictly unbalanced ergodic digraphs and more general weakly connected signed digraphs.For balanced and anti-balanced ergodic digraphs, convergence times match those of corresponding unsigned digraphs.
A Properties of ergodic digraphs
This section establishes structural and stationary-distribution properties of ergodic digraphs. It proves the existence of both even- and odd-length paths between any node pair and records a matrix-power identity involving the stationary distribution.
- Every node pair in an ergodic digraph has both an even-length path and an odd-length path connecting them.
- For an ergodic unsigned digraph, P̄^(t−1)π^T equals (P̄^−1π^T)^t for every integer t > 0.
B Special matrix power series
This section develops matrix power-series results under vanishing powers of two matrices. The results use spectral-radius and Jordan-form arguments to establish convergence-related algebraic properties and bounds.
- If X^t and Z^t converge to zero, then I−X and I−Z are invertible.The proof uses the fact that convergence of X^t to zero is equivalent to spectral radius ρ(X) < 1.
- The matrix-power analysis represents X through its standard Jordan form and bounds entries of its powers using eigenvalue multiplicities.
C Illustration of exponential convergence time of P t on ergodic digraph.
This illustration constructs an ergodic digraph whose random-walk convergence is exponentially slow. The argument uses the stationary distribution and bounds the probability of reaching the right-hand node set from an initial left-side node.
- Figure 23 presents an ergodic digraph with exponential convergence time and unit edge weights.
- The graph has symmetric stationary probabilities, with x(L1)=x(R1)=ρ/4 and x(Li)=x(Ri)=ρ/2^i for i=2,…,m.
- Starting from the leftmost node, the right-side set W can gain probability only through the edge from Lm to R1.
- The convergence bound requires t to be at least 2^(m−3) for the right-side probability to approach its stationary value within the stated tolerance.