Picture of Open Access badges

Discover Open Access research at Strathprints

It's International Open Access Week, 24-30 October 2016. This year's theme is "Open in Action" and is all about taking meaningful steps towards opening up research and scholarship. The Strathprints institutional repository is a digital archive of University of Strathclyde research outputs. Explore recent world leading Open Access research content by University of Strathclyde researchers and see how Strathclyde researchers are committing to putting "Open in Action".


Image: h_pampel, CC-BY

Distance-sum heterogeneity in graphs and complex networks

Estrada, Ernesto and Vargas Estrada, Eusebio (2012) Distance-sum heterogeneity in graphs and complex networks. Applied Mathematics and Computation, 218 (21). pp. 10393-10405. ISSN 0096-3003

Full text not available in this repository. (Request a copy from the Strathclyde author)


The heterogeneity of the sum of all distances from one node to the rest of nodes in a graph (distance-sum or status of the node) is analyzed. We start here by analyzing the cumulative statistical distributions of the distance-sum of nodes in random and real-world networks. From this analysis we conclude that statistical distributions do not reveal the distance-sumheterogeneity in networks. Thus, we motivate an index of distance-sumheterogeneity based on a hypothetical consensus model in which the nodes of the network try to reach an agreement on their distance-sum values. This index is expressed as a quadratic form of the combinatorial Laplacian matrix of the network. The distance-sumheterogeneity index φ(G) gives a natural interpretation of the Balaban index for any kind of graph/network. We conjecture here that among graphs with a given number of nodes φ(G) is maximized for a graph with a structure resembling the agave plant. We also found the graphs that maximize φ(G) for a given number of nodes and links. Using this index and a normalized version of it we studied random graphs as well as 57 real-world networks. Our findings indicate that the distance-sumheterogeneity index reveals important structural characteristics of networks which can be important for understanding the functional and dynamical processes in complex systems.