Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator

DOI10.4310/CAG.2013.V21.N4.A2zbMATH Open1290.05100arXiv0910.3118WikidataQ125022610 ScholiaQ125022610MaRDI QIDQ2450139FDOQ2450139

Authors: Frank Bauer, Jürgen Jost 

Publication date: 16 May 2014

Published in: Communications in Analysis and Geometry (Search for Journal in Brave)

Abstract: We study the spectrum of the normalized Laplace operator of a connected graph $Gamma$. As is well known, the smallest nontrivial eigenvalue measures how difficult it is to decompose $Gamma$ into two large pieces, whereas the largest eigenvalue controls how close $Gamma$ is to being bipartite. The smallest eigenvalue can be controlled by the Cheeger constant, and we establish a dual construction that controls the largest eigenvalue. Moreover, we find that the neighborhood graphs $Gamma[l]$ of order $lgeq2$ encode important spectral information about $Gamma$ itself which we systematically explore. In particular, the neighborhood graph method leads to new estimates for the smallest nontrivial eigenvalue that can improve the Cheeger inequality, as well as an explicit estimate for the largest eigenvalue from above and below. As applications of such spectral estimates, we provide a criterion for the synchronizability of coupled map lattices, and an estimate for the convergence rate of random walks on graphs.

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

Recommendations

• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• Spectral gap of the largest eigenvalue of the normalized graph Laplacian
• On the spectrum of the normalized graph Laplacian
• Effects on the normalized Laplacian spectral radius of non-bipartite graphs under perturbation and their applications
• On the second largest normalized Laplacian eigenvalue of graphs

zbMATH Keywords

Cheeger constantlargest eigenvalueCheeger inequality

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random walks on graphs (05C81)

Cited In (31)

• Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs
• Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator
• The heat flow on metric random walk spaces
• Normalized graph Laplacians for directed graphs
• Cahn–Hilliard equations on random walk spaces
• Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• Spectra of graphs and fractal dimensions. I
• Two models for sandpile growth in weighted graphs
• Curvature and higher order Buser inequalities for the graph connection Laplacian
• On the spectrum of the normalized graph Laplacian
• On the bipartiteness constant and expansion of Cayley graphs
• Generalized Ricci curvature and the geometry of graphs
• Pseudoinverse graph convolutional networks. Fast filters tailored for large eigengaps of dense graphs and hypergraphs
• Bipartite communities via spectral partitioning
• Multi-way dual Cheeger constants and spectral bounds of graphs
• Torsional Rigidity in Random Walk Spaces
• On a Cheeger type inequality in Cayley graphs of finite groups
• Diffusion determines the recurrent graph
• Spectral distances on graphs
• Normalized Laplacian spectrum of complete multipartite graphs
• \(p\)-Laplace operators for oriented hypergraphs
• The dual Cheeger constant and spectra of infinite graphs
• Laplacian energies of vertices
• Petals and books: The largest Laplacian spectral gap from 1
• Cheeger inequalities for the discrete magnetic Laplacian
• Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
• Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians
• The geometric meaning of curvature: local and nonlocal aspects of Ricci curvature
• Sharp bounds for the largest eigenvalue
• Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology

This page was built for publication: Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator

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