Optimizing spread dynamics on graphs by message passing
From MaRDI portal
Publication:3301689
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).
Recommendations
Cites work
- A simple model of global cascades on random networks
- Algorithmic Game Theory
- An analysis of approximations for maximizing submodular set functions—I
- Authoritative sources in a hyperlinked environment
- Combinatorial model and bounds for target set selection
- Contagion in financial networks
- Dynamical Processes on Complex Networks
- Information, Physics, and Computation
- Introduction to algorithms
- Network models and financial stability
- Systemic risk in financial systems
- The complexity of influence maximization problem in the deterministic linear threshold model
Cited in
(18)- Minimum Weight Dynamo and Fast Opinion Spreading
- The patient-zero problem with noisy observations
- The large deviations of the whitening process in random constraint satisfaction problems
- Rewiring the network. What helps an innovation to diffuse?
- Statistical mechanics of the minimum dominating set problem
- Influencer identification of threshold models in hypergraphs
- Hierarchical cycle-tree packing model for optimal \(K\)-core attack
- Scheduling a cascade with opposing influences
- A Max-Sum algorithm for training discrete neural networks
- Uncovering the non-equilibrium stationary properties in sparse Boolean networks
- Minimal contagious sets in random regular graphs
- A closure for the master equation starting from the dynamic cavity method
- A spin glass approach to the directed feedback vertex set problem
- How to schedule a cascade in an arbitrary graph
- An exact method for influence maximization based on deterministic linear threshold model
- Message Passing Optimization of Harmonic Influence Centrality
- Spreading dynamics in complex networks
- Structure-oriented prediction in complex networks
This page was built for publication: Optimizing spread dynamics on graphs by message passing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3301689)
