On the Distribution of Topological and Spectral Indices on Random Graphs

We perform a detailed statistical study of the distribution of topological and spectral indices on random graphs $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) = ∑uv ∈ E f(dᵤ,dᵥ) and X_Π(G) = ∏uv ∈ E g(dᵤ,dᵥ), where $uv$ denotes the edge of G connecting the vertices u and v, dᵤ is the degree of the vertex u, and $f(x,y)$ and $g(x,y)$ are functions of the vertex degrees. Specifically, we apply X_Σ(G) and X_Π(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)) converges to a standard normal distribution, we show that P( X_Π(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.