Can I read Optimizing Spread Dynamics on Graphs by Message Passing on EtoBox?

Optimizing Spread Dynamics on Graphs by Message Passing by Altarelli, Fabrizio; Braunstein, Alfredo; Dall'Asta, Luca; Zecchina, Riccardo is a scholarly article available to read on EtoBox.

What is Optimizing Spread Dynamics on Graphs by Message Passing about?

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 a

Author

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

Published

2012

Language

EN