Connectivity Distribution of Spatial Networks

Abstract

We study spatial networks constructed by randomly placing nodes on a manifold and joining two nodes with an edge whenever their distance is less than a certain cutoff. We derive the general expression for the connectivity distribution of such networks as a functional of the distribution of the nodes. We show that for regular spatial densities, the corresponding spatial network has a connectivity distribution decreasing faster than an exponential. In contrast, we also show that scale-free networks with a power law decreasing connectivity distribution are obtained when a certain information measure of the node distribution (integral of higher powers of the distribution) diverges. We illustrate our results on a simple example for which we present simulation results. Finally, we speculate on the role played by the limiting case P(k)=1/k which appears empirically to be relevant to spatial networks of biological origin such as the ones constructed from gene expression data.

6 pages, 1 figure

References in corpus (10)

• Statistical mechanics of complex networks
• Epidemic spreading in scale-free networks
• Evolution of networks
• Random Geometric Graphs
• Modeling Urban Growth Patterns with Correlated Percolation
• The topology of the transcription regulatory network in the yeast, S. cerevisiae
• Geography in a Scale-Free Network Model
• Extreme self-organization in networks constructed from gene expression data
• Evolving networks with distance preferences
• Giant Clusters in Random Ad Hoc Networks

Cited by in corpus (31)

• Spatial Networks
• Complex network approaches to nonlinear time series analysis
• Self-similar disk packings as model spatial scale-free networks
• The Geometry of Chaotic Dynamics -- A Complex Network Perspective
• Analytical framework for recurrence-network analysis of time series
• A Random Growth Model for Power Grids and Other Spatially Embedded Infrastructure Networks
• WiFi Epidemiology: Can Your Neighbors' Router Make Yours Sick?
• Subgraphs and network motifs in geometric networks
• Worm Epidemics in Wireless Adhoc Networks
• Connectivity Concepts in Neuronal Network Modeling
• Geographical effects on cascading breakdowns of scale-free networks
• Spatial network surrogates for disentangling complex system structure from spatial embedding of nodes
• Cascading failures in spatially-embedded random networks
• Corporate competition: A self-organized network
• Geographical networks evolving with optimal policy
• Impact of network structure on the capacity of wireless multihop ad hoc communication
• Probabilities of spurious connections in gene networks: Application to expression time series
• Growing networks under geographical constraints
• Optimal transport on wireless networks
• A generalised model for asymptotically-scale-free geographical networks
• Scale-free networks embedded in fractal space
• Enhancing Robustness and Immunization in geographical networks
• Random geometric graph description of connectedness percolation in rod systems
• Scale-free network on a vertical plane
• Random spherical graphs
• Complex systems: features, similarity and connectivity
• Levy geometric graphs
• Topological conditions drive stability in meta-ecosystems
• Stochastic model for scale-free networks with cutoffs
• When the spatial networks split?
• Spectral properties of adjacency and distance matrices for various networks