On the distribution of topological and spectral indices on random graphs

Abstract

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_{\Sigma }(G)={\sum }_{uv\in E}f(d_u,d_v)$ and $X_{\Pi }(G)={\prod }_{uv\in E}g(d_u,d_v)$, where $uv$ denotes the edge of $G$ connecting the vertices $u$ and $v$, $d_u$ 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_{\Sigma }(G)$ and $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_{\Sigma }(G))$ converges to a standard normal distribution, we show that $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.

References in corpus (1)

• Random Rectangular Graphs