Robustness of skeletons and salient features in networks
arXiv:1309.3797 · doi:10.1093/comnet/cnt019
Abstract
Real world network datasets often contain a wealth of complex topological information. In the face of these data, researchers often employ methods to extract reduced networks containing the most important structures or pathways, sometimes known as `skeletons' or `backbones'. Numerous such methods have been developed. Yet data are often noisy or incomplete, with unknown numbers of missing or spurious links. Relatively little effort has gone into understanding how salient network extraction methods perform in the face of noisy or incomplete networks. We study this problem by comparing how the salient features extracted by two popular methods change when networks are perturbed, either by deleting nodes or links, or by randomly rewiring links. Our results indicate that simple, global statistics for skeletons can be accurately inferred even for noisy and incomplete network data, but it is crucial to have complete, reliable data to use the exact topologies of skeletons or backbones. These results also help us understand how skeletons respond to damage to the network itself, as in an attack scenario.
References in corpus (20)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Error and attack tolerance of complex networks
- The architecture of complex weighted networks
- Temporal Networks
- Network robustness and fragility: Percolation on random graphs
- Resilience of the Internet to random breakdowns
- Link communities reveal multiscale complexity in networks
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Scaling and percolation in the small-world network model
- Prediction and predictability of global epidemics: the role of the airline transportation network
- The complex network of global cargo ship movements
- Extracting the multiscale backbone of complex weighted networks
- Global organization of metabolic fluxes in the bacterium, Escherichia coli
- Co-evolution of strategy and structure in complex networks with dynamical linking
- Robustness of community structure in networks
- Robust classification of salient links in complex networks
- Transport in weighted networks: Partition into superhighways and roads
- Spectral coarse-graining of complex networks
- Information filtering in complex weighted networks