Spectral classes of regular, random, and empirical graphs

DOI10.1016/J.LAA.2015.08.038MaRDI QIDQ891525zbMATH OpenOpenAlexWikidataFDO

Authors Jiao Gu, Shiping Liu, Peter F. Stadler, Jürgen Jost

Publication date 17 November 2015

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

graph familiesLaplacian spectrumquasimetricRadon measure

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: We define a (pseudo-)distance between graphs based on the spectrum of the normalized Laplacian, which is easy to compute or to estimate numerically. It can therefore serve as a rough classification of large empirical graphs into families that share the same asymptotic behavior of the spectrum so that the distance of two graphs from the same family is bounded by $mathcalO(1/n)$ in terms of size $n$ of their vertex sets. Numerical experiments demonstrate that the spectral distance provides a practically useful measure of graph dissimilarity.

Recommendations

• Spectral distances on graphs
• Laplacian and normalized Laplacian spectral distances of graphs
• Distance between the normalized Laplacian spectra of two graphs
• Distance between the spectra of graphs with respect to normalized Laplacian spectra
• A study of graph spectra for comparing graphs and trees

Cites work

• A graph distance metric based on the maximal common subgraph
• A study of graph spectra for comparing graphs and trees
• An Interlacing Result on Normalized Laplacians
• Characteristic vectors of bordered matrices with infinite dimensions
• Characteristic vectors of bordered matrices with infinite dimensions. II
• Constructing cospectral graphs
• Emergence of Scaling in Random Networks
• Graph kernels
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3173143 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Interlacing eigenvalues and graphs
• Interlacing inequalities for eigenvalues of discrete Laplace operators
• Large networks and graph limits
• Limits of dense graph sequences
• Minimum vertex covers and the spectrum of the normalized Laplacian on trees
• More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures
• Nullity of graphs: an updated survey
• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• On Estimation of a Probability Density Function and Mode
• On the asymptotic behavior of graphs determined by their generalized spectra
• On the distribution of the roots of certain symmetric matrices
• On the spectrum of the normalized graph Laplacian
• Processes on unimodular random networks
• Recurrence of distributional limits of finite planar graphs
• Remarks on Some Nonparametric Estimates of a Density Function
• Research problems from the Aveiro workshop on graph spectra
• Spectra of random graphs with given expected degrees
• Spectral distances of graphs
• Spectral plot properties: towards a qualitative classification of networks
• The complexity of theorem-proving procedures
• The graph isomorphism disease
• The maximum common edge subgraph problem: A polyhedral investigation
• The spectrum of the graph Laplacian as a tool for analyzing structure and evolution of networks

Cited in

(12)

• Tracking network dynamics: a survey using graph distances
• Spectral analysis of transient amplifiers for death-birth updating constructed from regular graphs
• Random geometric complexes and graphs on Riemannian manifolds in the thermodynamic limit
• Spectral graph features for the classification of graphs and graph sequences
• Comparing large-scale graphs based on quantum probability theory
• Spectral distances on graphs
• Spectral classes of strongly-regular and distance-regular graphs
• The spectrum of the graph Laplacian as a tool for analyzing structure and evolution of networks
• scientific article; zbMATH DE number 7352045 (Why is no real title available?)
• Spectral dynamics of guided edge removals and identifying transient amplifiers for death-birth updating
• Spectral convergence of random regular graphs: Chebyshev polynomials, non-backtracking walks, and unitary-color extensions
• A study of graph spectra for comparing graphs and trees

This page was built for publication: Spectral classes of regular, random, and empirical graphs

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