Backbone discovery in traffic networks

We introduce a new computational problem, theBackbone-Discovery problem, which encapsulates both functional and structural aspects of network analysis. For example, while the topology of a typical road network has been available for a long time (e.g., through paper maps), it is only recently that fine-granularity usage information about the network (like gps traces), is being collected and is readily accessible. By combining functional and structural information, the so-lution of BackboneDiscovery provides an efficient way to explore and understand usage patterns of networks and aid in design and decision making. To address the Backbone-Discovery problem, we propose two algorithms that make use of the concepts of edge centrality. Our results indi-cate that it is possible to construct very sparse backbones that summarize the network activity very accurately. We also demonstrate that the usage of edge-centrality measures helps produce backbones of higher quality. 1