Videos

When Affinity Meets Resistance: On the Topological Centrality of Edges in Complex Networks

Presenter
September 7, 2012
Keywords:
  • Complex networks
MSC:
  • 05C82
Abstract
We explore a geometric and topological approach to understanding the structural significance of edges in a complex network. To do so, we embed the complex network (or the graph $G(V, E)$ representing it) into a Euclidean space determined by the eigen-space of the Moore-Penrose pseudo-inverse of the combinatorial laplacian (denoted by $\bb L^+(G)$). The element $l^+_{ij}$ in $\bb L^+(G)$ ($i^{th} ~row-j^{th} ~column)$ determines the angular distance between the position vectors of nodes $i$ and $j$ in this space and is thus a measure of angular affinity between the end points of an edge $e_{ij}$; whereas the Euclidean distance between nodes $i$ and $j$, called the {\em effective resistance} distance ($\Omega_{ij} = l^+_{ii} + l^+_{jj} - l^+_{ij} - l^+_{ji}$), is a measure of the separation between the end-points of the edge $e_{ij}$. Our emphasis is on the topological characteristics reflected in these quantities ($l^+_{ij}$ and $\Omega_{ij}$) with respect to the set of connected bi-partitions of the network (spanning sub-networks with exactly two components). In particular, $l^+_{ij}$ determines the number of nodes that the node pair $(i, j)$ joined through the edge $e_{ij}$, gets dissociated from when the network breaks into two. Higher the value of $l^+_{ij}$, greater the loss in connectedness of the node pair $(i, j)$ in the bi-partitions, and more peripheral $e_{ij}$ is in the network. Therefore, $l^+_{ij}$ captures the topological centrality of the edge $e_{ij}$. On the other hand, $\Omega_{ij}$ determines the strength of connectivities in the two sub-graphs representing a partition (in terms of the number of spanning trees in each part), when the edge $e_{ij}$ is eliminated. It, in fact, is related to the fraction of spanning trees of the network that $e_{ij}$ is present in. Based on these topological characteristics, we motivate several important applications, such as network core identification, greedy spanning tree extraction etc, that are relevant to complex network analysis. We demonstrate the properties of our metrics with the help of example as well as real world networks from diverse domains.