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 constantCheeger inequalitylargest eigenvalue

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

(40)

• Spectra of graphs and fractal dimensions. I
• Pseudoinverse graph convolutional networks. Fast filters tailored for large eigengaps of dense graphs and hypergraphs
• Sharp bounds for the largest eigenvalue
• Cheeger inequalities for the discrete magnetic Laplacian
• On the bipartiteness constant and expansion of Cayley graphs
• \(p\)-Laplace operators for oriented hypergraphs
• Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs
• Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
• The heat flow on metric random walk spaces
• On a Cheeger type inequality in Cayley graphs of finite groups
• Spectral distances on graphs
• The dual Cheeger constant and spectra of infinite graphs
• Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
• Normalized graph Laplacians for directed graphs
• The geometric meaning of curvature: local and nonlocal aspects of Ricci curvature
• Curvature and higher order Buser inequalities for the graph connection Laplacian
• Generalized Ricci curvature and the geometry of graphs
• Multi-way dual Cheeger constants and spectral bounds of graphs
• Diffusion determines the recurrent graph
• Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology
• Bipartite communities via spectral partitioning
• Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians
• Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator
• Petals and books: The largest Laplacian spectral gap from 1
• Cahn–Hilliard equations on random walk spaces
• Torsional Rigidity in Random Walk Spaces
• Two models for sandpile growth in weighted graphs
• Laplacian energies of vertices
• Ricci curvature, diameter and eigenvalues of amply regular graphs
• A unified analysis of likelihood-based estimators in the Plackett-Luce model
• Dual Cheeger constants, signless 1-Laplacians and maxcut
• Vertex isoperimetry on signed graphs and spectra of non-bipartite Cayley and Cayley sum graphs
• Gelfand-type problems in random walk spaces
• On the nontrivial extremal eigenvalues of graphs
• Remarks on Lagrange multiplier approach to Kazdan-Warner equations on a finite graph
• Cheeger's cut, maxcut and the spectral theory of 1-Laplacian on graphs
• Discrete Bakry-Émery curvature tensors and matrices of connection graphs
• O( n)-approximation algorithms for bipartiteness ratio
• Normalized Laplacian spectrum of complete multipartite graphs
• On the spectrum of the normalized graph Laplacian

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)