Introduction

The correlated random walk paradigm is the dominant conceptual framework for the modelling of non-orientated movement pattern data (Turchin 1998). It is founded on Brownian motion and the notion that bouts of near unidirectional motions (often called steps) have a characteristic size. Nonetheless, some organisms appear to have movement patterns that fall outside of the paradigm, as they are better represented by Lévy walks (LW) (Korobkova et al. 2004; Reynolds et al. 2007a, b; de Jager et al. 2011; Harris et al. 2012; Humphries et al. 2012, 2013). Lévy walks, named after the French mathematician Paul Lévy, arose in a purely mathematical context in the first half of the last century (Lévy 1937). They first entered the biological literature when Shlesinger and Klafter (1986) proposed that they can be observed in the movement patterns of foraging ants, and in subsequent biological and ecological literature, they are often called Lévy flights. LW comprise clusters of many short steps with longer steps between them. This pattern is repeated across all scales with the resultant clusters creating fractal patterns that have no characteristic scale. Because there is no characteristic scale, the overall length of a LW is dominated by the longest step and the step length variance grows over time but nonetheless remains finite even when unbounded by biological and ecological considerations (Reynolds and Rhodes 2009). When bounded, the minimum and maximum truncation scales introduce characteristic scales which make movement patterns scale finite. But unlike other finite-scale movement patterns, variability around the characteristic scales is huge and self-similar. Truncated LW do, however, become Gaussian (i.e. non-scale free) at large scales by virtue of the central limit theorem. The hallmark of a LW is a distribution of step lengths with a heavy power law tail: p(l) ∼ l − μ with 1 < μ ≤ 3, where l is the step length and μ is the power law (Lévy) exponent (here ‘∼’ means distributed as). Initial evidence for LW in wandering albatrosses (Viswanathan et al. 1996) together with the realisation that these movement patterns can be advantageous in random search scenarios (Viswanathan et al. 1999) led to an explosion of interest in LW as models of animal movement patterns. The superdiffusive movements are theoretically adaptive in heterogeneous and unpredictable environments where they can enhance resource encounter rates over Brownian and ballistic movements when the targets of the search are not rejected or depleted once visited but instead can be profitably revisited. This applies when targets replenish over time or tend to occur in clusters because they are patchily distributed. LW became contentious when it was found that they had been wrongly attributed to the wandering albatross and many other species through the employment of inappropriate statistical techniques and through misinterpretations of the data (Edwards et al. 2007). The situation changed again when Sims et al. (2008) presented strong evidence for LW in a diverse range of marine predator. This evidence began to shift the debate from do animals perform LW to when do they and why (Buchanan 2008). This shift has gained impetus from a steady accumulation of seemingly compelling evidence that many organisms including T cells, Escherichia coli, mussels, honeybees and once again in wandering albatrosses have movement patterns that can be approximated by LW (Korobkova et al. 2004; Reynolds et al. 2007a, b; de Jager et al. 2011; Harris et al. 2012; Humphries et al. 2012, 2013). Nonetheless, LW are at best an approximation to actual movements, and this has prompted the question ‘How “non-like Lévy-like” do the data have to be for them not to be considered as “Lévy-like” anymore?’ (Buchanan 2008). The question is usually addressed by an analysis of the step length distribution, a step length being the straight line distance between two consecutive significant turns. The tail of the distribution is then typically compared with a power law and a null model, such as an exponential. When the tail of the step length distribution is better represented by a power law with 1 < μ ≤ 3, then the movement patterns are considered to be better represented by Lévy walks and less well by correlated random walks. Conversely, when the tail of the step length distribution is better approximated by an exponential distribution, then the movement patterns are better represented by correlated random walks (CRW). Hyper-exponential tails would be indicative of composite correlated random walks (CCRW), i.e. multiphasic walks (Benhamou 2007) which can also be interpreted as self-similar walks, akin to truncated LW when multiple scales are involved (Reynolds 2014). The results of such analyses can be bolstered by the application of other techniques, e.g. a time series analysis (a.k.a. detrended fluctuation analysis), spectral analyses and first digit analyses (a generalisation of Benford’s Law (1938)), which can distinguish between self-similar movement patterns and movement patterns with a few scales (Viswanathan et al. 1996; Reynolds 2012). All of these techniques rely on the determination of turning points in movement paths. In some cases, this determination is straightforward because movements are inherently discrete with reorientation events occurring abruptly or during pauses (Korobkova et al. 2004; Reynolds and Frye 2007; Reynolds et al. 2007a, b; Harris et al. 2012), but in other cases, turn designation has been problematic (Codling and Plank 2011). This is because turn identification methods typically use an arbitrary threshold angle and/or because turns can occur gradually over time. Turn identification is, however, less problematic if movement pattern data is first projected onto a set of principal axes (Sims et al. 2008; Humphries et al. 2013). This is because in one dimension, turns are unambiguous and occur where the direction of travel changes sign and because the self-similar properties of LW are preserved under the projection. Consequently, if the distributions of the movement lengths in both the x- and y-directions each have a power law tail and are characterised by the same Lévy (power law) exponent, then the two-dimensional movement pattern can be represented by a Levy flight (see Sims et al. 2008; Humphries et al. 2013). But even when evidence for step lengths having LW characteristics is compelling, the question about how non-Lévy-like are they remains open. This is because such analyses take no account of actual movements made between significant turns. These movements could, in principle, be perfect straight line as in a true LW but are more likely to be meanderings as in fractal clock random walks (Lévy modulated correlated random walks, Lévy intermittency) (Bartumeus and Levin 2008). Distinguishing between these processes will lead to a better understanding of how and why animals perform LW and help bridge the apparent divide between correlated random walks and LW.

Here, I show that ‘structure functions’ can distinguish between LW, fractal clock random walks, CRW and CCRW, thereby dispensing with the need to identify turns. A structure function of ‘order’ n is just the nth-order moment of the net displacements made in a given time interval. The first and second-order structure functions correspond to net displacements and squared net displacements, quantities that are being used extensively in the context of animal movement analysis (Barraquand and Benhamou 2008; Bunnefeld et al. 2011). Higher-order structure functions provide additional information about the movement pattern data because they are more sensitive to the presence of rarely occurring movement bouts. The new work represents the next step in a progression of rigorous methods that have been developed to distinguish between LW and competing models, such as Brownian walks (Edwards et al. 2007), and more strongly competing or more mechanistic models such as composite correlated random walks (Benhamou 2007; Reynolds 2012). Structure functions have been used to reveal complex multi-fractal, non-Lévy-like scaling in the movement patterns of aquatic crustaceans (Schmitt and Seuront 2001; Dur et al. 2011; Seuront 2010; Seuront and Stanley 2014). Reynolds and Frye (2007) used structure functions to reveal Lévy-like scaling in the flight patterns of Drosophila fruit flies. Seuront and Stanley (2014) subsequently used structure functions to distinguish between different models of movement pattern, including Brownian motion, persistent/anti-persistent random walks, LW and multi-fractal walks. Reynolds and Frye (2007) and Seuront and Stanley (2014) were not faced with the challenge of distinguishing between LW and alternative strongly competing models of movement patterns with self-similar characteristics.

Structure functions and the identification of LW in movement pattern data

Structure functions are the moments 〈|ΔX τ |q〉 of the net displacements |ΔX τ | = [(x(t + τ) − x(t))2 + (y(t + τ) − y(t))2]1/2 made within fixed time intervals, τ, where x(t) and y(t) are the coordinates of an individual at time, t. The angular brackets denote an average along a trajectory. Averaging can also be performed over trajectories if several trajectories are available. Here, without loss of generality, attention is focused on two-dimensional movement patterns. Klafter et al. (1987) showed that a power law relationship of the form 〈|ΔX τ |〉 ∝ τ α with α = 1 is indicative of LW with μ < 2 whilst that with α = 2 − μ/2 is indicative of LW with μ > 2. These scaling relations hold true irrespective of the dimensionality of the movement pattern. Here, I posit that the scaling relation extends to higher moments so that 〈|ΔX τ |q〉 ∝ τ α * q. This ansatz is supported by the results of numerical simulations shown later. It is consistent with the results of Dhar et al. (2013) who determined the exact form of 〈|ΔX τ |2〉 for 2 < μ < 3. Dhar et al. (2013) showed that 〈|ΔX τ |2〉 ∝ τ α * 2. This scaling behaviour should not be confused with the bilinear scaling that characterises Lévy flights, as defined in the mathematical literature. In the mathematical literature, the term Lévy flights refers to discrete random jump processes rather than to continuous random walk processes as in the biological and ecological literature. These mathematical Lévy flights are characterised by α = 1/(μ − 1) for q < μ − 1 and by α = 1/q for q ≥ μ − 1 (Chechkin and Gonchar 2000; Nakao 2000). Notice that the second-order structure function (the mean-squared position) for a true Levy flight grows linearly in time and therefore has a 'normally diffusive' characteristic. Correlated random walks (CRW), composite correlated random walks (CCRW) and other random walks with a few scales are characterised by α = 1/2. Short-term correlations in the data may cause the initial slope of a plot of log 〈|ΔX τ |q〉/log τ to differ from 1/2, although it will still approach 1/2 at longer times. Movement patterns produced by any walk with a few scales must eventually become Brownian (and so characterised by α = 1/2) by virtue of the central limit theorem. This theorem does not apply when movements are self-similar. The α = 1/2, Brownian-like scaling is markedly different from the α = 1, ballistic-like scaling, associated with optimal LW searching (Viswanathan et al. 1999). Consequently, structure functions have the potential to cleanly discriminate between random walks with a few scales and LW with and without truncation. When, as in the case of the copepod Temora longicornis (Schmitt and Seuront 2001), movement patterns cannot be characterised by a single value of α, the movement pattern is said to be ‘multi-fractal’. Higher-order structure functions with q > 1 can therefore discriminate between LW and multi-fractal walks. Note, however, that accurate computation of high-order structure functions requires relatively large data sets and is not possible if data are scarce.

Application of structure function analyses to movement pattern data for honeybees and Drosophila

The aforementioned power law scaling 〈|ΔX τ |q〉 is, however, only obtained asymptotically and is not realised fully by truncated LW that can be captured in movement pattern data. This is illustrated in Fig. 1a which shows structure functions characterising movement pattern data for honeybees attempting to locate their hive (Reynolds et al. 2007a). Reynolds et al. (2007a) reported on the flight paths of bees that had been captured at a feeder, artificially displaced and then released. The bees were fitted with transponders and then tracked using a harmonic radar. The tracks showed that the bees initially tended to make long looping flights away from the release point, as though they were searching systematically for their hive. Analyses were based upon 60 recorded flight patterns. Fifty-six flights terminated in the immediate vicinity of the hive. Flight durations ranged from 128 to 7286 s. Flight lengths ranged from 341 to 14,187 m and had a mean of 2153 m. The structure functions for these flights show power law scaling over about one decade, from the 3-s data sampling interval to about 60 s. Least squares regressions of log 〈|ΔX τ |q〉 on log τ for q = 1, 2 and 3 yield a consistent estimate for the scaling exponent, α ≈ 0.7. The estimates for α * q corresponding to q = 1, 2 and 3 are, with 95 % confidence intervals, 0.69 ± 0.01, 1.42. ± 0.02 and 2.16 ± 0.03, and in each case, R 2 = 0.99. Scaling to this precision is also evident in analyses using just ten randomly selected flight patterns. For longer time intervals, plots of log 〈|ΔX τ |q〉/log τ differ from α = 0.7 and plateau. Movements are therefore superdiffusive but not ballistic (in which case α = 1). These behaviours are consistent with truncated μ ≈ 2 LW produced in numerical simulations (Fig. 1b). They are markedly different from the expectations for movement patterns with a few scales (Fig. 1a, b) and markedly different from the expectations for LW with Lévy exponents, μ, significantly different from 2 (Fig. 1c). To account correctly for the effects of truncation on scaling, the lengths of the simulated LW were taken to be equal to the average length of the bee flight patterns. And the shortest step length in the simulated LW was taken to be 5 m, the shortest flight length that could be resolved by the harmonic radar. Above the truncation scale, observed and simulated movement patterns are seen to depart from the expectations for LW and acquire Brownian-like characteristics consistent with expectations from the central limit theorem. The close correspondence between the empirical movement pattern data and the simulation data indicates that the honeybee flight patterns can be well approximated by truncated LW with μ ≈ 2 but not by random walks with a few scales such as CRW and CCRW. This is consistent with the results of previous analyses using a variety of techniques including maximum likelihood methods, time series analyses of turning points, spectral and ‘first digit’ analyses, and fractal scaling analyses (Reynolds et al. 2007a; Reynolds 2012). These techniques required the determination of turning points. Closely analogous results were obtained for starved Drosophila flying within a circular experimental arena of diameter 1 m (Reynolds and Frye 2007). These analyses are based upon the flight trajectories of 11 individuals. Flight durations ranged from approximately 5.3 to 67.8 s. For time intervals between the recording interval 1/30 s and the time taken by the flies to cross the arena, which is about and 1 s, structure functions displayed power law scaling that was characterised by α = 0.9 ± 0.01 (R 2 = 0.99). At longer times, the structure functions plateaued because movements were confined. These empirical observations are reproduced in numerical simulations by LW with μ = 2.2 that undergo perfect reflection at the walls of the arena.

Fig. 1
figure 1

Structure function analysis of honeybee flight pattern data showing behaviour consistent with the presence of truncated LW with μ = 2. a Structure functions for empirical data (solid lines). Data has been ensemble averaged over 60 different flight patterns. b Structure functions for simulated truncated LW with μ = 2.2 (solid lines). As with the empirical data, the duration of the longest step is 100 s. Power-scaling behaviour corresponding to α = 0.7 is indicated for q = 1, 2 and 3 (dotted lines). Shown for comparison are the distinctly different short- (short dashed lines) and long-time (long dashed lines) scaling behaviours expected for finite-scale movement patterns such as CRW and CCRW. c The power-scaling parameter α as a function for the Lévy exponent μ for truncated LW produced in numerical simulations

Full size image

The analyses of the honeybee and Drosophila data show how the utility structure functions and set out how they can be used in practice, taking into account sample size, path duration and sampling intensity. It is crucial to compare structure functions derived from empirical data with those derived from a comparable data set of synthetic Lévy walks. The goodness of fit between the empirical data and expectations for LW could, for example, be quantified using an R 2 statistic. If the resulting p value is greater than 0.1, then LW are a plausible model of the movement pattern data; otherwise, LW can be rejected. p values can be calculated following a standard approach advocated by Clauset et al. (2009). In this approach, a large number of synthetic data sets are created, structure functions are found each of these data sets and each of these structure functions is fitted to its own power law model. The R 2 statistic is then found for each structure function relative to its own model. The proportion of these R 2 statistics that is smaller than the R 2 statistic of the empirical data is the p value. For the case of the honeybee flight patterns, p = 0.42.

Distinguishing between LW and more complex mechanistic models

Composite correlated random walks

Composite correlated random walks can be confounded with LWs when, as is often the case, the tail of the step length distribution is compared with a power law and an exponential distribution using maximum likelihood methods (Reynolds 2012). As an illustrative case, Reynolds (2012) showed that with maximum likelihood methods, a CCRW in which step lengths are drawn at random from a bi-exponential distribution, one exponential for relatively short movements with mean length 15 (arbitrary length units) used with a 0.9 probability and the other for relatively long movements with mean length 74 used with a 0.1 probability, is always mistaken for a LW with μ = 2. The two patterns of movement can, however, be distinguished using power spectral and first significant digit analyses, approaches which require turn designation (Reynolds 2012). They can also be distinguished using structure functions (Fig. 2). The structure functions are indicative of ballistic (straight line) movements at short times, and Brownian movements at long times, and so are consistent with general expectations for random walks with a few scales but unlike the expectations for a realisable LW (Fig. 2). This becomes ever more evident as the order of the structure function increases (Fig. 2).

Fig. 2
figure 2

Structure function analysis of a CCRW (solid lines) which maximum likelihood methods misidentify as being a LW with μ = 2. The structure functions are consistent with the expectations for movement patterns with a few scales, i.e. ballistic movements at short times and Brownian movements at long times (dashed lines), and markedly different from the expectations (α = 0.7) for a LW with μ = 2 (dotted lines)

Full size image

Fractal clock random walks

At the start of each walking bout in a fractal clock random walk, a new bout duration is extracted from a distribution with a heavy power law tail, and a new direction of travel, θ(t), is selected at random from a uniform distribution ranging between 00 and 3600 (Bartumeus and Levin 2008). At each tick of the clock, i.e. at each unit time interval, ∆t, the walker moves forward with uniform speed. The direction travel is then incremented by a random amount φ(t + Δt) so that the next step is made in the direction θ(t + Δt) = θ(t) + φ(t + Δt) and so that the walker meanders between the fractal-timed reorientation events where the direction of travel changes abruptly so that directional persistence is lost entirely. Structure function analysis reveals that movement patterns closely resemble LW at short times but that scale-free behaviour is lost at long times, i.e. meandering results in truncated LW even when the fractal clock produces ticks of arbitrarily long duration (Fig. 3). This is simply because relatively short bouts will produce relatively straight steps as in LW whilst relatively long bouts (spanning many meandering cycles) will produce irregular steps with numerous turns.

Fig. 3
figure 3

Structure function analysis of a fractal-timed random walk (solid lines) putatively corresponding to at LW with μ = 2. The walkers move with speed in arbitrary space-time units. Changes in the direction of travel made at each tick of the fractal clock are randomly and uniformly distributed between −450 and 450. Power-scaling behaviour corresponding to α = 0.76 indicative of a truncated LW is indicated (dotted line)

Full size image

Discussion

In recent years there has been an accumulation of evidence that the movement patterns of many organisms can be approximated by LW, i.e. by a movement pattern that is self-similar across a range scales (Korobkova et al. 2004; Reynolds et al. 2007a, b; Sims et al. 2008; de Jager et al. 2011; Harris et al. 2012; Humphries et al. 2012, 2013). This evidence comes principally from distributions of straight line distances travelled between consecutive significant turns that, to good approximation, have heavy power law tails. Step length distributions with thin (exponential) tails are the hallmark of finite-scale movement patterns like CRW and some CCRW. Designation of turning points is, however, often arbitrary and reflects measurement resolution rather than a naturally occurring pattern (Codling and Plank 2011). Even when much of this ambiguity is removed, as in the ‘projection’ approach advocated by Humphries et al. (2013), analyses based solely on turning points cannot account for movements made between turns and so cannot discriminate between different kinds of LW. Here, it was shown how structure functions which dispense with turning point designation can be used to discriminate between self-similar movement patterns and movement patterns with a few scales. The utility of the method was illustrated by its application to telemetry data for honeybees searching for their hive (Reynolds et al. 2007a). The structure function analyses revealed that the honeybee flight patterns can be approximated by LW with μ ≈ 2 and are distinctly different from movement patterns with a few scales (Fig. 1a, b). It was further demonstrated by examining simulation data for a bi-modal CCRW that was tuned to resemble a LW over a range of scales (Fig. 2). As more and more modes are added, a CCRW can be tuned to make its resemblance with LW even more precise (Reynolds 2014), and in this case, structure functions along with other diagnostic tools may not be able to distinguish between a true LW and its realisation as a CCRW. But in these situations, LW and CCRW would not be competing models of the movement pattern data. Instead, the LW could be viewed as simple integrative models whilst the CCRW with their added complexity would provide more mechanistic descriptions of movement patterns revealing how organisms approximate LW. The fine-tuning does, after all, require selection pressures for Lévy-like movement patterns (Reynolds 2014). Without such fine-tuning (selection for Lévy characteristics), the resemblance would be an unexplained occurrence.

Representations of movement pattern data in terms of LW will always be approximate, in part because movement bouts can not be perfect straight line movements but will instead exhibit some degree of meandering. Bartumeus and Levin (2008) showed how such meandering can be encapsulated by fractal clock random walks (e.g. Lévy modulated correlated random walks, Lévy intermittency) where organisms randomly meander rather than move in straight lines between consecutive reorientation events. Meandering introduces a truncation scale below which movement patterns are self-similar and above which they behave as random walks with a few scales. Meandering thereby modifies resource encounter rates and so can have important ramifications for the interpretation of self-similar movement pattern in terms of advantageous foraging behaviours (Bartumeus and Levin 2008). Identification of this truncation scale is also of importance when attempting to extrapolate from observational scales to expectations at larger scales. Here, it was shown that this truncation scale can be extracted from structure function analyses of entire movement patterns. Identifying this range of scales cannot be achieved by statistical techniques such as maximum likelihood methods that focus attention exclusively on turning points and individual steps. It can only be determined from whole-path analyses. Previously, this could be assessed using the time series analysis adopted by Viswanathan et al. (1996), but this diagnostic requires the determination of biological significant turns.

This ability to distinguish between different self-similar processes addresses directly a major challenge in movement ecology, namely to ‘understand how reorientation mechanisms are integrated into the set of traits enabling the execution of movement and how navigation capacity and/or internal states of the animal can control and modify reorientation patterns based on different external stimuli’ and to ‘help to discriminate between different causes for Lévy patterns in animal movement’ (Bartumeus and Levin 2008). In this regard, it would be interesting to use structure functions to examine the extent to which marine predators with self-similar movement patterns are true LW (Sims et al. 2008). The extensive study of Sims et al. (2008) provides the strongest evidence obtained so far for self-similar movement patterns and so warrants further analysis.