Pseudoinverse of the Laplacian and best spreader node in a network

P. Van Mieghem, K. Devriendt, H. Cetinay

Research output: Contribution to journalArticleScientificpeer-review

49 Citations (Scopus)
258 Downloads (Pure)

Abstract

Determining a set of "important" nodes in a network constitutes a basic endeavor in network science. Inspired by electrical flows in a resistor network, we propose the best conducting node j in a graph G as the minimizer of the diagonal element Qjj† of the pseudoinverse matrix Q† of the weighted Laplacian matrix of the graph G. We propose a new graph metric that complements the effective graph resistance RG and that specifies the heterogeneity of the nodal spreading capacity in a graph. Various formulas and bounds for the diagonal element Qjj† are presented. Finally, we compute the pseudoinverse matrix of the Laplacian of star, path, and cycle graphs and derive an expansion and lower bound of the effective graph resistance RG based on the complement of the graph G.

Original languageEnglish
Article number032311
Pages (from-to)1-22
JournalPhysical Review E
Volume96
Issue number3
DOIs
Publication statusPublished - 2017

Fingerprint

Dive into the research topics of 'Pseudoinverse of the Laplacian and best spreader node in a network'. Together they form a unique fingerprint.

Cite this