Pseudoinverse of the Laplacian and best spreader node in a network

More Info
expand_more

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.

Files