Discovering the network backbone from traffic activity data

Sanjay Chawla; Kiran Garimella; Aristides Gionis; Dominic Tsang

doi:10.1007/978-3-319-31753-3_33

Discovering the network backbone from traffic activity data

Sanjay Chawla, Kiran Garimella^*, Aristides Gionis, Dominic Tsang

^*Corresponding author for this work

Qatar Computing Research Institute

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Advances in Knowledge Discovery and Data Mining - 20th Pacific-Asia Conference, PAKDD 2016, Proceedings
Editors	Ruili Wang, James Bailey, Takashi Washio, Joshua Zhexue Huang, Latifur Khan, Gillian Dobbie
Publisher	Springer Verlag
Pages	409-422
Number of pages	14
ISBN (Print)	9783319317526
DOIs	https://doi.org/10.1007/978-3-319-31753-3_33
Publication status	Published - 2016
Event	20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2016 - Auckland, New Zealand Duration: 19 Apr 2016 → 22 Apr 2016

Publication series

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

Conference

Conference	20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2016
Country/Territory	New Zealand
City	Auckland
Period	19/04/16 → 22/04/16

Access to Document

10.1007/978-3-319-31753-3_33

Cite this

Chawla, S., Garimella, K., Gionis, A., & Tsang, D. (2016). Discovering the network backbone from traffic activity data. In R. Wang, J. Bailey, T. Washio, J. Z. Huang, L. Khan, & G. Dobbie (Eds.), Advances in Knowledge Discovery and Data Mining - 20th Pacific-Asia Conference, PAKDD 2016, Proceedings (pp. 409-422). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9651). Springer Verlag. https://doi.org/10.1007/978-3-319-31753-3_33

Chawla, Sanjay ; Garimella, Kiran ; Gionis, Aristides et al. / Discovering the network backbone from traffic activity data. Advances in Knowledge Discovery and Data Mining - 20th Pacific-Asia Conference, PAKDD 2016, Proceedings. editor / Ruili Wang ; James Bailey ; Takashi Washio ; Joshua Zhexue Huang ; Latifur Khan ; Gillian Dobbie. Springer Verlag, 2016. pp. 409-422 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d3229c0f934544d49f197fbd81480ecf,

title = "Discovering the network backbone from traffic activity data",

abstract = "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.",

author = "Sanjay Chawla and Kiran Garimella and Aristides Gionis and Dominic Tsang",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2016 ; Conference date: 19-04-2016 Through 22-04-2016",

year = "2016",

doi = "10.1007/978-3-319-31753-3_33",

language = "English",

isbn = "9783319317526",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "409--422",

editor = "Ruili Wang and James Bailey and Takashi Washio and Huang, {Joshua Zhexue} and Latifur Khan and Gillian Dobbie",

booktitle = "Advances in Knowledge Discovery and Data Mining - 20th Pacific-Asia Conference, PAKDD 2016, Proceedings",

address = "Germany",

}

Chawla, S, Garimella, K, Gionis, A & Tsang, D 2016, Discovering the network backbone from traffic activity data. in R Wang, J Bailey, T Washio, JZ Huang, L Khan & G Dobbie (eds), Advances in Knowledge Discovery and Data Mining - 20th Pacific-Asia Conference, PAKDD 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9651, Springer Verlag, pp. 409-422, 20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2016, Auckland, New Zealand, 19/04/16. https://doi.org/10.1007/978-3-319-31753-3_33

Discovering the network backbone from traffic activity data. / Chawla, Sanjay; Garimella, Kiran; Gionis, Aristides et al.
Advances in Knowledge Discovery and Data Mining - 20th Pacific-Asia Conference, PAKDD 2016, Proceedings. ed. / Ruili Wang; James Bailey; Takashi Washio; Joshua Zhexue Huang; Latifur Khan; Gillian Dobbie. Springer Verlag, 2016. p. 409-422 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9651).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Discovering the network backbone from traffic activity data

AU - Chawla, Sanjay

AU - Garimella, Kiran

AU - Gionis, Aristides

AU - Tsang, Dominic

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

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

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

UR - http://www.scopus.com/inward/record.url?scp=84964049708&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-31753-3_33

DO - 10.1007/978-3-319-31753-3_33

M3 - Conference contribution

AN - SCOPUS:84964049708

SN - 9783319317526

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 409

EP - 422

BT - Advances in Knowledge Discovery and Data Mining - 20th Pacific-Asia Conference, PAKDD 2016, Proceedings

A2 - Wang, Ruili

A2 - Bailey, James

A2 - Washio, Takashi

A2 - Huang, Joshua Zhexue

A2 - Khan, Latifur

A2 - Dobbie, Gillian

PB - Springer Verlag

T2 - 20th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2016

Y2 - 19 April 2016 through 22 April 2016

ER -

Chawla S, Garimella K, Gionis A, Tsang D. Discovering the network backbone from traffic activity data. In Wang R, Bailey J, Washio T, Huang JZ, Khan L, Dobbie G, editors, Advances in Knowledge Discovery and Data Mining - 20th Pacific-Asia Conference, PAKDD 2016, Proceedings. Springer Verlag. 2016. p. 409-422. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-31753-3_33

Discovering the network backbone from traffic activity data

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this