Optimizing spread dynamics on graphs by message passing
From MaRDI portal
Publication:3301689
DOI10.1088/1742-5468/2013/09/P09011zbMATH Open1456.82420arXiv1203.1426WikidataQ61444405 ScholiaQ61444405MaRDI QIDQ3301689FDOQ3301689
Authors: Fabrizio Altarelli, Alfredo Braunstein, Luca Dall'Asta, Riccardo Zecchina 
Publication date: 11 August 2020
Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)
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).
Full work available at URL: https://arxiv.org/abs/1203.1426
Recommendations
Cites Work
- Introduction to algorithms
- Algorithmic Game Theory
- Authoritative sources in a hyperlinked environment
- Combinatorial model and bounds for target set selection
- Systemic risk in financial systems
- Dynamical Processes on Complex Networks
- An analysis of approximations for maximizing submodular set functions—I
- Information, Physics, and Computation
- Network models and financial stability
- Contagion in financial networks
- A simple model of global cascades on random networks
- The complexity of influence maximization problem in the deterministic linear threshold model
Cited In (18)
- A spin glass approach to the directed feedback vertex set problem
- Statistical mechanics of the minimum dominating set problem
- Hierarchical cycle-tree packing model for optimal \(K\)-core attack
- Message Passing Optimization of Harmonic Influence Centrality
- A Max-Sum algorithm for training discrete neural networks
- The patient-zero problem with noisy observations
- The large deviations of the whitening process in random constraint satisfaction problems
- Structure-oriented prediction in complex networks
- Influencer identification of threshold models in hypergraphs
- A closure for the master equation starting from the dynamic cavity method
- Rewiring the network. What helps an innovation to diffuse?
- Scheduling a cascade with opposing influences
- How to schedule a cascade in an arbitrary graph
- An exact method for influence maximization based on deterministic linear threshold model
- Minimal contagious sets in random regular graphs
- Minimum Weight Dynamo and Fast Opinion Spreading
- Spreading dynamics in complex networks
- Uncovering the non-equilibrium stationary properties in sparse Boolean 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)
