On the distribution of topological and spectral indices on random graphs
C. T. Martínez-Martínez, R. Aguilar-Sánchez, J. A. Méndez-Bermúdez · 2025
Read On the distribution of topological and spectral indices on random graphs by C. T. Martínez-Martínez, R. Aguilar-Sánchez, J. A. Méndez-Bermúdez (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04008.txt.
Introduction
Martinez-Martinez and co-authors study number summaries of random networks in a 2025 paper. Such summaries, called indices, compress a network into one value, based either on how connected each point is or on the network's spectrum. The team asks what shapes these values follow when the network is random.
They test two standard kinds of random networks, from nearly empty to nearly complete. Sums of degree-based terms settle into the classic bell curve. Products of such terms instead follow a skewed curve famous in finance and biology. A newer degree variant behaves the same as the classic one. Spectrum-only indices follow the bell curve, while indices mixing spectrum and direction follow the skewed one. The clean split gives modelers a rule for guessing an index's spread before computing it.
Catalog record
| CREATOR | C. T. Martínez-Martínez, R. Aguilar-Sánchez, J. A. Méndez-Bermúdez |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-04008
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the distribution of topological and spectral indices on random graphs C. T. Martínez-Martínez, R. Aguilar-Sánchez, J. A. Méndez-Bermúdez Abstract We perform a detailed statistical study of the distribution of topological and spectral indices on random graphs G = ( V , E ) G=(V,E) in a wide range of connectivity regimes. First, we consider degree-based topological indices (TIs), and focus on two classes of them: X Σ ( G ) = ∑ u v ∈ E f ( d u , d v ) X_{\Sigma}(G)=\sum_{uv\in E}f(d_{u},d_{v}) and X Π ( G ) = ∏ u v ∈ E g ( d u , d v ) X_{\Pi}(G)=\prod_{uv\in E}g(d_{u},d_{v}) , where u v uv denotes the edge of G G connecting the vertices u u and v v , d u d_{u} is the degree of the vertex u u , and f ( x , y ) f(x,y) and g ( x , y ) g(x,y) are functions of the vertex degrees. Specifically, we apply X Σ ( G ) X_{\Sigma}(G) and X Π ( G ) X_{\Pi}(G) on Erdös-Rényi graphs and random geometric graphs along the full transition from almost isolated vertices to mostly connected graphs. While we verify that P ( X Σ ( G ) ) P(X_{\Sigma}(G)) converges to a standard normal distribution, we show that P ( X Π ( G ) ) P(X_{\Pi}(G)) converges to a log-normal distribution. In addition we also analyze Revan-degree-based indices and spectral indices (those defined from the eigenvalues and eigenvectors of the graph adjacency matrix). Indeed, for Revan-degree indices, we obtain results equivalent to those for standard degree-based TIs. Instead, for spectral indices, we report two distinct patterns: the distribution of indices defined only from eigenvalues approaches a normal distribution, while the distribution of those indices involving both eigenvalues and eigenvectors approaches a log-normal distribution. 1 Introduction In chemical graph theory, graph invariants are widely used to characterize the structural properties of graphs [ 3 , 2 , 1 ] . These invariants can be classified mainly into two types: Topological indices (TIs) and multiplicative topological indices (MTIs). TIs are typically defined as sums over vertex or edge functions, such as \displaystyle X_{\Sigma,F_{V}}(G)=\sum_{u\in V(G)}F_{V}(d_{u}) (1) \displaystyle\mbox{or} \displaystyle X_{\Sigma,F_{E}}(G)=\sum_{uv\in E(G)}F_{E}(d_{u},d_{v}) while MTIs are defined as products over vertex or edge functions, such as \displaystyle X_{\Pi,F_{V}}(G)=\prod_{u\in V(G)}F_{V}(d_{u}) (2) \displaystyle\mbox{or} \displaystyle X_{\Pi,F_{E}}(G)=\prod_{uv\in E(G)}F_{E}(d_{u},d_{v})\,. Here uv denotes the edge of the graph G=(V(G),E(G)) connecting the vertices u and v , d_{u} is the degree of the vertex u , and F_{X}(x) and F_{X}(x,y) are appropriate chosen functions, see e.g. [ 4 ] . While both X_{\Sigma}(G) and X_{\Pi}(G) are referred to as topological indices in the literature, to make a distinction between them, here we name X_{\Sigma}(G) as topological indices (TIs) and X_{\Pi}(G) as multiplicative topological indices (MTIs). Some prominent examples of TIs are the Randić index [ 5 ] , the Zagreb indices [ 6 ] , and the Sombor index [ 7 ] , while among the MTIs we can mention the Narumi-Katayama index [ 8 ] and the multiplicative versions of the Zagreb indices [ 9 ] . All these indices (to be defined later), among others, will be analyzed below. More recently, a new class of TIs based on the Revan vertex degree has been introduced, see e.g. [ 10 , 11 , 12 , 13 , 14 ] . The Revan vertex degree of the vertex u is defined as r_{u}=\Delta+\delta-d_{u}, (3) where \Delta and \delta are the maximum and minimum degrees among the vertices of the graph G , respectively. Revan-degree indices, defined as \displaystyle RX_{\Sigma}(G)=\sum_{uv\in E(G)}F(r_{u},r_{v}) (4) \displaystyle\mbox{or} \displaystyle RX_{\Pi}(G)=\prod_{uv\in E(G)}F(r_{u},r_{v}) are the Revan analogs of standard TIs and MTIs, respectively. That is, RX_{\Sigma}(G) is the Revan version of X_{\Sigma}(G) and RX_{\Pi}(G) is the Revan version of X_{\Pi}(G) . In this work, we also explore the distributions of Revan-degree indices. Additionally, spectral indices, defined in terms of the eigenvalues and eigenvectors of the graph adjacency matrix, have gained attention due to their ability to capture global graph properties avoiding the problem of degeneracy, present in standard TIs; see e.g. [ 15 ] . Specifically, we compute the so-called Rodríguez-Velázquez indices [ 15 , 16 ] as well as the graph energy [ 17 , 18 ] and the subgraph centrality [ 19 ] (to be defined later). The use of topological and spectral indices on random graphs is relatively recent. Moreover, since a given parameter set represents an infinite-size ensemble of random graphs, the computation of a graph invariant on a single graph may be irrelevant. In contrast, the computation of the average value of a graph invariant over a large ensemble of random graphs, all characterized by the same parameter set, may provide useful average information about the full ensemble. This statistical approach, well known in random matrix theory (RMT) studies, has been recently applied to random graphs and networks by means of topological and spectral indices, see e.g. [ 14 , 16 , 20 , 21 , 22 , 24 , 23 ] . In fact, the average value of some topological indices have been shown to be equivalent to standard RMT measures [ 22 , 16 ] . While most studies of topological and spectral indices on random graphs have been focused on the average values of the indices, just a few have considered their probability distribution functions numerically [ 20 , 21 ] and analytically [ 25 , 26 ] . Specifically, on the one hand, in Refs. [ 20 , 21 ] the probability distribution functions of the Randić index, the harmonic index, the sum-connectivity index, the modified Zagreb index, and the inverse degree index on Erdös-Rényi graphs were reported. On the other hand, in Refs. [ 25 , 26 ] the the probability distribution functions of TIs on Erdös-Rényi graphs and of the Randić index on random geometric graphs were studied; see also the related Refs. [ 27 , 28 ] . Therefore, in this work to go a step forward in the direction addressed by Refs. [ 20 , 21 , 25 , 26 ] , we conduct a comprehensive statistical (numeirical) analysis of the probability distribution functions (from now on we will call them just distributions) of TIs, MTIs, Revan-degree indices, and spectral indices on two types of random graphs: Erdös-Rényi graphs (ERGs) and random geometric graphs (RGGs). This paper is organized as follows. In Sec. 2 we introduce the graph models and the parameter settings to be used in the numerical analysis. In Sec. 3 we report the distributions of TIs, MTIs, Revan-degree indices, and spectral indices on ERGs. To avoid text saturation, the results corresponding to RGGs are reported in the Appendix. Finally, our findings are summarized in Sec. 4 . 2 Graph models and parameter settings ERGs [ 29 , 30 , 31 ] , G_{\mbox{\tiny ERG}}(n,p) , are formed by n vertices connected independently with probability p\in[0,1] . While RGGs [ 32 , 33 ] , G_{\mbox{\tiny RGG}}(n,r) , consist of n vertices uniformly and independently distributed on the unit square, where an edge connects two vertices if their