Optimizing spread dynamics on graphs by message passing

Abstract

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).

Replacement for "The Spread Optimization Problem"

References in corpus (6)

• Finding undetected protein associations in cell signaling by belief propagation
• Large deviations of cascade processes on graphs
• Statistical Mechanics of Steiner trees
• Spreading dynamics on spatially constrained complex brain networks
• On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
• Stochastic optimization by message passing

Cited by in corpus (46)

• Influence maximization in complex networks through optimal percolation
• Vital nodes identification in complex networks
• Robustness and resilience of complex networks
• Unification of theoretical approaches for epidemic spreading on complex networks
• Network dismantling
• Spreading dynamics in complex networks
• Bayesian inference of epidemics on networks via Belief Propagation
• Identifying optimal targets of network attack by belief propagation
• Fast and simple decycling and dismantling of networks
• Containing epidemic outbreaks by message-passing techniques
• A message-passing approach for recurrent-state epidemic models on networks
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• Leveraging percolation theory to single out influential spreaders in networks
• Dynamic message-passing equations for models with unidirectional dynamics
• Efficient collective influence maximization in cascading processes with first-order transitions
• Fundamental difference between superblockers and superspreaders in networks
• Statistical Mechanics of the Minimum Dominating Set Problem
• Minimal contagious sets in random regular graphs
• Targeted Damage to Interdependent Networks
• The zero-patient problem with noisy observations
• Epidemic mitigation by statistical inference from contact tracing data
• Network reconstruction from infection cascades
• Rewiring the network. What helps an innovation to diffuse?
• A Bayesian generative neural network framework for epidemic inference problems
• The large deviations of the whitening process in random constraint satisfaction problems
• A Cavity Master Equation for the continuous time dynamics of discrete spins models
• A Max-Sum algorithm for training discrete neural networks
• On Minimal Sets to Destroy the $k$-Core in Random Networks
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• Influence Maximization for Fixed Heterogeneous Thresholds
• Heterogeneous message passing for heterogeneous networks
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Dynamical Phase Transitions in Graph Cellular Automata
• Backtracking Dynamical Cavity Method
• Spin glass phase transitions in the random feedback vertex set problem
• Hierarchical cycle-tree packing model for $K$-core attack problem
• Predicting epidemic evolution on contact networks from partial observations
• Feedback arcs and node hierarchy in directed networks
• Statics and dynamics of selfish interactions in distributed service systems
• Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference
• A closure for the Master Equation starting from the Dynamic Cavity Method
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm
• Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks