Discovering the Network Backbone from Traffic Activity Data
| Autor: | Kiran Garimella, Sanjay Chawla, Dominic Tsang, Aristides Gionis |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Social and Information Networks (cs.SI)
FOS: Computer and information sciences Backbone network Computer science Topology (electrical circuits) Network science Computer Science - Social and Information Networks 02 engineering and technology computer.software_genre 020204 information systems 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Data mining Enhanced Data Rates for GSM Evolution Computational problem Greedy algorithm Centrality computer Network analysis |
| Zdroj: | Advances in Knowledge Discovery and Data Mining Lecture Notes in Computer Science Lecture Notes in Computer Science-Advances in Knowledge Discovery and Data Mining Advances in Knowledge Discovery and Data Mining ISBN: 9783319317526 PAKDD (1) |
| ISSN: | 0302-9743 1611-3349 |
| DOI: | 10.48550/arxiv.1402.6138 |
| Popis: | 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 (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. Comment: Submitted for review |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|