Scaling properties of multilayer random networks

Non-Hermitian diluted banded random matrices: Scaling of eigenfunction and spectral properties

Here we introduce the non-Hermitian diluted banded random matrix (nHdBRM) ensemble as the set of N×N real nonsymmetric matrices whose entries are independent Gaussian random variables with zero mean and variance one if |i-j| Collapse

Nonuniform random graphs on the plane: A scaling study

We consider random geometric graphs on the plane characterized by a nonuniform density of vertices. In particular, we introduce a graph model where n vertices are independently distributed in the unit disk with positions, in polar coordinates (l,θ), obeying the probability density functions ρ(l) and ρ(θ). Here we choose ρ(l) as a normal distribution with zero mean and variance σ∈(0,∞) and ρ(θ) as a uniform distribution in the interval θ∈[0,2π). Then, two vertices are connected by an edge if their Euclidean distance is less than or equal to the connection radius ℓ. We characterize the topological properties of this random graph model, which depends on the parameter set (n,σ,ℓ), by the use of the average degree 〈k〉 and the number of nonisolated vertices V_{×}, while we approach their spectral properties with two measures on the graph adjacency matrix: the ratio of consecutive eigenvalue spacings r and the Shannon entropy S of eigenvectors. First we propose a heuristic expression for 〈k(n,σ,ℓ)〉. Then, we look for the scaling properties of the normalized average measure 〈X[over ¯]〉 (where X stands for V_{×}, r, and S) over graph ensembles. We demonstrate that the scaling parameter of 〈V_{×}[over ¯]〉=〈V_{×}〉/n is indeed 〈k〉, with 〈V_{×}[over ¯]〉≈1-exp(-〈k〉). Meanwhile, the scaling parameter of both 〈r[over ¯]〉 and 〈S[over ¯]〉 is proportional to n^{-γ}〈k〉 with γ≈0.16.

Structural and spectral properties of generative models for synthetic multilayer air transportation networks

To understand airline transportation networks (ATN) systems we can effectively represent them as multilayer networks, where layers capture different airline companies, the nodes correspond to the airports and the edges to the routes between the airports. We focus our study on the importance of leveraging synthetic generative multilayer models to support the analysis of meaningful patterns in these routes, capturing an ATN’s evolution with an emphasis on measuring its resilience to random or targeted attacks and considering deliberate locations of airports. By resorting to the European ATN and the United States ATN as exemplary references, in this work, we provide a systematic analysis of major existing synthetic generation models for ATNs, specifically ANGEL, STARGEN and BINBALL. Besides a thorough study of the topological aspects of the ATNs created by the three models, our major contribution lays on an unprecedented investigation of their spectral characteristics based on Random Matrix Theory and on their resilience analysis based on both site and bond percolation approaches. Results have shown that ANGEL outperforms STARGEN and BINBALL to better capture the complexity of real-world ATNs by featuring the unique properties of building a multiplex ATN layer by layer and of replicating layers with point-to-point structures alongside hub-spoke formations.

Spacing ratio characterization of the spectra of directed random networks

Previous literature on random matrix and network science has traditionally employed measures derived from nearest-neighbor level spacing distributions to characterize the eigenvalue statistics of random matrices. This approach, however, depends crucially on eigenvalue unfolding procedures, which in many situations represent a major hindrance due to constraints in the calculation, especially in the case of complex spectra. Here we study the spectra of directed networks using the recently introduced ratios between nearest and next-to-nearest eigenvalue spacing, thus circumventing the shortcomings imposed by spectral unfolding. Specifically, we characterize the eigenvalue statistics of directed Erdős-Rényi (ER) random networks by means of two adjacency matrix representations, namely, (1) weighted non-Hermitian random matrices and (2) a transformation on non-Hermitian adjacency matrices which produces weighted Hermitian matrices. For both representations, we find that the distribution of spacing ratios becomes universal for a fixed average degree, in accordance with undirected random networks. Furthermore, by calculating the average spacing ratio as a function of the average degree, we show that the spectral statistics of directed ER random networks undergoes a transition from Poisson to Ginibre statistics for model 1 and from Poisson to Gaussian unitary ensemble statistics for model 2. Eigenvector delocalization effects of directed networks are also discussed.

Topological versus spectral properties of random geometric graphs

In this work we perform a detailed statistical analysis of topological and spectral properties of random geometric graphs (RGGs), a graph model used to study the structure and dynamics of complex systems embedded in a two-dimensional space. RGGs, G(n,ℓ), consist of n vertices uniformly and independently distributed on the unit square, where two vertices are connected by an edge if their Euclidian distance is less than or equal to the connection radius ℓ∈[0,sqrt[2]]. To evaluate the topological properties of RGGs we chose two well-known topological indices, the Randić index R(G) and the harmonic index H(G). We characterize the spectral and eigenvector properties of the corresponding randomly weighted adjacency matrices by the use of random matrix theory measures: the ratio between consecutive eigenvalue spacings, the inverse participation ratios, and the information or Shannon entropies S(G). First, we review the scaling properties of the averaged measures, topological and spectral, on RGGs. Then we show that (i) the averaged-scaled indices, 〈R(G)〉 and 〈H(G)〉, are highly correlated with the average number of nonisolated vertices 〈V_{×}(G)〉; and (ii) surprisingly, the averaged-scaled Shannon entropy 〈S(G)〉 is also highly correlated with 〈V_{×}(G)〉. Therefore, we suggest that very reliable predictions of eigenvector properties of RGGs could be made by computing topological indices.

Geometrical and spectral study of β-skeleton graphs

We perform an extensive numerical analysis of β-skeleton graphs, a particular type of proximity graphs. In a β-skeleton graph (BSG) two vertices are connected if a proximity rule, that depends of the parameter β∈(0,∞), is satisfied. Moreover, for β>1 there exist two different proximity rules, leading to lune-based and circle-based BSGs. First, by computing the average degree of large ensembles of BSGs we detect differences, which increase with the increase of β, between lune-based and circle-based BSGs. Then, within a random matrix theory (RMT) approach, we explore spectral and eigenvector properties of random BSGs by the use of the nearest-neighbor energy-level spacing distribution and the entropic eigenvector localization length, respectively. The RMT analysis allows us to conclude that a localization transition occurs at β=1.

Information Entropy of Tight-Binding Random Networks with Losses and Gain: Scaling and Universality

We study the localization properties of the eigenvectors, characterized by their information entropy, of tight-binding random networks with balanced losses and gain. The random network model, which is based on Erdős–Rényi (ER) graphs, is defined by three parameters: the network size N, the network connectivity α, and the losses-and-gain strength γ. Here, N and α are the standard parameters of ER graphs, while we introduce losses and gain by including complex self-loops on all vertices with the imaginary amplitude iγ with random balanced signs, thus breaking the Hermiticity of the corresponding adjacency matrices and inducing complex spectra. By the use of extensive numerical simulations, we define a scaling parameter ξ≡ξ(N,α,γ) that fixes the localization properties of the eigenvectors of our random network model; such that, when ξ<0.1 (10<ξ), the eigenvectors are localized (extended), while the localization-to-delocalization transition occurs for 0.1<ξ<10. Moreover, to extend the applicability of our findings, we demonstrate that for fixed ξ, the spectral properties (characterized by the position of the eigenvalues on the complex plane) of our network model are also universal; i.e., they do not depend on the specific values of the network parameters.

Crossover in nonstandard random-matrix spectral fluctuations without unfolding

Recently, singular value decomposition (SVD) was applied to standard Gaussian ensembles of random-matrix theory to determine the scale invariance in spectral fluctuations without performing any unfolding procedure. Here, SVD is applied directly to the β-Hermite ensemble and to a sparse matrix ensemble, decomposing the corresponding spectra in trend and fluctuation modes. In correspondence with known results, we obtain that fluctuation modes exhibit a crossover between soft and rigid behavior. In this way, possible artifacts introduced applying unfolding techniques are avoided. By using the trend modes, we perform data-adaptive unfolding, and we calculate traditional spectral fluctuation measures. Additionally, ensemble-averaged and individual-spectrum averaged statistics are calculated consistently within the same basis of normal modes.

Information-Length Scaling in a Generalized One-Dimensional Lloyd's Model

We perform a detailed numerical study of the localization properties of the eigenfunctions of one-dimensional (1D) tight-binding wires with on-site disorder characterized by long-tailed distributions: For large ϵ , P ( ϵ ) ∼ 1 / ϵ 1 + α with α ∈ ( 0 , 2 ] ; where ϵ are the on-site random energies. Our model serves as a generalization of 1D Lloyd's model, which corresponds to α = 1 . In particular, we demonstrate that the information length β of the eigenfunctions follows the scaling law β = γ x / ( 1 + γ x ) , with x = ξ / L and γ ≡ γ ( α ) . Here, ξ is the eigenfunction localization length (that we extract from the scaling of Landauer's conductance) and L is the wire length. We also report that for α = 2 the properties of the 1D Anderson model are effectively reproduced.

Identifying network structure similarity using spectral graph theory

Most real networks are too large or they are not available for real time analysis. Therefore, in practice, decisions are made based on partial information about the ground truth network. It is of great interest to have metrics to determine if an inferred network (the partial information network) is similar to the ground truth. In this paper we develop a test for similarity between the inferred and the true network. Our research utilizes a network visualization tool, which systematically discovers a network, producing a sequence of snapshots of the network. We introduce and test our metric on the consecutive snapshots of a network, and against the ground truth. To test the scalability of our metric we use a random matrix theory approach while discovering Erdös-Rényi graphs. This scaling analysis allows us to make predictions about the performance of the discovery process.

Super-Resolution Community Detection for Layer-Aggregated Multilayer Networks

Applied network science often involves preprocessing network data before applying a network-analysis method, and there is typically a theoretical disconnect between these steps. For example, it is common to aggregate time-varying network data into windows prior to analysis, and the trade-offs of this preprocessing are not well understood. Focusing on the problem of detecting small communities in multilayer networks, we study the effects of layer aggregation by developing random-matrix theory for modularity matrices associated with layer-aggregated networks with N nodes and L layers, which are drawn from an ensemble of Erdős-Rényi networks with communities planted in subsets of layers. We study phase transitions in which eigenvectors localize onto communities (allowing their detection) and which occur for a given community provided its size surpasses a detectability limit K* . When layers are aggregated via a summation, we obtain [Formula: see text], where T is the number of layers across which the community persists. Interestingly, if T is allowed to vary with L, then summation-based layer aggregation enhances small-community detection even if the community persists across a vanishing fraction of layers, provided that T/L decays more slowly than 𝒪(L-1/2). Moreover, we find that thresholding the summation can, in some cases, cause K* to decay exponentially, decreasing by orders of magnitude in a phenomenon we call super-resolution community detection. In other words, layer aggregation with thresholding is a nonlinear data filter enabling detection of communities that are otherwise too small to detect. Importantly, different thresholds generally enhance the detectability of communities having different properties, illustrating that community detection can be obscured if one analyzes network data using a single threshold.