Abstract
Experimental observations of animal collective behaviour have shown stunning evidence for the emergence of largescale cooperative phenomena resembling phase transitions in physical systems. Indeed, quantitative studies have found scalefree correlations and critical behaviour consistent with the occurrence of continuous, secondorder phase transitions. The standard Vicsek model (SVM), a minimal model of selfpropelled particles in which their tendency to align with each other competes with perturbations controlled by a noise term, appears to capture the essential ingredients of critical flocking phenomena. In this paper, we review recent finitesize scaling and dynamical studies of the SVM, which present a full characterization of the continuous phase transition through dynamical and critical exponents. We also present a complex network analysis of SVM flocks and discuss the onset of ordering in connection with XYlike spin models.
1. Introduction
Nature offers abundant manifestations of collective motion phenomena in selfpropelled living systems at all scales, from biomolecular micromotors, migrating cells and growing bacteria colonies, to insect swarms, fish schools, bird flocks, mammal herds and even human crowds. Instead of focusing on the specific details that make each of these biological systems unique, statistical physicists have been studying the general patterns of biological collective motion, aiming to identify the general laws and underlying principles that may govern their behaviour [1].
From this perspective, one important question to address is the onset of ordered macroscopic phases, i.e. the way in which individuals having shortrange interactions are capable of selforganizing into largescale cooperative patterns in the absence of leaders or other ordering cues from the environment. By analogy with large molecular systems, flocking and swarming phenomena can be associated with phase transitions that depend on a few parameters that characterize the macroscopic states, such as the density of individuals and the flock size. For instance, Buhl et al. [2] investigated the collective motion of locusts, which display a densitydriven transition from disordered movement of individuals within the group to highly aligned collective motion. In analogy with secondorder (or continuous) phase transitions in physical phenomena such as critical opalescence, in which liquids appear opaque owing to density fluctuations at all wavelengths of visible light, the onset of a coordinated alignment in the motion of marching locusts was found to display secondorder behaviour. Moreover, a critical locust density for the occurrence of the continuous phase transition was identified.
Familiar to most of us is also the rich variety of collective motion phenomena displayed by flocks of birds, where highly correlated longrange ordering effects are readily apparent (see [3] for some stunning footage of complex flocking patterns and other kinds of swarm behaviour). Indeed, some studies have quantitatively characterized the formation of ordered bird flocks in terms of continuous phase transitions. For instance, Cavagna et al. [4] obtained highresolution spatial data of thousands of starlings using stereo imaging in order to calculate the response of a large flock to external perturbations. This study showed that behavioural correlations are scalefree, a signature of critical states in secondorder phase transitions. Correlation functions revealing the pairwise interaction between homing pigeons have recently been investigated by means of highresolution lightweight GPS devices as well [5].
On the theoretical side, Vicsek et al. [6] proposed a minimal model to study the onset of order in systems of selfdriven individuals, which was later followed by other investigations by means of agentbased modelling [7,8], the Newtonian forceequation approach [9,10] and the hydrodynamic approximation [11,12]. This socalled standard Vicsek model (SVM) assumes that neighbouring individuals tend to align their direction of movement when they are placed within a certain interaction range. This alignment rule, which would trivially lead to fully ordered collective motion, is complemented by a second one that introduces noise in the communications among individuals. The SVM assumes that each individual can assess exactly the direction of its neighbours, but it incurs an error when adjusting its own direction of motion to match that of its neighbours' average. This type of noise, sometimes identified as angular noise (AN), was shown to drive the system through a secondorder transition between the ordered phase of collective motion and a disordered phase. Although several variations to the SVM have later been considered in the literature, such as different noise types, models without alignment rule, adhesion between neighbour individuals, bipolar particles, etc. (see [1] for a review), here we will chiefly focus on the original SVM, as formulated by Vicsek et al. [6] in their seminal paper.
In this context, the aim of this work is to review recent findings for the SVM that confirm the continuous nature of the order–disorder phase transition driven by the noise amplitude, as well as to present a novel complex network analysis that provides new insights into the onset of ordering. The rest of this paper is organized as follows. In §2, we present the definition of the SVM. Section 3 reviews recent finitesize scaling and dynamical studies of the SVM, leading to a fully quantitative characterization of the continuous phase transition through dynamical and critical exponents. In §4, we present a complex network analysis of SVM flocks, we study their topology and we discuss the onset of ordering in connection with XYlike spin models. Finally, our conclusions appear in §5.
2. The standard Vicsek model
The SVM [6] consists of a fixed number of interacting particles, N, which are moving on a plane. In computer simulations, that plane is represented by a square of side L with periodic boundary conditions [6,13]. The particles move offlattice with constant and common speed . Each particle interacts locally, adopting the direction of motion of the subsystem of neighbouring particles (within an interaction circle of radius centred in the considered particle), which is then perturbed by the presence of noise. Because the interaction radius is the same for all particles, we adopt the interaction radius as the unit of length throughout, i.e. .
The evaluation of the average angle of motion of each individual's neighbours at time t, , is affected by a noise term. Hence, the updated direction of motion for the ith particle, , is given by 2.1where η is the noise amplitude, the summation is carried over all particles within the interaction circle centred at the ith particle and is a realization of a δcorrelated white noise uniformly distributed between −π and π. The noise term can be thought of as due to the error committed by the individual when trying to adjust its direction of motion to the averaged direction of motion of its neighbours.
The model dynamics is usually implemented by adopting the socalled backward update rule: after the position and orientation (velocity) of all particles are determined at time t, the position of the particles at time t + 1 is updated according to 2.2which is then followed by the update of all velocities at time t + 1 according to equation (2.1). However, different updating schemes implemented in the literature may lead to spurious effects in the simulations [14].
The parameters of the model are the number of particles N, the dimension of the displacement space d, the linear size of the displacement space L, the interaction radius , the particle density ρ, the particle speed and the noise amplitude η. Notice, however, that , where in the standard case, and that can be chosen as the unit of length. Moreover, merely plays the role of a ‘thermalization parameter’ that measures how many times, on average, two neighbours check out each other's positions while they remain at a distance within the unitary interaction radius. Therefore, relatively large values of speed (typically ) correspond to the lowthermalization regime, characterized by highly anisotropic diffusion and the manifestation of simulation artefacts in the form of directionally quantized density waves (see [15] for details). The relevant region of parameter space addressed in this paper is the highthermalization regime for that guarantees isotropic diffusion. Within this regime, the choice of has only mild effects on the order parameter probability distributions and it does not affect the nature of the phase transition [13].
3. Critical behaviour of the standard Vicsek model: finitesize and dynamic scaling
The SVM exhibits a farfromequilibrium continuous phase transition between ordered states of motion at low noise levels and disordered motion at high noise levels. The natural order parameter is given by the absolute value of the normalized mean velocity of the system [6,16]: 3.1where φ is close to zero in the disordered phase and close to unity in the ordered phase. In order to analyse the critical nature of the phase transition exhibited by the SVM, we have studied the behaviour of the order parameter φ and other quantities related to the probability distribution of φ, such as the susceptibility ) and the Binder cumulant ). The phase transition has been investigated by means of two independent approaches, namely a finitesize scaling analysis and a shorttime critical dynamic technique [16,17].
Let us briefly mention that the secondorder nature of the SVM farfromequilibrium phase transition has been a matter of some debate. In fact, early simulations by Vicsek's group, which were consistent with a continuous secondorder transition [6], were later challenged by Grégoire & Chaté [18], who claimed that the transition was discontinuous, i.e. of first order. The controversy was further stimulated by subsequent papers of Vicsek and coworkers [15,19], Aldana and coworkers [8,20–22], Dossetti et al. [23] and Baglietto & Albano [13,14,16], supporting the critical nature of the transition, which were in conflict with additional results published by Chaté et al. [24–26]. In the remainder of this work, we assume that the SVM (using the socalled AN type) undergoes a secondorder phase transition. For further details, see [14,15,22].
While critical systems are characterized by the divergence of correlation length and time scales, computational simulations are limited to systems of finite extent and finite time observation intervals. In systems of finite size L (where, in our case, the correlation length cannot grow beyond L. Instead of the theoretically expected power laws at criticality (e.g. and , where τ represents the distance to the critical point and β and γ are critical exponents), for finitesize samples of critical systems, stationary quantities must obey scaling laws of the form 3.2and 3.3where and are scaling functions, and is the correlation length critical exponent. In the case of the SVM, a very good agreement between simulation results and equations (3.2) and (3.3) is obtained. Figure 1 shows the behaviour of φ versus η for different sizes and densities, while figure 2 displays the collapse obtained by applying equation (3.2) to a known scaling law for the densities [16]. The values of β and used in the simulations are listed in table 1.
On the other hand, when a critical system, initially placed either in a ground state or in the disordered phase, is suddenly brought to the critical point, it is also possible to measure its critical dynamic evolution. In this way, one can obtain not only the static exponents (β, and γ) but also the dynamic exponent z that governs the timedependent growth of the correlation length [17]. Table 1 summarizes the exponents obtained for the SVM by means of stationary and dynamic measurements [16].
Considering statistical errors, the obtained exponents satisfy the hyperscaling relationship ), which is firmly established for critical systems in equilibrium but less documented for the case of nonequilibrium critical systems [27]. This finding is a strong indication that the SVM undergoes a continuous nonequilibrium phase transition. It worth mentioning that the set of critical exponents found for the SVM constitutes a new universality class. Also, the agreement between results obtained from stationary and dynamic measurements provides strong support to the SVM's critical nature.
4. The onset of orientation ordering in standard Vicsek model flocks
The SVM, which describes a farfromequilibrium phenomenon, has often been compared with another archetypical case in the study of critical phenomena but under equilibrium conditions, namely the XY model [28,29]. In the XY model, nearestneighbour interacting spins may adopt any possible orientation, depending on the strength of the interactions and the temperature. By considering the SVM as a model of interacting spins that can undergo displacements in the direction of the spin, the basic difference between both models is precisely due to those displacements. In fact, other relevant symmetries for the study of phase transitions, such as the dimensionality of the space, the nature of the order parameter and the range of the interactions, are the same in both models. On the other hand, it is well known that, according to the Mermin–Wagner theorem [30,31], the XY model, as well as all other equilibrium systems in two dimensions with shortrange interactions and O(2) symmetry defined on translationally invariant substrates, cannot display ordered phases. Therefore, the onset of ordering in the SVM in two dimensions is quite intriguing. What is, then, the essential ingredient that generates the ordered phase of SVM flocks, despite Mermin–Wagner? Naturally, the possible answers lie in the conditions required by the theorem to apply, which are not met by the SVM, namely:

— the SVM is nonequilibrium (e.g. particle interactions do not conserve momentum);

— SVM ‘spins’ move and originate effective longrange interactions (flocks merge and dismember, carrying information across the system); and

— the SVM ‘substrate’ is not translationally invariant (particle positions are distributed inhomogeneously in space).
It is worth mentioning that the XY model defined on onedimensional smallworld networks (generated by the addition of a small number of random longrange ‘shortcuts’ on top of a regular onedimensional lattice) was found capable of sustaining ordered phases [32,33]. Hence, the inhomogeneous arrangement of particle positions in the twodimensional displacement space, interpreted as a complex network substrate in which ‘spins’ undergo ferromagnetic interactions, could arguably be the key ingredient that allows the onset of ordered clusters in the SVM.
In order to explore this further, let us define the concept of flocks as complex network structures. Starting with a disordered initial state in which individuals are randomly located within the displacement space, SVM rules lead to the formation of local structures of interacting individuals. These structures, which we call flocks or clusters, are not permanent: their shape and size evolve with time, with new individuals and subflocks merging with them and, conversely, other individuals and subflocks separating from them. Moreover, besides the statistical perspective in which flocks are the fundamental building blocks of the ensembles that characterize SVM stationary states, flocks can be regarded as ‘domains’ that carry key information on the ordering of the system at the mesoscopic level.
In order to gain insights into the structure of the clusters, let us evaluate the average path length (APL) [34]. According to the standard definition used in the study of complex networks, for each pair of nodes or individuals (A, B) belonging to the same cluster, the path length (also known as chemical distance) is given by the minimum number of links that one has to use in order to pass from one node to the other. By calculating all the pairwise nodetonode path lengths in the cluster and taking the average, one obtains the , which consequently is a characteristic length of the cluster. In Euclidean lattices, the volume of an object is related to its characteristic length by an integer power, i.e. the dimension of the object. On the basis of observation, as well as on the experience gained in the study of fractal objects, it is customary to define the dimension (D) of a complex network according to 4.1where is the complex network size or, in the present context, the cluster mass [34]. Figure 3 shows a log–log plot of the versus for SVM flocks corresponding to the critical point of the secondorder phase transition. The best fit to the data yields D = 4(2), which strongly suggests that the effective dimension of the clusters is D = 4. Other complex network measures, not shown here for the sake of space, confirm that SVM flocks are characterized by a fourdimensional topology [35].
As mentioned already, flocks can be regarded as domains that carry important information on the ordering of the system at the mesoscopic level. Therefore, let us now study the onset of order within individual flocks as a necessary condition to have macroscopic ordering systemwide. Notice, however, that the detailed mechanisms leading to the emergence of global order from locally ordered clusters are not well understood yet and remain an open question that lies beyond the scope of the present analysis.
With this aim, here we investigate whether the topology of the socalled frozen clusters, once particle displacements and cluster rearrangements are suppressed, is capable by itself of supporting the existence of an orientationally ordered phase. In our approach, we first generate configurations of clusters by applying the full SVM dynamics. Once the nonequilibrium stationary state is reached, we identify the clusters and ‘freeze’ them, i.e. we disallow any further displacements of the individuals. From that point on, the orientation of the particles is allowed to evolve according to equation (2.1), but subsequent displacements (equation (2.2)) do not occur. We will refer to this stage as ‘restricted SVM dynamics’. Because the full SVM dynamics has an entanglement between particle displacements and XYtype interactions, by resorting to ‘frozen clusters’, we disentangle these two major components. This procedure allows us to explore the relation between local topology and the ability for the restricted SVM dynamics to sustain local ordering.
Figure 4 shows the dependence of the order parameter φ on the inverse cluster mass . The clusters were first generated using the full SVM dynamics with critical noise. After freezing them, the restricted SVM dynamics was applied using different noise values in the range, as indicated. Even for very large noise amplitudes, the order parameter in the large cluster limit () tends to finite values, e.g. for . Although we are not presenting here a full finitesize scaling analysis, these results were obtained for a large system size () and they provide strong evidence that frozen clusters are capable of sustaining order () in the thermodynamic limit ). The inset to figure 4 shows the order parameter extrapolations to the limit, , as a function of the noise amplitude . For the sake of comparison, the inset also shows exact results from the mean field solution obtained for an infinite density of individuals [23], which closely follow the trend of our computer simulation results. Recalling that the effective dimension of SVM clusters is D = 4, we argue that the observed meanfieldlike behaviour is related to the fact that D = 4 is the uppercritical dimension of the XY model, which essentially has the same symmetries as the SVM defined on frozen clusters.
Therefore, our findings indicate that the full SVM dynamics creates flocks with enhanced connectivity, which behave as fourdimensional objects compactified into a twodimensional displacement space (more details will be published elsewhere [35]). By virtue of this higherdimensional complex network substrate, the approximately equivalent XY representation (attained by our ‘frozen cluster’ procedure) displays meanfieldlike behaviour, thus solving the apparent paradox posed by the Mermin–Wagner theorem.
5. Conclusions
In this work, we revisit the SVM, a minimal model of selfpropelled particles that displays a noisedriven phase transition between the ordered phase (in which individuals align with each other and move coherently systemwide) and the disordered phase (in which the net translational motion averages out to zero). By means of a combined finitesize scaling and dynamical analysis of the SVM, we present a full characterization through dynamical and critical exponents and confirm the nature of the SVM phase transition as continuous (second order), in agreement with the early results by Vicsek et al. [6]. Finally, we analyse the onset of ordering in SVM flocks by performing a complex network analysis and interpreting the results in connection with XYlike spin models.
In a forthcoming paper [35], we will extend the complex network analysis of Vicsek flocks to variants of the model, in which perturbations are implemented either as AN or as vectorial noise (VN). We believe that this topological approach will provide key insights into the different nature of the ordering phase transitions observed in the Vicsek model under the two noise types, namely continuous second order for AN and first order for VN. Indeed, the connection between the order of the transition and the topology of the flocks remains an important open question that certainly deserves further investigation.
Acknowledgements
This work was financially supported by CONICET, UNLP and ANPCyT (Argentina).
Footnotes
One contribution of 11 to a Theme Issue ‘Collective motion in biological systems: experimental approaches joint with particle and continuum models’.
 Received March 21, 2012.
 Accepted June 12, 2012.
 This journal is © 2012 The Royal Society