ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Graph Theory and Linear Algebra

Thu 11:00–11:30, Auditorium Max Weber
Resistive distances on networks
Ángeles Carmona (Universitat Politècnica de Catalunya)
Joint work with Andrés M. Encinas (Universitat Politècnica de Catalunya); Margarida Mitjana (Universitat Politècnica de Catalunya)

Because its structural meaning, resistive distance has become an useful tool to analyze structural properties of graphs, or more generally of networks such as robustness, see for instance [2]. In contrast to the standard geodesic distance, the resistive distance takes into account all paths between vertices. The high sensibility of this metric with respect to small perturbations, makes it suitable to compare different network structures. This is one of the main reason for which effective resistances and the corresponding Kirchhoff Index, the sum of all of them, have emerged as a structure-descriptor in the framework of Organic Chemistry, where the topology of chemical compounds is conventionally represented by a molecular network where edge weights correspond to bond properties, see for instance [3] and references therein. Effective resistances can be expressed in terms of the group inverse of the Laplacian matrix and the corresponding Kirchhoff index is nothing else but its trace.

Many other structural parameters and distances on networks have been studied with similar purposes. In this work we pay attention on the so–called forest metric introduced by P. Chebotarev and E. Shamis at the late 90's, or more specifically on its reformulation as adjusted forest metric, see [1]. They interpret this metric as a measure of the accessibility and then in terms of choosing an unsuccessful connection between vertices. The adjusted forests metrics form a one–parametric family, where the parameter determines the proportion of taking into account long and short routes between vertices. Moreover, the usual resistive distance is the asymptotic value of the metric when the parameter goes to infinite. The objetive of this communication is twofold. Firstly we show that each distance of the one–parametric family correspond in fact to that associated to an effective resistance corresponding to suitable Schrödinger operators on the network, instead to Laplacian one, and then its main properties can by analyzed within the framework of potential theory. On the other hand, the relation between irreducible $M$–matrices and Schrödinger operators on networks, leads to consider effective resistances associated with this class of matrices. We also study the effect of some perturbation on the given $M$–matrix on its resistive distance.

This research was supported by the Spanish Research Council under project MTM2014-60450-R.

  1. P. Chebotarev and E. Shamis, The Forest Metrics for Graph Vertices, Electron. Notes Discrete Math. 11 (2002) 98-107.
  2. W. Ellens, F.M. Spieksma, P. Van Mieghem, A. Jamakovic, R.E. Kooij, Effective graph resistance, Linear Algebra Appl. 435 (2011) 2491–2506
  3. Y. Yang and D.J. Klein, A recursion formula for resistance distances and its applications, Discrete Appl. Math. 161 (2013) 2702–2715.