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

Friday, September 7, 2012 - 9:00am - 10:00am
Lind 305
Gyan Ranjan (University of Minnesota, Twin Cities)
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.
MSC Code: