# 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

## 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 |

Depositing user: | Pure Administrator |

Date Deposited: | 02 Aug 2012 12:52 |

Last modified: | 22 Mar 2017 12:15 |

Related URLs: | |

URI: | http://strathprints.strath.ac.uk/id/eprint/40673 |

Export data: |