TY - JOUR

T1 - Concentration of the Kirchhoff index for Erdos-Rényi graphs

AU - Boumal, Nicolas

AU - Cheng, Xiuyuan

N1 - Funding Information:
We thank Amit Singer for suggesting this collaboration, and we thank him as well as Balázs Gerencsér and Romain Hollanders for interesting discussions. We are indebted to and thank the reviewers for identifying shortcomings in the original proofs. This paper presents research results of the Belgian Network DYSCO, funded by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office. NB is an FNRS research fellow.
Publisher Copyright:
© 2014 Elsevier B.V. All rights reserved.

PY - 2014/12

Y1 - 2014/12

N2 - Given an undirected graph, the resistance distance between two nodes is the resistance one would measure between these two nodes in an electrical network if edges were resistors. Summing these distances over all pairs of nodes yields the so-called Kirchhoff index of the graph, which measures its overall connectivity. In this work, we consider Erdos-Rényi random graphs. Since the graphs are random, their Kirchhoff indices are random variables. We give formulas for the expected value of the Kirchhoff index and show it concentrates around its expectation. We achieve this by studying the trace of the pseudoinverse of the Laplacian of Erdos-Rényi graphs. For synchronization (a class of estimation problems on graphs) our results imply that acquiring pairwise measurements uniformly at random is a good strategy, even if only a vanishing proportion of the measurements can be acquired.

AB - Given an undirected graph, the resistance distance between two nodes is the resistance one would measure between these two nodes in an electrical network if edges were resistors. Summing these distances over all pairs of nodes yields the so-called Kirchhoff index of the graph, which measures its overall connectivity. In this work, we consider Erdos-Rényi random graphs. Since the graphs are random, their Kirchhoff indices are random variables. We give formulas for the expected value of the Kirchhoff index and show it concentrates around its expectation. We achieve this by studying the trace of the pseudoinverse of the Laplacian of Erdos-Rényi graphs. For synchronization (a class of estimation problems on graphs) our results imply that acquiring pairwise measurements uniformly at random is a good strategy, even if only a vanishing proportion of the measurements can be acquired.

KW - Cramér-Rao bounds

KW - Erdos-Rényi

KW - Estimation on graphs

KW - Kirchhoff index

KW - Laplacian Random matrices

KW - Pseudoinverse of graph

KW - Resistance distance

KW - Sensor network localization

KW - Synchronization

UR - http://www.scopus.com/inward/record.url?scp=84909951226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84909951226&partnerID=8YFLogxK

U2 - 10.1016/j.sysconle.2014.10.006

DO - 10.1016/j.sysconle.2014.10.006

M3 - Article

AN - SCOPUS:84909951226

VL - 74

SP - 74

EP - 80

JO - Systems and Control Letters

JF - Systems and Control Letters

SN - 0167-6911

ER -