Pseudoinverse of the Laplacian and best spreader node in a network

P. Van Mieghem, K. Devriendt, and H. Cetinay
Phys. Rev. E 96, 032311 – Published 15 September 2017

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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Received 9 March 2017

DOI:https://doi.org/10.1103/PhysRevE.96.032311

©2017 American Physical Society

Physics Subject Headings (PhySH)

NetworksInterdisciplinary Physics

Authors & Affiliations

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

  • Faculty of EECS, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands

  • *P.F.A.VanMieghem@tudelft.nl
  • K.L.T.Devriendt@student.tudelft.nl
  • H.Cetinay-Iyicil@tudelft.nl

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 96, Iss. 3 — September 2017

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×