A continuum of degree-normalized spectral embeddings that includes these commonly used choices as special cases is studied, and a row-wise central limit theorem is established under a random dot product graph model for this family of embeddings.
Abstract
Spectral clustering methods for network data are commonly based on a few matrix representations, such as the adjacency matrix and the symmetric Laplacian. We study a continuum of degree-normalized spectral embeddings that includes these commonly used choices as special cases. Under a random dot product graph model, we establish a row-wise central limit theorem for this family of embeddings. The result provides an explicit description of how degree normalization affects both population geometry and the local uncertainty of embedded nodes. We use the limiting distributions to compare different normalizations in two-community stochastic block models through a projected-Gaussian Bayes-error diagnostic. These comparisons show that no single normalization is uniformly preferred. Instead, the favored normalization depends on network density, community imbalance, and block-probability structure. Typically, stronger normalization is favored in lower-density or more imbalanced settings. These results provide a unified distributional understanding of when and why alternative normalizations may improve spectral clustering.
Networks with nearly identical degree distributions can place their hubs in sharply different neighborhoods. We develop a model diagnostic based on the mean degree of the neighbors of a degree-$k$ vertex. Under rank-one inhomogeneous random graphs, this statistic has degree-invariant centering and $k^{-1/2}$ fluctuations. Under non-rank-one kernels, posterior uncertainty about the root type can instead determine both centering and scale. Under linear preferential attachment, the statistic grows as $(m+\delta)\log k$. We turn these model-specific limits into goodness-of-fit tests for specified sparse-graph nulls and a weighted log-degree slope test for residual hub-neighborhood trends. Simulations evaluate null calibration, degree-distribution misspecification, and power against degree-matched preferential-attachment alternatives. Applications to high-school contact and arXiv coauthorship networks show that the method separates level misspecification from disassortative and positive residual trends. Reddit interaction networks provide a further appendix example.
The results give an empirical separation, on a real hierarchical-classification problem, between two natural latent geometries for a class-structured regularizer.
It is shown that r-uniform Erd\H{o}s-R\'enyi hypergraphs on n vertices exhibit a spectral gap as soon as their expected number of hyperedges satisfies $m \gg n^{r/2}$.
This approach demonstrates that models trained on small-scale random graphs learn to extract universal distance-preserving features, achieving robust generalization to large-scale, real-world networks that match or exceed the fidelity of classical, exact landmark-based embeddings.
My Le, Luana Ruiz, Souvik Dhara· arXiv.org· 0 citations
We study the spectral and eigenvector properties of random mixed graphs, combining undirected and directed interactions, using random matrix theory (RMT). The network is represented by a Hermitian adjacency matrix, with undirected links as real entries and directed links as purely imaginary conjugate pairs, ensuring a real spectrum. Network density is controlled by the connection probability, while directionality sets the fraction of directed edges. We focus on the GOE-to-GUE crossover: at fixed connectivity, increasing directionality breaks time-reversal symmetry and drives spectral statistics from GOE to GUE. We show that this transition requires sufficient connectivity. In sparse networks, weak level repulsion produces Poisson statistics regardless of directionality. At fixed directionality, increasing connectivity drives a Poisson-to-GUE crossover; only above a sparsity threshold does the directionality-induced GOE-to-GUE transition emerge. In the dense regime, where the spectral density follows the Wigner semicircle law, the crossover is characterized using spacing distributions, spacing ratios, and spectral rigidity. In sparse networks, where unfolding is unreliable, spacing-ratio statistics provide an unfolding-free characterization. Eigenvector structure is examined through multifractal dimensions and component distributions, while Kullback--Leibler divergence confirms the robustness of the transitions. Applied to S&P 500 mixed graphs, the framework reveals a GOE-to-GUE crossover across four major market crashes. Denser crisis periods show sharper crossovers than sparser recovery periods. The results provide a unified picture of how connectivity and symmetry breaking govern spectral and eigenvector universality, while providing a transparent probe of changing financial-market organization.
Himanshu Shekhar, Hrishidev Unni, Santosh Kumar et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
