Topological versus spectral properties of random geometric graphs

Hyperbolic random geometric graphs: Structural and spectral properties

In this paper we perform a thorough numerical study of structural and spectral properties of hyperbolic random geometric graphs (HRGs) G(n,ρ,α,ζ) by means of a random matrix theory (RMT) approach. HRGs are formed by distributing n nodes in a Poincaré disk of fixed radius ρ; the radial node distribution is characterized by the exponent α and ζ controls the curvature of the embedding space. Specifically, we report and analyze average structural properties [by means of the number of nonisolated vertices V_{x}(G), topological indices, and clustering coefficients] and average spectral properties [by means of standard RMT measures: the ratio between consecutive eigenvalue spacings r_{R}(G), the ratio between nearest- and next-to-nearest-neighbor eigenvalue distances r_{C}(G), and the inverse participation ratio and the Shannon entropy S(G) of the eigenvectors]. Even though HRGs are, in general, more elaborated than Euclidean random geometric graphs, we show that both types of random graphs share important average properties, namely: (i) 〈V_{x}(G)〉 is a simple function of the average degree 〈k〉, 〈V_{x}(G)〉≈n[1-exp(-γ〈k〉)], while (ii) properly normalized 〈r_{R}(G)〉, 〈r_{C}(G)〉 and 〈S(G)〉 scale with the parameter ξ∝〈k〉n^{δ}. Here, γ≡γ(α/ζ), δ≡δ(α/ζ), and 〈·〉 is the average over a graph ensemble.

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

Topological and spectral properties of random digraphs

We investigate some topological and spectral properties of Erdős-Rényi (ER) random digraphs of size n and connection probability p, D(n,p). In terms of topological properties, our primary focus lies in analyzing the number of nonisolated vertices V_{x}(D) as well as two vertex-degree-based topological indices: the Randić index R(D) and sum-connectivity index χ(D). First, by performing a scaling analysis, we show that the average degree 〈k〉 serves as a scaling parameter for the average values of V_{x}(D), R(D), and χ(D). Then, we also state expressions relating the number of arcs, largest eigenvalue, and closed walks of length 2 to (n,p), the parameters of ER random digraphs. Concerning spectral properties, we observe that the eigenvalue distribution converges to a circle of radius sqrt[np(1-p)]. Subsequently, we compute six different invariants related to the eigenvalues of D(n,p) and observe that these quantities also scale with sqrt[np(1-p)]. Additionally, we reformulate a set of bounds previously reported in the literature for these invariants as a function (n,p). Finally, we phenomenologically state relations between invariants that allow us to extend previously known bounds.

Revan Sombor indices: Analytical and statistical study

In this paper, we perform analytical and statistical studies of Revan indices on graphs $ G $: $ R(G) = \sum_{uv \in E(G)} F(r_u, r_v) $, where $ uv $ denotes the edge of $ G $ connecting the vertices $ u $ and $ v $, $ r_u $ is the Revan degree of the vertex $ u $, and $ F $ is a function of the Revan vertex degrees. Here, $ r_u = \Delta + \delta - d_u $ with $ \Delta $ and $ \delta $ the maximum and minimum degrees among the vertices of $ G $ and $ d_u $ is the degree of the vertex $ u $. We concentrate on Revan indices of the Sombor family, i.e., the Revan Sombor index and the first and second Revan $ (a, b) $-$ KA $ indices. First, we present new relations to provide bounds on Revan Sombor indices which also relate them with other Revan indices (such as the Revan versions of the first and second Zagreb indices) and with standard degree-based indices (such as the Sombor index, the first and second $ (a, b) $-$ KA $ indices, the first Zagreb index and the Harmonic index). Then, we extend some relations to index average values, so they can be effectively used for the statistical study of ensembles of random graphs.

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.

Normalized Sombor Indices as Complexity Measures of Random Networks

We perform a detailed computational study of the recently introduced Sombor indices on random networks. Specifically, we apply Sombor indices on three models of random networks: Erdös-Rényi networks, random geometric graphs, and bipartite random networks. Within a statistical random matrix theory approach, we show that the average values of Sombor indices, normalized to the order of the network, scale with the average degree. Moreover, we discuss the application of average Sombor indices as complexity measures of random networks and, as a consequence, we show that selected normalized Sombor indices are highly correlated with the Shannon entropy of the eigenvectors of the adjacency matrix.