Sizing the length of complex networks
arXiv:1810.12825 · doi:10.1038/s42005-019-0239-0
Abstract
Among all characteristics exhibited by natural and man-made networks the small-world phenomenon is surely the most relevant and popular. But despite its significance, a reliable and comparable quantification of the question `how small is a small-world network and how does it compare to others' has remained a difficult challenge to answer. Here we establish a new synoptic representation that allows for a complete and accurate interpretation of the pathlength (and efficiency) of complex networks. We frame every network individually, based on how its length deviates from the shortest and the longest values it could possibly take. For that, we first had to uncover the upper and the lower limits for the pathlength and efficiency, which indeed depend on the specific number of nodes and links. These limits are given by families of singular configurations that we name as ultra-short and ultra-long networks. The representation here introduced frees network comparison from the need to rely on the choice of reference graph models (e.g., random graphs and ring lattices), a common practice that is prone to yield biased interpretations as we show. Application to empirical examples of three categories (neural, social and transportation) evidences that, while most real networks display a pathlength comparable to that of random graphs, when contrasted against the absolute boundaries, only the cortical connectomes prove to be ultra-short.
References in corpus (21)
- The structure and function of complex networks
- Efficient Behavior of Small-World Networks
- Cooperative Game Theory Approaches for Network Partitioning
- Epidemic processes in complex networks
- Synchronization in complex networks
- Spatial Networks
- Resilience of the Internet to random breakdowns
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Universal Behavior of Load Distribution in Scale-free Networks
- Community Structure in Jazz
- Structural Properties of the Caenorhabditis elegans Neuronal Network
- Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems
- Random Walks on Multiplex Networks
- Navigability of Complex Networks
- Average path length in random networks
- Average path length in uncorrelated random networks with hidden variables
- Spreading dynamics in complex networks
- Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
- Functional complexity emerging from anatomical constraints in the brain: the significance of network modularity and rich-clubs
- A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
- The shape of shortest paths in random spatial networks