Geometry of complex networks and topological centrality

Gyan Ranjan, Zhi-Li Zhang

Research output: Contribution to journalArticle

28 Scopus citations

Abstract

We explore the geometry of complex networks in terms of an n-dimensional Euclidean embedding represented by the Moore-Penrose pseudo-inverse of the graph Laplacian (L+). The squared distance of a node i to the origin in this n-dimensional space (lii+), yields a topological centrality index, defined as C* (i)=1/lii+. In turn, the sum of reciprocals of individual node centralities, Σi1/Câ̂ -(i)= Σilii+, or the trace of L+, yields the well-known Kirchhoff index (K), an overall structural descriptor for the network. To put into context this geometric definition of centrality, we provide alternative interpretations of the proposed indices that connect them to meaningful topological characteristics - first, as forced detour overheads and frequency of recurrences in random walks that has an interesting analogy to voltage distributions in the equivalent electrical network; and then as the average connectedness of i in all the bi-partitions of the graph. These interpretations respectively help establish the topological centrality (C* (i)) of node i as a measure of its overall position as well as its overall connectedness in the network; thus reflecting the robustness of i to random multiple edge failures. Through empirical evaluations using synthetic and real world networks, we demonstrate how the topological centrality is better able to distinguish nodes in terms of their structural roles in the network and, along with Kirchhoff index, is appropriately sensitive to perturbations/re-wirings in the network.

Original languageEnglish (US)
Pages (from-to)3833-3845
Number of pages13
JournalPhysica A: Statistical Mechanics and its Applications
Volume392
Issue number17
DOIs
StatePublished - Sep 1 2013

Keywords

  • Connected bi-partitions of a graph
  • Equivalent electrical network
  • Expected hitting and commute times
  • Kirchhoff index
  • Moore-Penrose pseudo-inverse of the Laplacian
  • Topological centrality

Fingerprint Dive into the research topics of 'Geometry of complex networks and topological centrality'. Together they form a unique fingerprint.

  • Cite this