2011/07/05 by Gyan Ranjan, Zhi-Li Zhang, Ranjan, Gyan +1 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Physical sciences #Graph theory and applications #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #Topological and Geometric Data Analysis #cs.DM #cs.SI #physics.soc-ph
paper · pdf · doi:10.48550/arxiv.1107.0989
17 pages, 6 figures, 2 tables
openalex publication_date 2011/07/05 · arxiv created 2012/11/25 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (\bb L+). The squared distance of a node i to the origin in this n-dimensional space (l+ii), yields a topological centrality index (C*(i) = 1/l+ii) for node i. In turn, the sum of reciprocals of individual node structural centralities, ∑i1/C^*(i) = ∑i l+ii, i.e. the trace of \bb L+, yields the well-known Kirchhoff index (K), an overall structural descriptor for the network. In addition to this geometric interpretation, we provide alternative interpretations of the proposed indices to reveal their true topological characteristics: first, in terms of 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 node 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/rewirings in the network.