Spectral density of random graphs: convergence properties and application in model fitting

DOI10.1093/COMNET/CNAB041MaRDI QIDQ5022521zbMATH OpenOpenAlexFDO

Authors Suzana de Siqueira Santos, André Fujita, Catherine Matias

Publication date 19 January 2022

Published in Journal of Complex Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.11224

zbMATH Keywords

model fittingmodel selectionrandom graph modelsreal-world networksspectral density

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: Random graph models are used to describe the complex structure of real-world networks in diverse fields of knowledge. Studying their behavior and fitting properties are still critical challenges, that in general, require model specific techniques. An important line of research is to develop generic methods able to fit and select the best model among a collection. Approaches based on spectral density (i.e., distribution of the graph adjacency matrix eigenvalues) are appealing for that purpose: they apply to different random graph models. Also, they can benefit from the theoretical background of random matrix theory. This work investigates the convergence properties of model fitting procedures based on the graph spectral density and the corresponding cumulative distribution function. We also review results on the convergence of the spectral density for the most widely used random graph models. Moreover, we explore through simulations the limits of these graph spectral density convergence results, particularly in the case of the block model, where only partial results have been established.

Recommendations

• CONCENTRATION OF RANDOM GRAPHS AND APPLICATION TO COMMUNITY DETECTION
• Spectral density of random graphs with topological constraints
• A spectral analysis of the normalized Laplacian matrix in random graphs
• The method of moments and degree distributions for network models
• The graph spectra and spectral moments of random graphs

Cited in

(6)

• A spectral signature of breaking of ensemble equivalence for constrained random graphs
• Almost sure convergence of vertex degree densities in the vertex splitting model
• Approximating sparse graphs: The random overlapping communities model
• On the limiting spectral distributions of stochastic block models
• Complex systems in ecology: a guided tour with large Lotka-Volterra models and random matrices
• Vertex-wise graph's spectral density decomposition and its applications

This page was built for publication: Spectral density of random graphs: convergence properties and application in model fitting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5022521)