Exact solution for statics and dynamics of maximal-entropy random walks on Cayley trees.

We provide analytical solutions for two types of random walk: generic random walk (GRW) and maximal-entropy random walk (MERW) on a Cayley tree with arbitrary branching number, root degree, and number of generations. For MERW, we obtain the stationary state given by the squared elements of the eigenvector associated with the largest eigenvalue λ(0) of the adjacency matrix. We discuss the dynamics, depending on the second largest eigenvalue λ(1), of the probability distribution approaching to the stationary state. We find different scaling of the relaxation time with the system size, which is generically shorter for MERW than for GRW. We also signal that depending on the initial conditions, there are relaxations associated with lower eigenvalues which are induced by symmetries of the tree. In general, we find that there are three regimes of a tree structure resulting in different statics and dynamics of MERW; these correspond to strongly, critically, and weakly branched roots.

Spectral relations between products and powers of isotropic random matrices.

We show that the limiting eigenvalue density of the product of n identically distributed random matrices from an isotropic unitary ensemble is equal to the eigenvalue density of nth power of a single matrix from this ensemble, in the limit when the size of the matrix tends to infinity. Using this observation, one can derive the limiting density of the product of n independent identically distributed non-Hermitian matrices with unitary invariant measures. In this paper we discuss two examples: the product of n Girko-Ginibre matrices and the product of n truncated unitary matrices. We also provide evidence that the result holds also for isotropic orthogonal ensembles.

Motifs emerge from function in model gene regulatory networks.

Gene regulatory networks allow the control of gene expression patterns in living cells. The study of network topology has revealed that certain subgraphs of interactions or "motifs" appear at anomalously high frequencies. We ask here whether this phenomenon may emerge because of the functions carried out by these networks. Given a framework for describing regulatory interactions and dynamics, we consider in the space of all regulatory networks those that have prescribed functional capabilities. Markov Chain Monte Carlo sampling is then used to determine how these functional networks lead to specific motif statistics in the interactions. In the case where the regulatory networks are constrained to exhibit multistability, we find a high frequency of gene pairs that are mutually inhibitory and self-activating. In contrast, networks constrained to have periodic gene expression patterns (mimicking for instance the cell cycle) have a high frequency of bifan-like motifs involving four genes with at least one activating and one inhibitory interaction.

Multiplication law and S transform for non-Hermitian random matrices.

We derive a multiplication law for free non-Hermitian random matrices allowing for an easy reconstruction of the two-dimensional eigenvalue distribution of the product ensemble from the characteristics of the individual ensembles. We define the corresponding non-Hermitian S transform being a natural generalization of the Voiculescu S transform. In addition, we extend the classical Hermitian S transform approach to deal with the situation when the random matrix ensemble factors have vanishing mean including the case when both of them are centered. We use planar diagrammatic techniques to derive these results.

Distribution of essential interactions in model gene regulatory networks under mutation-selection balance.

Gene regulatory networks typically have low in-degrees, whereby any given gene is regulated by few of the genes in the network. They also tend to have broad distributions for the out-degree. What mechanisms might be responsible for these degree distributions? Starting with an accepted framework of the binding of transcription factors to DNA, we consider a simple model of gene regulatory dynamics. There, we show that selection for a target expression pattern leads to the emergence of minimum connectivities compatible with the selective constraint. As a consequence, these gene networks have low in-degree and "functionality" is parsimonious, i.e., is concentrated on a sparse number of interactions as measured for instance by their essentiality. Furthermore, we find that mutations of the transcription factors drive the networks to have broad out-degrees. Finally, these classes of models are evolvable, i.e., significantly different genotypes can emerge gradually under mutation-selection balance.

Spectrum of the product of independent random Gaussian matrices.

We show that the eigenvalue density of a product X=X1X2...XM of M independent NxN Gaussian random matrices in the limit N-->infinity is rotationally symmetric in the complex plane and is given by a simple expression rho(z,z)=1/Mpisigma(-2/M)|z|(-2+(2/M)) for |z|sigma. The parameter sigma corresponds to the radius of the circular support and is related to the amplitude of the Gaussian fluctuations. This form of the eigenvalue density is highly universal. It is identical for products of Gaussian Hermitian, non-Hermitian, and real or complex random matrices. It does not change even if the matrices in the product are taken from different Gaussian ensembles. We present a self-contained derivation of this result using a planar diagrammatic technique. Additionally, we conjecture that this distribution also holds for any matrices whose elements are independent centered random variables with a finite variance or even more generally for matrices which fulfill Pastur-Lindeberg's condition. We provide a numerical evidence supporting this conjecture.

Eigenvalues and singular values of products of rectangular gaussian random matrices.

We derive exact analytic expressions for the distributions of eigenvalues and singular values for the product of an arbitrary number of independent rectangular gaussian random matrices in the limit of large matrix dimensions. We show that they both have power-law behavior at zero and determine the corresponding powers. We also propose a heuristic form of finite size corrections to these expressions which very well approximates the distributions for matrices of finite dimensions.

Localization of the maximal entropy random walk.

We define a new class of random walk processes which maximize entropy. This maximal entropy random walk is equivalent to generic random walk if it takes place on a regular lattice, but it is not if the underlying lattice is irregular. In particular, we consider a lattice with weak dilution. We show that the stationary probability of finding a particle performing maximal entropy random walk localizes in the largest nearly spherical region of the lattice which is free of defects. This localization phenomenon, which is purely classical in nature, is explained in terms of the Lifshitz states of a certain random operator.

Adaptive networks of trading agents.

Multiagent models have been used in many contexts to study generic collective behavior. Similarly, complex networks have become very popular because of the diversity of growth rules giving rise to scale-free behavior. Here we study adaptive networks where the agents trade "wealth" when they are linked together while links can appear and disappear according to the wealth of the corresponding agents; thus the agents influence the network dynamics and vice versa. Our framework generalizes a multiagent model of Bouchaud and Mézard [Physica A 282, 536 (2000)], and leads to a steady state with fluctuating connectivities. The system spontaneously self-organizes into a critical state where the wealth distribution has a fat tail and the network is scale free; in addition, network heterogeneities lead to enhanced wealth condensation.

Counting metastable states of Ising spin glasses on arbitrary graphs.

Using a field-theoretical representation of the Tanaka-Edwards integral, we develop a method to systematically compute the number Ns of one-spin stable states (local energy minima) of a glassy Ising system with nearest-neighbor interactions and random Gaussian couplings on an arbitrary graph. In particular, we use this method to determine Ns for K -regular random graphs and d -dimensional regular lattices for d=2,3 . The method works also for other graphs. Excellent accuracy of the results allows us to observe that the number of local energy minima depends mainly on local properties of the graph on which the spin glass is defined.

Condensation in zero-range processes on inhomogeneous networks.

We investigate the role of inhomogeneities in zero-range processes in condensation dynamics. We consider the dynamics of balls hopping between nodes of a network with one node of degree k_{1} much higher than a typical degree k , and find that the condensation is triggered by the inhomogeneity and that it depends on the ratio k_{1}k . Although, on the average, the condensate takes an extensive number of balls, its occupation can oscillate in a wide range. We show that in systems with strong inhomogeneity, the typical melting time of the condensate grows exponentially with the number of balls.

Balls-in-boxes condensation on networks.

We discuss two different regimes of condensate formation in zero-range processes on networks: on a q-regular network, where the condensate is formed as a result of a spontaneous symmetry breaking, and on an irregular network, where the symmetry of the partition function is explicitly broken. In the latter case we consider a minimal irregularity of the q-regular network introduced by a single Q node with degree Q>q. The statics and dynamics of the condensation depend on the parameter alpha=ln Q/q, which controls the exponential falloff of the distribution of particles on regular nodes and the typical time scale for melting of the condensate on the Q node, which increases exponentially with the system size N. This behavior is different than that on a q-regular network, where alpha=0 and where the condensation results from the spontaneous symmetry breaking of the partition function, which is invariant under a permutation of particle occupation numbers on the q nodes of the network. In this case the typical time scale for condensate melting is known to increase typically as a power of the system size.

Network of inherent structures in spin glasses: scaling and scale-free distributions.

The local minima (inherent structures) of a system and their associated transition links give rise to a network. Here we consider the topological and distance properties of such a network in the context of spin glasses. We use steepest descent dynamics, determining for each disorder sample the transition links appearing within a given barrier height. We find that differences between linked inherent structures are typically associated with local clusters of spins; we interpret this within a framework based on droplets in which the characteristic "length scale" grows with the barrier height. We also consider the network connectivity and the degrees of its nodes. Interestingly, for spin glasses based on random graphs, the degree distribution of the network of inherent structures exhibits a nontrivial scale-free tail.

From simple to complex networks: inherent structures, barriers, and valleys in the context of spin glasses.

Given discrete degrees of freedom (spins) on a graph interacting via an energy function, what can be said about the energy local minima and associated inherent structures? Using the lid algorithm in the context of a spin glass energy function, we investigate the properties of the energy landscape for a variety of graph topologies. First, we find that the multiplicity N(s) of the inherent structures generically has a log-normal distribution. In addition, the large volume limit of ln / differs from unity, except for the Sherrington-Kirkpatrick model. Second, we find simple scaling laws for the growth of the height of the energy barrier between the two degenerate ground states and the size of the associated valleys. For finite connectivity models, changing the topology of the underlying graph does not modify qualitatively the energy landscape, but at the quantitative level the models can differ substantially.

Perturbing general uncorrelated networks.

This paper is a direct continuation of an earlier work, where we studied Erdös-Rényi random graphs perturbed by an interaction Hamiltonian favoring the formation of short cycles. Here, we generalize these results. We keep the same interaction Hamiltonian but let it act on general graphs with uncorrelated nodes and an arbitrary given degree distribution. It is shown that the results obtained for Erdös-Rényi graphs are generic, at the qualitative level. However, scale-free graphs are an exception to this general rule and exhibit a singular behavior, studied thoroughly in this paper, both analytically and numerically.

Network transitivity and matrix models.

This paper is a step towards a systematic theory of the transitivity (clustering) phenomenon in random networks. A static framework is used, with adjacency matrix playing the role of the dynamical variable. Hence, our model is a matrix model, where matrices are random, but their elements take values 0 and 1 only. Confusion present in some papers where earlier attempts to incorporate transitivity in a similar framework have been made is hopefully dissipated. Inspired by more conventional matrix models, analytic techniques to develop a static model with nontrivial clustering are introduced. Computer simulations complete the analytic discussion.

Uncorrelated random networks.

We define a statistical ensemble of nondegenerate graphs, i.e., graphs without multiple-connections and self-connections between nodes. The node degree distribution is arbitrary, but the nodes are assumed to be uncorrelated. This completes our earlier publication [Phys. Rev. 64, 046118 (2001)] where trees and degenerate graphs were considered. An efficient algorithm generating nondegenerate graphs is constructed. The corresponding computer code is available on request. Finite-size effects in scale-free graphs, i.e., those where the tail of the degree distribution falls like n(-beta), are carefully studied. We find that in the absence of dynamical internode correlations the degree distribution is cut at a degree value scaling like N(gamma), with gamma=min[1/2,1/(beta-1)], where N is the total number of nodes. The consequence is that, independently of any specific model, the internode correlations seem to be a necessary ingredient of the physics of scale-free networks observed in nature.

Exotic trees.

We discuss the scaling properties of free branched polymers. The scaling behavior of the model is classified by the Hausdorff dimensions for the internal geometry, d(L) and d(H), and for the external one, D(L) and D(H). The dimensions d(H) and D(H) characterize the behavior for long distances, while d(L) and D(L) for short distances. We show that the internal Hausdorff dimension is d(L)=2 for generic and scale-free trees, contrary to d(H), which is known to be equal to 2 for generic trees and to vary between 2 and infinity for scale-free trees. We show that the external Hausdorff dimension D(H) is directly related to the internal one as D(H)=alphad(H), where alpha is the stability index of the embedding weights for the nearest-vertex interactions. The index is alpha=2 for weights from the Gaussian domain of attraction and 0

Tree networks with causal structure.

A geometry of networks endowed with a causal structure is discussed using the conventional framework of the equilibrium statistical mechanics. The popular growing network models appear as particular causal models. We focus on a class of tree graphs, an analytically solvable case. General formulas are derived, describing the degree distribution, the ancestor-descendant correlation, and the probability that a randomly chosen node lives at a given geodesic distance from the root. It is shown that the Hausdorff dimension d(H) of the causal networks is generically infinite, in contrast to the maximally random trees where it is generically finite.

Wealth condensation in pareto macroeconomies.

We discuss a Pareto macroeconomy (a) in a closed system with fixed total wealth and (b) in an open system with average mean wealth, and compare our results to a similar analysis in a super-open system (c) with unbounded wealth [J.-P. Bouchaud and M. Mézard, Physica A 282, 536 (2000)]. Wealth condensation takes place in the social phase for closed and open economies, while it occurs in the liberal phase for super-open economies. In the first two cases, the condensation is related to a mechanism known from the balls-in-boxes model, while in the last case, to the nonintegrable tails of the Pareto distribution. For a closed macroeconomy in the social phase, we point to the emergence of a "corruption" phenomenon: a sizeable fraction of the total wealth is always amassed by a single individual.