Levy geometric graphs

Abstract

We present a new family of graphs with remarkable properties. They are obtained by connecting the points of a random walk when their distance is smaller than a given scale. Their degree (number of neighbors) does not depend on the graph's size but only on the considered scale. It follows a Gamma distribution and thus presents an exponential decay. Levy flights are particular random walks with some power-law increments of infinite variance. When building the geometric graphs from them, we show from dimensional arguments, that the number of connected components (clusters) follows an inverse power of the scale. The distribution of the size of their components, properly normalized, is scale-invariant, which reflects the self-similar nature of the underlying process. This allows to test if a graph (including non-spatial ones) could possibly result from an underlying Levy process. When the scale increases, these graphs never tend towards a single cluster, the giant component. In other words, while the autocorrelation of the process scales as a power of the distance, they never undergo a phase transition of percolation type. The Levy graphs may find applications in community detection and in the analysis of collective behaviors as in face-to-face interaction networks.

arXiv commentversion published in PRE

References in corpus (14)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community detection in graphs
• Power laws, Pareto distributions and Zipf's law
• Temporal Networks
• Spatial Networks
• Scale-free correlations in bird flocks
• Hyperbolic Geometry of Complex Networks
• Are biological systems poised at criticality?
• Random Geometric Graphs
• Modeling human dynamics of face-to-face interaction networks
• Connectivity Distribution of Spatial Networks
• Similarity forces and recurrent components in human face-to-face interaction networks