Constrained Markovian dynamics of random graphs

We introduce and apply a novel efficient method for the precise simulation of stochastic dynamical processes on locally tree-like graphs. Networks with cycles are treated in the framework of the cavity method. Such models correspond, for example, to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon ideas from quantum many-body theory, the new approach is based on a matrix product approximation of the ...

In this paper we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics. The Glauber dynamics is a Markov chain that sequentially updates individual nodes (variables) in a graphical model and it is frequently used to sample from the stationary distribution (to which it converges given sufficient time). Additionally, the Glauber dynamics is a natural dynamical model in a variety of settings. This work deviates from th...

Understanding common properties of different systems is a challenging task for interdisciplinary research. By representing these systems as complex networks, different fields facilitate their comparison. Common properties can then be extracted by network randomisation, in which a stochastic process preserves some properties of the network modifying others. If different systems exhibit statistically similar characteristics after being randomised by the same process, then these...

We present a statistical mechanics approach for the description of complex networks. We first define an energy and an entropy associated to a degree distribution which have a geometrical interpretation. Next we evaluate the distribution which extremize the free energy of the network. We find two important limiting cases: a scale-free degree distribution and a finite-scale degree distribution. The size of the space of allowed simple networks given these distribution is evaluat...

We study random walk with adaptive move strategies on a class of directed graphs with variable wiring diagram. The graphs are grown from the evolution rules compatible with the dynamics of the world-wide Web [Tadi\'c, Physica A {\bf 293}, 273 (2001)], and are characterized by a pair of power-law distributions of out- and in-degree for each value of the parameter $\beta$, which measures the degree of rewiring in the graph. The walker adapts its move strategy according to local...

We study a colored generalization of the famous simple-switch Markov chain for sampling the set of graphs with a fixed degree sequence. Here we consider the space of graphs with colored vertices, in which we fix the degree sequence and another statistic arising from the vertex coloring, and prove that the set can be connected with simple color-preserving switches or moves. These moves form a basis for defining an irreducible Markov chain necessary for testing statistical mode...

In this research paper, weighted / unweighted, directed / undirected graphs are associated with interesting Discrete Time Markov Chains (DTMCs) as well as Continuous Time Markov Chains (CTMCs). The equilibrium / transient behaviour of such Markov chains is studied. Also entropy dynamics (Shannon entropy) of certain structured Markov chains is investigated. Finally certain structured graphs and the associated Markov chains are studied.

We review the recent fast progress in statistical physics of evolving networks. Interest has focused mainly on the structural properties of random complex networks in communications, biology, social sciences and economics. A number of giant artificial networks of such a kind came into existence recently. This opens a wide field for the study of their topology, evolution, and complex processes occurring in them. Such networks possess a rich set of scaling properties. A number ...

Contrary to many recent models of growing networks, we present a model with fixed number of nodes and links, where it is introduced a dynamics favoring the formation of links between nodes with degree of connectivity as different as possible. By applying a local rewiring move, the network reaches equilibrium states assuming broad degree distributions, which have a power law form in an intermediate range of the parameters used. Interestingly, in the same range we find non-triv...

The unconstrained exponential family of random graphs assumes no prior knowledge of the graph before sampling, but it is natural to consider situations where partial information about the graph is known, for example the total number of edges. What does a typical random graph look like, if drawn from an exponential model subject to such constraints? Will there be a similar phase transition phenomenon (as one varies the parameters) as that which occurs in the unconstrained expo...