Symmetric motifs in random geometric graphs

Abstract

We study symmetric motifs in random geometric graphs. Symmetric motifs are subsets of nodes which have the same adjacencies. These subgraphs are particularly prevalent in random geometric graphs and appear in the Laplacian and adjacency spectrum as sharp, distinct peaks, a feature often found in real-world networks. We look at the probabilities of their appearance and compare these across parameter space and dimension. We then use the Chen-Stein method to derive the minimum separation distance in random geometric graphs which we apply to study symmetric motifs in both the intensive and thermodynamic limits. In the thermodynamic limit the probability that the closest nodes are symmetric approaches one, whilst in the intensive limit this probability depends upon the dimension.

arXiv comment11 pages

References in corpus (12)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Spatial Networks
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• On Automorphism Groups of Networks
• Synchronization processes in complex networks
• Random geometric graphs with general connection functions
• Proximity Networks and Epidemics
• Worm Epidemics in Wireless Adhoc Networks
• Spectral Characteristics of Network Redundancy
• Synchronization in Random Geometric Graphs
• Mesoscale symmetries explain dynamical equivalence of food webs

Cited by in corpus (1)

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