Spanning edge centrality: Large-scale computation and applications

Charalampos Mavroforakis, Richard Garcia-Lebron, Ioannis Koutis, Evimaria Terzi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationWWW 2015 - Proceedings of the 24th International Conference on World Wide Web
PublisherAssociation for Computing Machinery, Inc
Pages732-742
Number of pages11
ISBN (Electronic)9781450334693
DOIs
StatePublished - May 18 2015
Externally publishedYes
Event24th International Conference on World Wide Web, WWW 2015 - Florence, Italy
Duration: May 18 2015May 22 2015

Publication series

NameWWW 2015 - Proceedings of the 24th International Conference on World Wide Web

Other

Other24th International Conference on World Wide Web, WWW 2015
Country/TerritoryItaly
CityFlorence
Period5/18/155/22/15

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Software

Keywords

  • Edge centrality
  • Graph algorithms
  • Social networks
  • Spanning trees

Fingerprint

Dive into the research topics of 'Spanning edge centrality: Large-scale computation and applications'. Together they form a unique fingerprint.

Cite this