TY - GEN

T1 - A geometric approach to robustness in complex networks

AU - Ranjan, Gyan

AU - Zhang, Zhi-Li

PY - 2011/9/9

Y1 - 2011/9/9

N2 - We explore the geometry of networks in terms of an n-dimensional Euclidean embedding represented by the Moore-Penrose pseudo-inverse of the graph Laplacian (L+). The reciprocal of squared distance from each node i to the origin in this n-dimensional space yields a structural centrality index (C*(i)) for the node, while the harmonic sum of individual node structural centrality indices, Σi 1/C* (i), i.e. the trace of L+, yields the well-known Kirchoff index (K), an overall structural descriptor for the network. In addition to its geometric interpretation, we provide alternative interpretation of the proposed structural centrality index (C*(i)) of each node in terms of forced detour costs and recurrences in random walks and electrical networks. Through empirical evaluation over example and real world networks, we demonstrate how structural centrality is better able to distinguish nodes in terms of their structural roles in the network and, along with Kirchoff index, is appropriately sensitive to perturbations/rewirings in the network.

AB - We explore the geometry of networks in terms of an n-dimensional Euclidean embedding represented by the Moore-Penrose pseudo-inverse of the graph Laplacian (L+). The reciprocal of squared distance from each node i to the origin in this n-dimensional space yields a structural centrality index (C*(i)) for the node, while the harmonic sum of individual node structural centrality indices, Σi 1/C* (i), i.e. the trace of L+, yields the well-known Kirchoff index (K), an overall structural descriptor for the network. In addition to its geometric interpretation, we provide alternative interpretation of the proposed structural centrality index (C*(i)) of each node in terms of forced detour costs and recurrences in random walks and electrical networks. Through empirical evaluation over example and real world networks, we demonstrate how structural centrality is better able to distinguish nodes in terms of their structural roles in the network and, along with Kirchoff index, is appropriately sensitive to perturbations/rewirings in the network.

KW - Complex networks

KW - random walks

KW - robustness

KW - scale free networks

UR - http://www.scopus.com/inward/record.url?scp=80052402571&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052402571&partnerID=8YFLogxK

U2 - 10.1109/ICDCSW.2011.18

DO - 10.1109/ICDCSW.2011.18

M3 - Conference contribution

AN - SCOPUS:80052402571

SN - 9780769543864

T3 - Proceedings - International Conference on Distributed Computing Systems

SP - 146

EP - 153

BT - Proceedings - 31st International Conference on Distributed Computing Systems Workshops, ICDCSW 2011

T2 - 31st International Conference on Distributed Computing Systems Workshops, ICDCSW 2011

Y2 - 20 June 2011 through 24 June 2011

ER -