Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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)

Abstract

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.

Item type: Article
ID code: 40673
Keywords: distance distributions, distance-sum, complex networks, Balaban index, graph distances, Mathematics, Computational Mathematics, Applied Mathematics
Subjects: Science > Mathematics
Department: Faculty of Science > Mathematics and Statistics
Related URLs:
Depositing user: Pure Administrator
Date Deposited: 02 Aug 2012 13:52
Last modified: 27 Mar 2014 10:23
URI: http://strathprints.strath.ac.uk/id/eprint/40673

Actions (login required)

View Item