Pseudoinverse of the Laplacian and best spreader node in a network

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 Q_{jj}^{†} of the pseudoinverse matrix Q^{†}...

Full description

Saved in:
Bibliographic Details
Published in:Physical review. E 2017-09, Vol.96 (3-1), p.032311-032311, Article 032311
Main Authors: Van Mieghem, P, Devriendt, K, Cetinay, H
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Q_{jj}^{†} 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 R_{G} and that specifies the heterogeneity of the nodal spreading capacity in a graph. Various formulas and bounds for the diagonal element Q_{jj}^{†} 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 R_{G} based on the complement of the graph G.
ISSN:2470-0045
2470-0053
DOI:10.1103/PhysRevE.96.032311