Large algebraic connectivity fluctuations in spatial network ensembles imply a predictive advantage from node location information

Abstract

A Random Geometric Graph (RGG) ensemble is defined by the disordered distribution of its node locations. We investigate how this randomness drives sample-to-sample fluctuations in the dynamical properties of these graphs. We study the distributional properties of the algebraic connectivity which is informative of diffusion and synchronization timescales in graphs. We use numerical simulations to provide the first characterisation of the algebraic connectivity distribution for RGG ensembles. We find that the algebraic connectivity can show fluctuations relative to its mean on the order of $30\%$, even for relatively large RGG ensembles ($N=10^5$). We explore the factors driving these fluctuations for RGG ensembles with different choices of dimensionality, boundary conditions and node distributions. Within a given ensemble, the algebraic connectivity can covary with the minimum degree and can also be affected by the presence of density inhomogeneities in the nodal distribution. We also derive a closed-form expression for the expected algebraic connectivity for RGGs with periodic boundary conditions for general dimension.

References in corpus (25)

• Finding community structure in networks using the eigenvectors of matrices
• Spatial Networks
• Hyperbolic Geometry of Complex Networks
• Synchronization in Complex Oscillator Networks and Smart Grids
• Popularity versus Similarity in Growing Networks
• Consistency of spectral clustering
• Random Geometric Graphs
• Hidden geometric correlations in real multiplex networks
• Continuum percolation of wireless ad hoc communication networks
• Emergence of overlap in ensembles of spatial multiplexes and statistical mechanics of spatial interacting networks ensembles
• Random geometric graphs with general connection functions
• Network synchronization: Spectral versus statistical properties
• Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that
• Socioeconomic correlations and stratification in social-communication networks
• Connectivity of soft random geometric graphs
• Ensemble averageability in network spectra
• Eigenvalue Spectra of Modular Networks
• Full Connectivity: Corners, edges and faces
• Dimensionality of social networks using motifs and eigenvalues
• Spreading dynamics on spatially constrained complex brain networks
• Spectral statistics of random geometric graphs
• Connectivity of Soft Random Geometric Graphs Over Annuli
• Entropy of Spatial Network Ensembles
• Symmetric motifs in random geometric graphs
• Sample-to-sample fluctuations in real-network ensembles