On the Smallest Eigenvalue of Grounded Laplacian Matrices

DOI10.1109/TAC.2015.2444191zbMATH Open1359.05077arXiv1406.2271MaRDI QIDQ2980684FDOQ2980684

Authors: Mohammad Pirani, Shreyas Sundaram 

Publication date: 3 May 2017

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: We provide upper and lower bounds on the smallest eigenvalue of grounded Laplacian matrices (which are matrices obtained by removing certain rows and columns of the Laplacian matrix of a given graph). The gap between the upper and lower bounds depends on the ratio of the smallest and largest components of the eigenvector corresponding to the smallest eigenvalue of the grounded Laplacian. We provide a graph-theoretic bound on this ratio, and subsequently obtain a tight characterization of the smallest eigenvalue for certain classes of graphs. Specifically, for Erdos-Renyi random graphs, we show that when a (sufficiently small) set $S$ of rows and columns is removed from the Laplacian, and the probability $p$ of adding an edge is sufficiently large, the smallest eigenvalue of the grounded Laplacian asymptotically almost surely approaches $|S|p$. We also show that for random $d$-regular graphs with a single row and column removed, the smallest eigenvalue is $Theta(fracdn)$. Our bounds have applications to the study of the convergence rate in continuous-time and discrete-time consensus dynamics with stubborn or leader nodes.

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

Recommendations

• Bounds on the Smallest Eigenvalue of a Pinned Laplacian Matrix
• Lower bounds for the eigenvalues of Laplacian matrices
• The smallest eigenvalue of the signless Laplacian
• An upper bound for small eigenvalues of the Laplacian
• On the smallest eigenvalue of \({A_\alpha}(G)\)-matrix
• scientific article; zbMATH DE number 5942888
• Small eigenvalues of Laplacian for $Γ_{0}(N)$
• scientific article; zbMATH DE number 3925012
• The smallest eigenvalue of Hankel matrices
• scientific article; zbMATH DE number 3948505

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial probability (60C05) Stochastic stability in control theory (93E15)

Cited In (14)

• State estimation using a network of distributed observers with unknown inputs
• A first hitting time approach to finding effective spreaders in a network
• Analysis and applications of spectral properties of grounded Laplacian matrices for directed networks
• An upper bound for small eigenvalues of the Laplacian
• An algorithm for accurate distributed time synchronization in mobile wireless sensor networks from noisy difference measurements
• Maximizing the smallest eigenvalue of a symmetric matrix: a submodular optimization approach
• Multi-agent control: a graph-theoretic perspective
• Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition
• Cluster consensus in first and second-order continuous-time networks with input and communication delays
• Title not available (Why is that?)
• Spectral and structural properties of random interdependent networks
• State estimation using a network of distributed observers with switching communication topology
• Graph-theoretic approaches for analyzing the resilience of distributed control systems: a tutorial and survey
• Ranking cliques in higher-order complex networks

This page was built for publication: On the Smallest Eigenvalue of Grounded Laplacian Matrices

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