Backbone discovery in traffic networks

Sanjay Chawla, Kiran Garimella, Aristides Gionis, Dominic Tsang

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We introduce a new computational problem, the BackboneDiscovery problem, which encapsulates both functional and structural aspects of network analysis. While the topology of a typical road network has been available for a long time (e.g., through maps), it is only recently that fine–granularity functional (activity and usage) information about the network (such as source–destination traffic information) is being collected and is readily available. The combination of functional and structural information provides an efficient way to explore and understand usage patterns of networks and aid in design and decision making. We propose efficient algorithms for the BackboneDiscovery problem including a novel use of edge centrality. We observe that for many real-world networks, our algorithm produces a backbone with a small subset of the edges that support a large percentage of the network activity.

Original languageEnglish
Pages (from-to)215-227
Number of pages13
JournalInternational Journal of Data Science and Analytics
Volume1
Issue number3-4
DOIs
StatePublished - Nov 1 2016
Externally publishedYes

Keywords

  • Backbone
  • Network simplification
  • Network sparsification
  • Shortest path

Fingerprint

Dive into the research topics of 'Backbone discovery in traffic networks'. Together they form a unique fingerprint.

Cite this