Uncovering the non-equilibrium stationary properties in sparse Boolean networks

Abstract

Dynamic processes of interacting units on a network are out of equilibrium in general. In the case of a directed tree, the dynamic cavity method provides an efficient tool that characterises the dynamic trajectory of the process for the linear threshold model. However, because of the computational complexity of the method, the analysis has been limited to systems where the largest number of neighbours is small. We devise an efficient implementation of the dynamic cavity method which substantially reduces the computational complexity of the method for systems with discrete couplings. Our approach opens up the possibility to investigate the dynamic properties of networks with fat-tailed degree distribution. We exploit this new implementation to study properties of the non-equilibrium steady-state. We extend the dynamical cavity approach to calculate the pairwise correlations induced by different motifs in the network. Our results suggest that just two basic motifs of the network are able to accurately describe the entire statistics of observed correlations. Finally, we investigate models defined on networks containing bi-directional interactions. We observe that the stationary state associated with networks with symmetric or anti-symmetric interactions is biased towards the active or inactive state respectively, even if independent interaction entries are drawn from a symmetric distribution. This phenomenon, which can be regarded as a form of spontaneous symmetry-breaking, is peculiar to systems formulated in terms of Boolean variables, as opposed to Ising spins.

References in corpus (39)

• Statistical mechanics of complex networks
• Direct-coupling analysis of residue co-evolution captures native contacts across many protein families
• Networks beyond pairwise interactions: structure and dynamics
• Emergence of Cooperation and Organization in an Evolutionary Game
• The Bethe lattice spin glass revisited
• A message passing approach for general epidemic models
• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Random hypergraphs and their applications
• High-accuracy approximation of binary-state dynamics on networks
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Simplicial Activity Driven Model
• Inferring interaction partners from protein sequences
• Expectation bubbles in a spin model of markets: Intermittency from frustration across scales
• Multitasking associative networks
• Message passing on networks with loops
• Exact solutions for diluted spin glasses and optimization problems
• Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms
• Optimizing spread dynamics on graphs by message passing
• Dynamical maximum entropy approach to flocking
• Dynamic message-passing equations for models with unidirectional dynamics
• Extensive load in multitasking associative networks
• Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
• Belief propagation for networks with loops
• Immune networks: multi-tasking capabilities near saturation
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• Dynamical TAP equations for non-equilibrium Ising spin glasses
• Dynamic mean-field and cavity methods for diluted Ising systems
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• A message-passing scheme for non-equilibrium stationary states
• Inference of kinetic Ising model on sparse graphs
• Heterogeneous micro-structure of percolation in sparse networks
• Phase Transitions in Operational Risk
• Dynamical systems on large networks with predator-prey interactions are stable and exhibit oscillations
• Effects of Economic Interactions on Credit Risk
• Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis
• Network resilience against intelligent attacks constrained by degree dependent node removal cost
• Replica methods for loopy sparse random graphs
• On the equivalence between the Kinetic Ising Model and discrete autoregressive processes
• Contagion in an interacting economy