Bounding Robustness via Kirchhoff Index

Bounding robustness in complex networks has gained increasing attention in the literature. Network robustness research has indeed been carried out by scientists with different backgrounds, like mathematics, physics, computer science and biology. As a result, quite a lot of different approaches to capture the robustness properties of a network have been undertaken. Traditionally, the concept of robustness was mainly centered on graph connectivity. Recently, a more contemporary definition has been developed. According to [16], it is defined as the ability of a network to maintain its total throughput under node and link removal. Under this definition, the dynamic processes that run over a network must be taken into consideration. In this framework several robustness metrics based on network topology or spectral graph theory have been developed ( see [4], [8], [9], [13]). In particular, we focus on spectral graph theory where robustness is measured by means of functions of eigenvalues of the Laplacian matrix associated to a graph ([10] and [19]). Indeed, this paper is aimed to the inspection of a graph measure called effective graph resistance, also known as Kirchhoff index (or resistance distance), derived from the field of electric circuit analysis ([14]). The Kirchhoff index has undergone intense scrutiny in recent years and a variety of techniques have been used, including graph theory, algebra (the study of the Laplacian and of the normalized Laplacian), electric networks, probabilistic arguments involving hitting times of random walks ([6] and [7]) and discrete potential theory (equilibrium measures and Wiener capacities), among others. It is defined as the accumulated effective resistance between all pairs of vertices. This index is widely used in Mathematical Chemistry, Computational Biology and, more generally in Network Analysis in order to describe the graph topology. It is worth pointing out that the Kirchhoff index can be highly valuable and informative as a robustness measure of a network, showing the ability of a network to continue performing well when it is subject to failure and/or attack. In fact, the pairwise effective resistance measures the vulnerability of a connection between a pair of vertices that considers both the number of paths between the vertices and their length. A small value of the effective graph resistance therefore indicates a robust network. Several works studied indeed the Kirchhoff index in networks that are topologically changed. For example, Ghosh et al [12] study the minimization of the effective graph resistance by allocating link weights in weighted graphs. Van Mieghem et al in [20] show the relation between the Kirchhoff index and the linear degree correlation coefficient. Abbas et al in [1] reduce the Kirchhoff index of a graph by adding links in a step-wise way. Finally, [17] focuses on Kirchhoff index as an indicator of robustness in complex networks when single links are added or removed. In particular, being the calculation of this index computationally intensive for large networks, they provide upper and lower bounds when an edge is added or removed. Some of them are based on the relation with the algebraic connectivity ([11]), another measure of network robustness. In this paper, we discuss a methodology aimed at obtaining some new and tighter bounds of this graph invariant when edges are added or removed which takes advantage of real analysis techniques, based on majorization theory and optimization of functions which preserve the majorization order, the so-called Schur-convex functions. One major advantage of this approach is to provide a unified framework for recovering many well-known upper and lower bounds obtained with a variety of methods, as well as providing better ones. It is worth pointing out that the localization of topological indices is typically carried out by applying classical inequalities such as the Cauchy-Schwarz inequality or the arithmetic-geometric-harmonic mean inequalities.Within this topological robustness framework, we propose to use our bounds, obtained by these techniques, for robustness assessment of complex networks. Further research regards a generalization to weighted and/or directed networks and the analysis of the correlation between alternative topological metrics.