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

Nicolas Boumal, Xiuyuan Cheng

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)74-80
Number of pages7
JournalSystems and Control Letters
Volume74
DOIs
StatePublished - Dec 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science(all)
  • Mechanical Engineering
  • Electrical and Electronic Engineering

Keywords

  • Cramér-Rao bounds
  • Erdos-Rényi
  • Estimation on graphs
  • Kirchhoff index
  • Laplacian Random matrices
  • Pseudoinverse of graph
  • Resistance distance
  • Sensor network localization
  • Synchronization

Fingerprint Dive into the research topics of 'Concentration of the Kirchhoff index for Erdos-Rényi graphs'. Together they form a unique fingerprint.

Cite this