Discovering the network backbone from traffic activity data

Sanjay Chawla, Kiran Garimella, Aristides Gionis, Dominic Tsang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


We introduce a new computational problem, the BACKBONE-DISCOVERY 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 (like 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
Title of host publicationAdvances in Knowledge Discovery and Data Mining - 20th Pacific-Asia Conference, PAKDD 2016, Proceedings
EditorsRuili Wang, James Bailey, Takashi Washio, Joshua Zhexue Huang, Latifur Khan, Gillian Dobbie
PublisherSpringer Verlag
Number of pages14
ISBN (Print)9783319317526
StatePublished - 2016
Externally publishedYes
Event20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2016 - Auckland, New Zealand
Duration: Apr 19 2016Apr 22 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2016
Country/TerritoryNew Zealand


Dive into the research topics of 'Discovering the network backbone from traffic activity data'. Together they form a unique fingerprint.

Cite this