Eigenvalue tunneling and decay of quenched random network

Free-energy density functional for Strauss's model of transitive networks

Ensemble models of graphs are one of the most important theoretical tools to study complex networks. Among them, exponential random graphs (ERGs) have proven to be very useful in the analysis of social networks. In this paper we develop a technique, borrowed from the statistical mechanics of lattice gases, to solve Strauss's model of transitive networks. This model was introduced long ago as an ERG ensemble for networks with high clustering and exhibits a first-order phase transition above a critical value of the triangle interaction parameter where two different kinds of networks with different densities of links (or, alternatively, different clustering) coexist. Compared to previous mean-field approaches, our method describes accurately even small networks and can be extended beyond Strauss's classical model-e.g., to networks with different types of nodes. This allows us to tackle, for instance, models with node homophily. We provide results for the latter and show that they accurately reproduce the outcome of Monte Carlo simulations.

Non-backtracking walks reveal compartments in sparse chromatin interaction networks

Chromatin communities stabilized by protein machinery play essential role in gene regulation and refine global polymeric folding of the chromatin fiber. However, treatment of these communities in the framework of the classical network theory (stochastic block model, SBM) does not take into account intrinsic linear connectivity of the chromatin loci. Here we propose the polymer block model, paving the way for community detection in polymer networks. On the basis of this new model we modify the non-backtracking flow operator and suggest the first protocol for annotation of compartmental domains in sparse single cell Hi-C matrices. In particular, we prove that our approach corresponds to the maximum entropy principle. The benchmark analyses demonstrates that the spectrum of the polymer non-backtracking operator resolves the true compartmental structure up to the theoretical detectability threshold, while all commonly used operators fail above it. We test various operators on real data and conclude that the sizes of the non-backtracking single cell domains are most close to the sizes of compartments from the population data. Moreover, the found domains clearly segregate in the gene density and correlate with the population compartmental mask, corroborating biological significance of our annotation of the chromatin compartmental domains in single cells Hi-C matrices.

Self-isolation or borders closing: What prevents the spread of the epidemic better?

Pandemic propagation of COVID-19 motivated us to discuss the impact of the human network clustering on epidemic spreading. Today, there are two clustering mechanisms which prevent of uncontrolled disease propagation in a connected network: an "internal" clustering, which mimics self-isolation (SI) in local naturally arranged communities, and an "external" clustering, which looks like a sharp frontiers closing (FC) between cities and countries, and which does not care about the natural connections of network agents. SI networks are "evolutionarily grown" under the condition of maximization of small cliques in the entire network, while FC networks are instantly created. Running the standard SIR model on clustered SI and FC networks, we demonstrate that the evolutionary grown clustered network prevents the spread of an epidemic better than the instantly clustered network with similar parameters. We find that SI networks have the scale-free property for the degree distribution P(k)∼k^{η}, with a small critical exponent -2<η<-1. We argue that the scale-free behavior emerges as a result of the randomness in the initial degree distributions.

Spectral peculiarity and criticality of a human connectome

We have performed the comparative spectral analysis of structural connectomes for various organisms using open-access data. Our results indicate new peculiar features of connectomes of higher organisms. We found that the spectral density of adjacency matrices of human connectome has maximal deviation from the one of randomized network, compared to other organisms. Considering the network evolution induced by the preference of 3-cycles formation, we discovered that for macaque and human connectomes the evolution with the conservation of local clusterization is crucial, while for primitive organisms the conservation of averaged clusterization is sufficient. Investigating for the first time the level spacing distribution of the spectrum of human connectome Laplacian matrix, we explicitly demonstrate that the spectral statistics corresponds to the critical regime, which is hybrid of Wigner-Dyson and Poisson distributions. This observation provides strong support for debated statement of the brain criticality.

Finite plateau in spectral gap of polychromatic constrained random networks

We consider critical behavior in the ensemble of polychromatic Erdős-Rényi networks and regular random graphs, where network vertices are painted in different colors. The links can be randomly removed and added to the network subject to the condition of the vertex degree conservation. In these constrained graphs we run the Metropolis procedure, which favors the connected unicolor triads of nodes. Changing the chemical potential, μ, of such triads, for some wide region of μ, we find the formation of a finite plateau in the number of intercolor links, which exactly matches the finite plateau in the network algebraic connectivity (the value of the first nonvanishing eigenvalue of the Laplacian matrix, λ_{2}). We claim that at the plateau the spontaneously broken Z_{2} symmetry is restored by the mechanism of modes collectivization in clusters of different colors. The phenomena of a finite plateau formation holds also for polychromatic networks with M≥2 colors. The behavior of polychromatic networks is analyzed via the spectral properties of their adjacency and Laplacian matrices.