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

DOI10.4310/CAG.2013.V21.N4.A2MaRDI QIDQ2450139zbMATH OpenWikidataFDO

Authors Frank Bauer, Jürgen Jost

Publication date 16 May 2014

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

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

zbMATH Keywords

Cheeger constantlargest eigenvalueCheeger inequality

Mathematics Subject Classification ID

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

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.

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

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
• Normalized graph Laplacians for directed graphs
• The heat flow on metric 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
• Cahn–Hilliard equations on random walk spaces
• 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
• Pseudoinverse graph convolutional networks. Fast filters tailored for large eigengaps of dense graphs and hypergraphs
• Generalized Ricci curvature and the geometry of graphs
• Bipartite communities via spectral partitioning
• Multi-way dual Cheeger constants and spectral bounds of graphs
• Torsional Rigidity in Random Walk Spaces
• Diffusion determines the recurrent graph
• On a Cheeger type inequality in Cayley graphs of finite groups
• 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
• Cheeger inequalities for the discrete magnetic Laplacian
• Petals and books: The largest Laplacian spectral gap from 1
• Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
• Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians
• Sharp bounds for the largest eigenvalue
• The geometric meaning of curvature: local and nonlocal aspects of Ricci curvature
• 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)