PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing spread dynamics on graphs by message passing

Fabrizio Altarelli, Alfredo Braunstein, Luca Dall'Asta, Riccardo Zecchina

arXiv:1203.1426v2cond-mat.dis-nncs.SImath.OC

TL;DR

Optimizing initial conditions for irreversible network cascades is difficult beyond submodular models, where greedy approximation is available. The paper maps cascade trajectories to activation-time constraints and develops a statistical-physics message-passing algorithm. On generated graphs and the Epinions network, the method efficiently finds competitive low-cost, high-spread solutions, while its near-optimality depends on graph structure.

  • Problem

    Optimizing seed sets for irreversible cascades is generally difficult, and greedy approximation applies only to submodular models that exclude cooperative effects.

    Source: §I · p. 2

  • Method

    The paper represents cascade trajectories by activation times and uses cavity-based belief propagation followed by zero-temperature Max-Sum optimization.

    Source: A. Mapping on a… · pp. 3–4

  • Results

    On random graphs, MS solves instances with N = 1 000 and M = 102 400 in less than 1 minute, whereas SA requires several hours and finds more than 400 seeds versus 386 for MS.

    Source: A. Validation of the algorithm on… · p. 9

  • Takeaways & Limitations

    The approach efficiently optimizes spread on large networks and identifies cooperative seed sets with lower cost than competing methods in the Epinions network.

    Source: §I · p. 2, B. Spread maximization in a social… · p. 11

Abstract

from arXiv · show

Cascade processes are responsible for many important phenomena in natural and social sciences. Simple models of irreversible dynamics on graphs, in which nodes activate depending on the state of their neighbors, have been successfully applied to describe cascades in a large variety of contexts. Over the last decades, many efforts have been devoted to understand the typical behaviour of the cascades arising from initial conditions extracted at random from some given ensemble. However, the problem of optimizing the trajectory of the system, i.e. of identifying appropriate initial conditions to maximize (or minimize) the final number of active nodes, is still considered to be practically intractable, with the only exception of models that satisfy a sort of diminishing returns property called submodularity. Submodular models can be approximately solved by means of greedy strategies, but by definition they lack cooperative characteristics which are fundamental in many real systems. Here we introduce an efficient algorithm based on statistical physics for the optimization of trajectories in cascade processes on graphs. We show that for a wide class of irreversible dynamics, even in the absence of submodularity, the spread optimization problem can be solved efficiently on large networks. Analytic and algorithmic results on random graphs are complemented by the solution of the spread maximization problem on a real-world network (the Epinions consumer reviews network).

I. INTRODUCTION

The paper frames spread optimization as a difficult control problem, reviews submodularity-based approaches, defines deterministic Linear Threshold dynamics, and maps trajectories to an energy-weighted constraint-satisfaction formulation.

I. INTRODUCTION

  • Irreversible spreading processes model phenomena including innovation diffusion, epidemics, cascade failures, neural avalanches, and financial distress, but selecting initial conditions for desired outcomes is generally computationally intractable.The optimization is practically important for applications such as viral marketing, systemic-risk assessment, and failure prevention.Source: §I · p. 2
  • The proposed statistical-physics algorithm targets spread optimization on large graphs, with validation planned on generated graphs and the Epinions social network.The paper emphasizes that optimization performance depends on collective dynamics and cooperative effects.Source: §I · p. 2

A. Related Work

  • Greedy methods for independent-cascade and Linear Threshold models achieve a (1 −1/e) approximation under submodularity, but expected-spread evaluation is computationally expensive and difficult to scale.Exact expected-influence computation is #P-hard, while lazy-forward strategies reduce evaluations without resolving large-graph scalability.Source: A. Related Work · pp. 2–3
  • Deterministic Linear Threshold dynamics lack the submodularity property that supports those guarantees, making the problem hard even to approximate in the worst case.The model captures adoption when accumulated neighbor influence exceeds an individual threshold, with active nodes remaining active.Source: A. Related Work · p. 3, B. The Linear Threshold model · p. 3

A. Mapping on a Constraint-Satisfaction Problem

  • Each Linear Threshold trajectory is represented by node activation times, constrained so that every node activates at the earliest time when active-neighbor weight reaches its threshold.Seeds have activation time 0, while nodes that do not activate by the stopping time receive activation time ∞.Source: A. Mapping on a… · pp. 3–4
  • An energy function assigns probabilistic weights to admissible trajectories, and the zero-temperature limit selects minimum-energy trajectories balancing seed costs against revenues from activated nodes.The stopping time T also controls a speed-versus-energy trade-off, while spread maximization minimizes E(t) = Σ_i {c_i1[t_i = 0] − r_i1[t_i < ∞]}.Source: A. Mapping on a… · p. 4

B. Derivation of the Belief-Propagation equations

The belief-propagation formulation converts the activation-time constraint system into a locally factorized graphical model and uses cavity marginals to characterize atypical trajectories. A dual factor graph removes systematic short loops before iterative message updates are applied.

B. Derivation of the Belief-Propagation equations

  • The activation-time model supports efficient message passing by representing dynamics as a static constraint-satisfaction problem over discrete variables.The factor nodes encode dynamical constraints and energetic contributions.Source: B. Derivation of the… · p. 4
  • The zero-temperature limit of belief propagation yields Max-Sum equations for explicitly identifying minimum-energy seed configurations.Finite-temperature BP analyzes large deviations, whereas β →∞ is used for optimization.Source: B. Derivation of the… · pp. 4–5
  • Belief propagation computes marginals under a correlation-decay assumption, which is exact on trees and approximately valid on locally tree-like graphs.The assumption treats variables separated by a removed factor as decorrelated.Source: B. Derivation of the… · p. 4
  • Because neighboring dynamical constraints share activation-time variables and create short loops, the method uses a dual factor graph with pair variables on original edges and constraint factors on original vertices.This construction is illustrated by Figure 1 in the supplied passages.Source: B. Derivation of the… · p. 4
  • Cavity marginals are iterated to a fixed point, after which full node and edge marginals describe activation-time statistics and atypical trajectories.The resulting quantities can characterize trajectory entropies and activation-time distributions.Source: B. Derivation of the… · pp. 4–5

C. Derivation of the Max-Sum equations

The Max-Sum derivation takes the zero-temperature limit of the belief-propagation messages and expresses each message as an energy-adjusted constrained maximization. Normalization fixes additive message constants without changing the selected optimum.

C. Derivation of the Max-Sum equations

  • Max-Sum messages are defined from belief-propagation messages by replacing finite-temperature aggregation with a constrained maximization over neighboring activation times.The message includes the local energy contribution and excludes the recipient neighbor from the maximization.Source: C. Derivation of the Max-Sum equations · p. 5
  • The additive constant C_iℓ is chosen so every message is normalized with maximum value zero.This fixes the gauge of the messages while preserving their relative values.Source: C. Derivation of the Max-Sum equations · p. 5
  • When t_i = 0, the maximization is unconstrained and therefore reduces to a simplified expression.Source: C. Derivation of the Max-Sum equations · p. 5

D. Efficient computation of the MS updates

The efficient implementation relaxes one timing constraint without changing the ground states under positive costs and revenues, then uses convolution-based dynamic programming to accelerate message updates. This reduces the update cost to linear in node connectivity for the relevant convolution.

D. Efficient computation of the MS updates

  • Dropping the second timing constraint permits delayed activation after a threshold is exceeded, but positive costs and revenues ensure the relaxed and original problems have the same ground states.For a fixed seed set, the original trajectory energy is no greater than that of any compatible relaxed trajectory.Source: D. Efficient computation of the MS… · p. 6
  • Convolution functions combine partial threshold contributions recursively, replacing exponential update computation with a dynamic-programming procedure.The convolution splits a target threshold between two partial neighborhoods.Source: D. Efficient computation of the MS… · p. 6
  • The convolution property computes q_∂i\ℓ in time linear in the connectivity of node i.This addresses the otherwise prohibitive dependence of message updates on node degree.Source: D. Efficient computation of the MS… · p. 6
  • The same efficient-update strategy is applied to the complementary Max-Sum update, whose cases depend on the threshold contribution and neighboring activation times.The supplied derivation introduces the corresponding functions before rewriting the update.Source: D. Efficient computation of the MS… · pp. 6–7

E. Simplification of the MS messages

The MS messages are compressed by exploiting their limited dependence on neighboring activation times, reducing the representation from quadratic to linear in the propagation duration.

E. Simplification of the MS messages

  • The message dependence on neighboring activation time is reduced to a three-state sign or indicator condition determined by the receiving node’s activation time.For ti = 0, messages are independent of tℓ; for 0 < ti ≤ T, they depend on sign(tℓ − (ti − 1)); for ti = ∞, they depend on 1[tℓ < T].Source: E. Simplification of the MS messages · p. 7
  • The transformed messages encode only three cases for σ, selecting shifted, current-time, or infeasible original-message values.The cases use hiℓ(ti, ti − 2), hiℓ(ti, ti − 1), and hiℓ(ti, ti), with −∞ otherwise.Source: E. Simplification of the MS messages · p. 7
  • The simplification reduces the number of messages per node from O(T^2) to O(T).The subsequent update equations are rewritten in terms of the new messages.Source: E. Simplification of the MS messages · p. 7

F. Time complexity of the updates

The update implementation uses convolutional precomputation to reduce per-vertex work, while reinforcement addresses nonconvergent MS equations through a gradually increasing external field.

F. Time complexity of the updates

  • Precomputing prefix and suffix convolutions saves a factor k − 1 in the update cost for a vertex of degree k.The cavity convolution is then obtained by combining the precomputed contributions on either side of the excluded neighbor.Source: F. Time complexity of the updates · p. 8

G. Convergence and reinforcement

  • Reinforcement adds an external field proportional to the instantaneous local field when MS equations fail to converge.The field increases gradually to guide the system toward a simpler convergent problem without, hopefully, substantially altering the true optimum.Source: G. Convergence and reinforcement · p. 8
  • With λτ = γτ, the iteration count scales roughly as γ^-1, whereas the energy of the solution increases with γ.The unmodified MS equations correspond to γ = 0.Source: G. Convergence and reinforcement · p. 8

IV. RESULTS

MS is evaluated against alternative optimization methods on homogeneous random regular graphs and tested on loopy two-dimensional lattices, where it remains effective despite the cavity approximation’s limitations.

A. Validation of the algorithm on computer-generated graphs

  • The random-graph validation uses homogeneous regular instances with identical costs and revenues to compare methods without extra topological information or ad hoc seeding heuristics.The observables are seed density rather than total cost or revenue, enabling comparisons across parameter choices.Source: A. Validation of the algorithm on… · p. 8
  • MS outperforms the greedy algorithm by finding solutions with about 25% fewer seeds, while linear/integer programming becomes impractical beyond graphs of a few dozen nodes.SA is slower than both GA and MS, and its time to reach the MS solution scales poorly with system size.Source: A. Validation of the algorithm on… · p. 8
  • For N = 1000, MS finds a full-spread solution with 386 seeds, while the best simulated-annealing solutions use more than 400 seeds and take several hours versus under 1 minute for MS.The SA–MS seed-density gap decreases only with an exponentially slow annealing convergence, and GA results lie outside the plotted scale.Source: A. Validation of the algorithm on… · pp. 8–9, Figure 2 · p. 9
  • On 100 × 100 lattices, reinforced MS produces seed densities 0.5210 for hexagonal and 0.3536 for rectangular coordination structures.These configurations use K = 6, θ = 5, T = 20 and K = 4, θ = 3, T = 15, respectively, with open boundaries.Source: A. Validation of the algorithm on… · p. 9, Figure 3 · p. 10
  • The lattice results are good despite the cavity approximation not being asymptotically exact on lattices.For comparison, infinite-size, infinite-duration constructions have seed densities 1/2 on the hexagonal lattice and 1/3 on the square lattice.Source: A. Validation of the algorithm on… · p. 9
  • The algorithm is expected to be close to optimal on locally tree-like random regular graphs, but no near-optimality guarantee is available on loopy real networks.Short loops violate the decorrelation conditions underlying the cavity approximation, even when the MS equations converge.Source: A. Validation of the algorithm on… · p. 9

B. Spread maximization in a social network

On Epinions, message passing identifies cooperative seed sets that achieve high activation with lower cost than comparison methods, while exposing the limits of greedy optimization in a non-submodular cascade.

B. Spread maximization in a social network

  • Figure 4 compares MS with GA, HITS, Hubs, and SA using seed cost ci = µ(kin_i), with activation and propagation plotted across costs and time.The figure includes MS results for T from 10 to 40 and activation-time distributions for representative solutions.Source: B. Spread maximization in a social… · pp. 10–11, Figure 4 · p. 11
  • At T = 40, MS costs about 33% less than simulated annealing, while for larger T its cost decreases and the number of activated nodes increases.If propagation continues for T > 40, only a small number of additional nodes activate.Source: B. Spread maximization in a social… · p. 11
  • MS finds many scarcely influential seeds whose cooperation initiates a large avalanche: about 35 times more seeds than Hubs at one point, but at one-third the cost.The corresponding activation-time distributions are bimodal, indicating an initial burst followed by slower propagation and renewed acceleration.Source: B. Spread maximization in a social… · p. 11

C. Role of Submodularity

  • Greedy methods are poorly suited to this network because cooperative threshold effects violate submodularity and can produce abrupt large-scale activation after adding one seed.The model permits marginal gains to increase with seed-set size as nodes approach, but do not cross, their thresholds.Source: C. Role of Submodularity · pp. 11–12

V. SUMMARY AND CONCLUSIONS

  • The paper presents a cavity-method approach that identifies seed sets maximizing objectives dependent on node activation times for irreversible network dynamics.The authors propose extensions to stochastic irreversible models, including Independent Cascades, stochastic-threshold LT, and SIR models.Source: §V · p. 12

Appendix A: Efficient update equations for BP

The appendix simplifies belief-propagation updates by exploiting constraints among incoming messages and aggregating them through convolution-based quantities.

  • For positive edge weights, the second condition in the relevant sum implies the first, enabling a simplification of the update equations.Source: Appendix A · p. 12
  • Incoming messages and weights are relabeled from 1 to r, after which single-index Qj and Q′j quantities follow directly from their definitions.Source: Appendix A · p. 13
  • Convolving the incoming Q or Q′ quantities computes Q(θ, t) and Q′(θ, t), which are then used to obtain the corresponding message updates.Source: Appendix A · p. 13
  • The analogous S quantity is introduced and computed across incoming edges before evaluating the remaining update expression.Source: Appendix A · p. 13
  • The dependence of Hiℓ on the neighboring activation time tℓ is simplified because it is trivial or absent in several ti and sign cases.Source: Appendix A · p. 13
  • The transformed quantities can be inverted, allowing the appendix’s alternative update forms to be recovered from the preceding definitions.Source: Appendix A · pp. 13–14

1. Linear Programming Algorithm

The evaluation contrasts exact linear-programming formulations with greedy baselines, finding that linear programming is impractical on modest graphs while greedy choices differ in speed and solution quality.

1. Linear Programming Algorithm

  • Both tested linear-programming formulations become computationally impractical for graphs of only a few dozen nodes.The formulations use IBM’s CPLEX software and differ in their representation of dynamical constraints and activation ordering.Source: §1 · p. 14

2. Greedy Algorithms

  • Greedy algorithms add one seed at a time using preferences based on marginal spread, energy variation, or network topology.The evaluated preferences include GA, Hubs, and HITS centrality.Source: §2 · p. 14
  • At each step, the selected node triggers propagation, preferences are recomputed, and a linear seed-prize term incorporates seed costs.The linear coefficient is tuned for overall performance.Source: §2 · p. 14

3. Simulated Annealing

Simulated annealing optimizes seed configurations by explicitly propagating the cascade, but each move remains costly on large graphs. On Epinions, initialization strongly affects performance, while SA remains inferior to Max-Sum and can become trapped in local minima.

3. Simulated Annealing

  • Each Monte Carlo seed-change move requires at most O(|E|) operations, making SA computationally demanding on large graphs.The optimized propagation tracks only newly activated-node sets rather than updating all nodes in parallel.Source: §3 · pp. 14–15
  • Accurate initial seed selection sometimes considerably improves SA performance, whereas linear and exponential annealing schedules show no relevant difference.This sensitivity is especially important when topology and cost or revenue values are nonuniform and correlated.Source: §3 · p. 15

Appendix C: Simulated Annealing on the Epinions graph

  • On Epinions, a single Monte Carlo sweep can take several hours, forcing fast schedules reaching βfin = 10^3 in O(10^7) proposed moves.The graph has approximately 76,000 nodes and 500,000 edges.Source: Appendix C · p. 15
  • E = −36 297 was the lowest SA energy on Epinions, compared with E = −42 465 for Max-Sum at µ = 0.3.The comparison used configurations starting from 166 hub-selected seeds and different βin values.Source: Appendix C · p. 15
  • At low temperatures, SA gets trapped in local energy minima, with single-seed energy changes spanning almost five orders of magnitude.Such variation produces extremely different move-acceptance rates at the same temperature, complicating low-temperature optimization.Source: Appendix C · p. 15
Loading 1203.1426v2…