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
SN - 0167-6911
VL - 74
SP - 74
EP - 80
JO - Systems and Control Letters
JF - Systems and Control Letters
ER -