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

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:

05C82

Keywords: