TY - GEN
T1 - Spanning edge centrality
T2 - 24th International Conference on World Wide Web, WWW 2015
AU - Mavroforakis, Charalampos
AU - Garcia-Lebron, Richard
AU - Koutis, Ioannis
AU - Terzi, Evimaria
PY - 2015/5/18
Y1 - 2015/5/18
N2 - The spanning centrality of an edge e in an undirected graph G is the fraction of the spanning trees of G that contain e. Despite its appealing definition and apparent value in certain applications in computational biology, spanning centrality hasn't so far received a wider attention as a measure of edge centrality. We may partially attribute this to the perceived complexity of computing it, which appears to be prohibitive for very large networks. Contrary to this intuition, spanning centrality can in fact be approximated arbitrary well by very efficient near-linear time algorithms due to Spielman and Srivastava, combined with progress in linear system solvers. In this article we bring theory into practice, with careful and optimized implementations that allow the fast computation of spanning centrality in very large graphs with millions of nodes. With this computational tool in our disposition, we demonstrate experimentally that spanning centrality is in fact a useful tool for the analysis of large networks. Specifically, we show that, relative to common centrality measures, spanning centrality is more effective in identifying edges whose removal causes a higher disruption in an information propagation procedure, while being very resilient to noise, in terms of both the edges scores and the resulting edge ranking.
AB - The spanning centrality of an edge e in an undirected graph G is the fraction of the spanning trees of G that contain e. Despite its appealing definition and apparent value in certain applications in computational biology, spanning centrality hasn't so far received a wider attention as a measure of edge centrality. We may partially attribute this to the perceived complexity of computing it, which appears to be prohibitive for very large networks. Contrary to this intuition, spanning centrality can in fact be approximated arbitrary well by very efficient near-linear time algorithms due to Spielman and Srivastava, combined with progress in linear system solvers. In this article we bring theory into practice, with careful and optimized implementations that allow the fast computation of spanning centrality in very large graphs with millions of nodes. With this computational tool in our disposition, we demonstrate experimentally that spanning centrality is in fact a useful tool for the analysis of large networks. Specifically, we show that, relative to common centrality measures, spanning centrality is more effective in identifying edges whose removal causes a higher disruption in an information propagation procedure, while being very resilient to noise, in terms of both the edges scores and the resulting edge ranking.
KW - Edge centrality
KW - Graph algorithms
KW - Social networks
KW - Spanning trees
UR - http://www.scopus.com/inward/record.url?scp=84961160860&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84961160860&partnerID=8YFLogxK
U2 - 10.1145/2736277.2741125
DO - 10.1145/2736277.2741125
M3 - Conference contribution
AN - SCOPUS:84961160860
T3 - WWW 2015 - Proceedings of the 24th International Conference on World Wide Web
SP - 732
EP - 742
BT - WWW 2015 - Proceedings of the 24th International Conference on World Wide Web
PB - Association for Computing Machinery, Inc
Y2 - 18 May 2015 through 22 May 2015
ER -