  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.
