Understanding edge-connectivity in the Internet through core-decomposition
arXiv:0912.1424 · doi:10.1080/15427951.2011.560786
Abstract
Internet is a complex network composed by several networks: the Autonomous Systems, each one designed to transport information efficiently. Routing protocols aim to find paths between nodes whenever it is possible (i.e., the network is not partitioned), or to find paths verifying specific constraints (e.g., a certain QoS is required). As connectivity is a measure related to both of them (partitions and selected paths) this work provides a formal lower bound to it based on core-decomposition, under certain conditions, and low complexity algorithms to find it. We apply them to analyze maps obtained from the prominent Internet mapping projects, using the LaNet-vi open-source software for its visualization.
References in corpus (7)
- New Model of Internet Topology Using k-shell Decomposition
- MEDUSA - New Model of Internet Topology Using k-shell Decomposition
- The phase transition in inhomogeneous random graphs
- k-core decomposition: a tool for the visualization of large scale networks
- Exploring networks with traceroute-like probes: theory and simulations
- The k-core and branching processes
- Modeling the Internet