Numerical models indicate that collective animal behaviour may emerge from simple local rules of interaction among the individuals. However, very little is known about the nature of such interaction, so that models and theories mostly rely on aprioristic assumptions. By reconstructing the three-dimensional position of individual birds in airborne flocks of few thousands members, we prove that the interaction does not depend on the metric distance, as most current models and theories assume, but rather on the topological distance. In fact, we discover that each bird interacts on average with a fixed number of neighbours (six-seven), rather than with all neighbours within a fixed metric distance. We argue that a topological interaction is indispensable to maintain flock's cohesion against the large density changes caused by external perturbations, typically predation. We support this hypothesis by numerical simulations, showing that a topological interaction grants significantly higher cohesion of the aggregation compared to a standard metric one. Collective behaviour of large aggregations of animals is a truly arresting natural phenomenon (1). Particularly interesting is the case when aggregations self-organize into complex patterns with no need of an external stimulus. Prominent examples of such behaviour are bird flocks (2), fish schools (3) and mammal herds (4). Apart from its obvious relevance in ethology and evolutionary biology, collective behaviour is a key concept in many other fields of science, including physics (5), control theory (6), mobile robotics (7), economics (8), and social sciences (9). How does collective behaviour emerge? Numerical models of self-organized motion, inspired both by biology (10, 11, 12, 13, 14, 15, 16) , and by physics (17, 18, 19) , support the idea that simple rules of interaction among the individuals are sufficient to produce collective behaviour. Unfortunately, we have very scarce empirical information about the precise nature of such rules. The main theoretical assumptions (attraction among the individuals, short range repulsion, and alignment of the velocities) are reasonable, but generic, and there are as many different models as different ways to implement these assumptions. Without decisive experimental feedback it is difficult to select what is the 'right' model, and therefore to understand what are the underlying fundamental rules of animal collective behaviour. The main goal of the interaction among individuals is to maintain cohesion of the aggregation. This is a very strong biological requirement, shaped by the evolutionary pressure for survivor: stragglers and small groups are significantly more prone to predation than animals belonging to large and highly cohesive aggregations (3, 20) . Consider a flock of starlings under attack by a peregrine falcon: the flock contracts, expands and even splits, continuously changing its density and structure. Yet, no bird remains isolated, and soon the flock reforms as whole. The question we want to answer is: what kind of interaction maintains cohesion in such a robust way? Dramatic density changes as the ones observed in animal aggregations are not at all common in physical systems: the density of an aggregate of particles is changed by changing the external constraints, as the volume of the box containing a gas. When, on the other hand, particles condensate in open space, the density is determined mainly by 3 the dependence of the inter-particle force on the distance, dependence that is a characteristic of the material and is therefore fixed. If the aggregation is subject to a strong external perturbation, density does not vary, but cohesion breaks down. Flocks and schools, however, live in an open space, and yet undergo enormous density changes without losing cohesion, in a very flexible way. This seems a challenging problem when tackled within the framework of standard physical interactions. To grant cohesion, models make the sound assumption that individuals align and attract to each other, and that such interaction decays with increasing distance between individuals. The vast majority of models, both developed by physicists and biologists, adopt a definition of 'distance' that is the same as in physics, i.e. metric distance. In a metric context, two birds 5 meters apart attract each other less than two birds 1 meter apart. Animals can estimate metric distance in various ways, including stereovision, retinal image size, and optic flow (21). Thus, a metric interaction seems natural. However, physical systems warn us that an interaction based on metric distance may be unable to reproduce the density changes typical of animal aggregations. An alternative is topological distance. In economics, for example, the relevant quantity is not how many kilometres separate two countries (metric distance), but rather the number of intermediate countries between them (topological distance) (22) . If the interaction depends on the topological distance, each individual interacts with a fixed number of neighbours, irrespective of their metric distance. The crucial difference between metric and topological interaction really kicks in when the density varies: in the topological case, two birds 5 meters apart in a sparse flock attract each other as much as two birds 1 meter apart in a denser flock, provided that the number of individuals between the two birds is the same. The strength of the interaction remains the same at different densities. This seems more suitable to keep cohesion in the face of strong density fluctuations. By means of empirical observations we show that the topological paradigm is in fact the correct one. Structure is the foremost effect of interaction, and, conversely, interaction is ciphered in the inter-individual spatial structure. Hence, in order to learn something about the interaction ruling collective behaviour it is necessary to analyze the structural organization of individuals within the aggregation. To do this, however, it is essential to have data on the 3D positions of individuals in large aggregations: collective behaviour is a qualitatively different phenomenon, with emerging complex patterns, only when the number of individuals is big; moreover, in small aggregations the surface-to-volume ratio is large, and the bias introduced by the border is inevitably very strong (see Methods). Unfortunately, gathering quantitative 3D data on even moderately large groups of animals is very difficult. Most empirical studies have two major limitations: a small number of individuals (few tens), and loose group arrangements (23, 24) , at variance with the huge, highly cohesive natural aggregations. Thanks to novel stereometric and computer vision techniques, we measured 3D individual birds positions in compact flocks of up to 2600 starlings (Sturnus vulgaris) in the field. This is an advance of almost two orders of magnitudes compared to former experiments. A typical flock and its 3D reconstruction are shown in Fig.1 (see also Figs.S3 in Supplementary Material [SM]). Starlings' aerial display provides a 4 paradigmatic case of collective behaviour (25). These birds gather in the evening over the roost and form sharp-bordered, strongly cohesive flocks, ranging from few hundreds to tens of thousands birds (see SM Figs.S1-S2). We reconstructed and analyzed ten flocking events recorded at the roosting site of Termini railway station (Rome, Italy) between Dec. 2005 and Feb. 2006. Each event is defined by a series of up to 80 stereo photographs, shot at 10 frames-per-second. Different events correspond to different flocking flight sequences, recorded on separate sessions. Observations were done at dusk. Details on the experiment and on the reconstruction algorithms can be found in the Materials and Methods section. The clearest characterization of the structure of birds within a flock is given by the spatial distribution of the nearest neighbours. Given a reference bird, we measure the angular orientation of its nearest neighbour with respect to the flock's direction of motion, i.e. the neighbour's bearing and elevation. We repeat this by taking all individuals within a flock as reference bird, and in this way we map the average spatial position of nearest neighbours (see caption of Fig.2 ). This map (Fig.2a) shows a striking lack of nearest neighbours along the direction of motion. The structure of individuals is therefore strongly anisotropic. The possible reasons for this anisotropy, probably related to the visual apparatus of birds, are discussed in SM. The crucial point, however, is that this anisotropy is the effect of the interaction among individuals. To support this claim, we compute the distribution of neighbours very far apart from the reference bird (Fig.2b ). This distribution is uniform, as for a completely isotropic, non-interacting aggregation of points. This is a direct empirical indication that interaction decays with the distance, and it demonstrates that we can use the anisotropy to get information about the interaction (see also SM on this point). To quantify the decay of the anisotropy we define a function g(n) that measures to what extent the spatial distribution of the n th -nearest neighbour around a reference bird is anisotropic (see caption of Fig.3 ). The value of g for an isotropic, non-interacting aggregation is 1/3. A value larger than 1/3 indicates that the interaction among the birds makes the structure anisotropic. In Fig.3a we show that g(n) decays gradually to 1/3 when n increases. Hence, for each flock we can define an interaction range n c , given by the value of n where g becomes 1/3. By definition, birds farther than the n c th nearest neighbour are isotropically distributed around the reference bird, and do not interact with it. We note that Fig.3a is the first empirical determination of how the interaction decays in a real instance of collective behaviour. The n th nearest neighbour of a given bird is characterized not only by its integer label n, but also by its actual distance in meters r from the reference bird. For example, in flock 32-06 (Fig.3b ) the 6 th nearest neighbour of a bird is found, on average, at 1.25m from it. Clearly, the relation between n and r depends on the specific density of the flock. While n measures the topological distance from a reference bird, r measures the metric distance. In addition to the topological interaction range in unit of birds, n c , we can therefore introduce a metric range, in unit of meters, r c . Going back to flock 32-06, we have n c =6, and r c =1.25m (Fig.3a) . The flocks we analyzed differ a lot one from the other in density. This implies that the topological and metric ranges, n c and r c , cannot be both constant from flock to flock. To elucidate this crucial point, let us consider two flocks with different densities. If the interaction depends on the metric distance, then the range in meters r c is the same in the 5 two flocks, while the number of individuals n c within this range is large in the denser flock, and small in the sparser one. Conversely, if the interaction depends on the topological distance, the range in units of birds n c is constant in the two flocks, while the distance r c of the n c th nearest neighbour is small in the denser flock, and large in the sparser one. The difference between topological and metric hypothesis is stark: in the topological scenario the number of interacting individuals is fixed. On the opposite, in the metric scenario, such number varies with density; for example, within the same metric range there are 10 birds in our densest flock, and only 1 bird in the sparsest one. Topological and metric ranges therefore are not interchangeable characterizations of the interaction. Therefore, to understand whether it is the metric or the topological distance that matters we must measure how r c and n c depend on the flocks' density. To cast in a quantitative way the two opposite scenarios, we note that the average distance r of the n th nearest neighbour grows with n according to the relation r ~ r 1 n 1/3 (see Fig.3b ). In this equation r 1 is the average nearest-neighbours distance, which is a direct measure of sparseness (the inverse of density); r 1 varies from 0.68m in the densest flock, to 1.51m in the sparsest one (see table S1 in SM). The equation above simply means that the number n of individuals within a sphere of radius r is proportional to r (Fig.3c,3d) . The topological range is therefore approximately constant from flock to flock. On average, we find n c =6.5±0.9 SE. We therefore showed that the interaction depends on the topological distance, rather than the metric one. The interaction between two birds 1m apart in flock A, is as strong as that between two birds 5m apart in flock B, provided that A is denser than B and that the topological distance n is the same. Our empirical result contrasts with the assumption of most models and theories. Even though some models introduce a cut-off, or numerical preference, in the number of interacting neighbours (so that this number is fixed), they still 'weight' these neighbours metrically (26). We must stress that this is not what we find here. It is the very shape of the interaction that depends on the topological distance, not simply the cut-off, or the range (Fig.3a) . Our result also rules out for starling flocks the hypothesis that the anisotropic structure is a consequence of the bird's effort to take advantage of the wakes of its neighbours (27), since such aerodynamic advantage would decay within a well-defined metric length-scale (see SM for a discussion of this point). In fact, we believe that the only mechanism compatible with our result is vision. Why 6-7 neighbours? This range is significantly smaller than the number of visually unobstructed neighbours around each bird. We conclude that this specific value of n c must derive from the cortical elaboration of the visual input, rather than from a limitation of the input itself. In order to keep under control a fixed number of 6 neighbours, irrespective of their metric distance, it is necessary for the individuals to have some pre-numeric ability, or, more precisely, an object-tracking, or 'subitizing', ability (28). This capability decays beyond a certain number, and such perceptual limit defines the range of interaction. Laboratory experiments show that trained pigeons can discriminate sets of different numerosities provided that these sets have less than 7 objects (29). In our field study we find a range of 6-7 neighbours. Such a striking agreement suggests that the same tracking ability at the basis of numerical discrimination may be used for interacting with a fixed number of neighbours, and then be an essential ingredient of collective animal behaviour. The existence of a perceptual limit in numerosity is also found in 2D experiments on shoaling fish, and it is estimated around 3-5 individuals (30). An alternative interpretation of the interaction range we find is that the specific value of n c may be functional to optimize anti-predatory response: if each individual interacts with too few neighbours, information is non-noisy, but too short-ranged; conversely, if the interaction involves too many neighbours, information is averaged over several ill-informed individuals, and it is too noisy (31). A recent model for collective behaviour (15) locates the optimal range for anti-predatory response in 2D between 3 and 5 individuals, to be compared to our 3D value of 6-7. Why a topological, and not a metric interaction? Animal collective behaviour is staged in a troubled natural environment. Hence, the interaction mechanism shaped by evolution must keep cohesion in the face of strong perturbations, of which predation is the most relevant. We believe that topological interaction is the only mechanism granting such robust cohesion, and therefore higher biological fitness. A metric interaction is inadequate to cope with this problem: whenever the inter-individual distance became larger than the metric range, interaction would vanish, cohesion would be lost, and stragglers would 'evaporate' from the aggregation. A topological interaction, on the opposite, is very robust, since its strength is the same at different densities. By interacting within a fixed number of individuals, rather than meters, the aggregation can be either dense or sparse, change shape, fluctuate and even split, yet maintaining the same degree of cohesion. To support this hypothesis we analyze topological vs. metric interaction in the context of one of the simplest two-dimensional flocking models, the Self-Propelled Particles (SPP) model of (17) (see caption of Fig.4 for the equations defining the model). The standard SPP model is strictly metric: each individual interacts with all neighbours within a fixed metric range r c . The model, however, can easily be modified to become topological: each individual interacts with a fixed number of neighbours, n c . In absence of external perturbation, both interactions produce cohesive flocks in an appropriate range of parameters. However, it is not simply cohesion we are after, but robust cohesion. We therefore expose a cohesive flock to an external perturbation that mimics the attack of a predator (see Fig.4) . A possible outcome of the attack is to break the original flock into many components (Fig.4a) . Most of these M components consist of isolated individuals, or small groups, which are of course very vulnerable to predation. A robust interaction must preserve cohesion under attack, and thus keep the number of components M as low as possible. M=1 indicates that the original flock resisted the attack as a whole, and it corresponds to maximum cohesion. Cohesion of the aggregation is therefore higher the lower the number of components M after the attack. We perform the numerical experiment a large number of times, with different initial conditions, and compute the probability of having M flocks after the attack. Metric flocks very often break into more than one component, with a maximum probability at M=5 (Fig.4b,d ). This means that the average resilience of a metric flock is extremely poor: many isolated birds and small groups are forced out of the main flock by the predator's attack. Cohesion in topological flocks, on the other hand, is far superior (Fig.4c,e) . The highest probability is at M=1, namely the most probable outcome of the attack is that the original flock does not break up. Moreover the probability decays very rapidly to zero. Flocks ruled by a topological interaction are therefore much more stable under perturbations than metric ones. We repeated the same experiment using an inter-individual interaction that decays as the inverse of the distance, either metric (1/r) or topological (1/n). Results were exactly the same (Fig.S6  in SM) . This proves a very important point: the nature of the interaction (metric vs. topological) is much more relevant than the specific way it depends on the distance (flat vs. decaying). We expect the difference between topological and metric interaction to be even more striking in 3D, where achieving cohesion is more difficult due to the larger number of individual degrees of freedom. In conclusion, we presented large-scale 3D empirical data on a paradigmatic instance of collective animal behaviour, namely starlings' aerial display over the roost. Our results show that the inter-individual interaction depends on the topological distance, not the metric distance, at variance with most current models and theories. We suggest that models should be reconsidered in the light of this result. We also argued that a topological interaction is necessary to sustain strong density fluctuations and to maintain cohesion under perturbation, most conspicuously predation. Our numerical simulations support this idea in a compelling way. Given the strong adaptive advantage of cohesion for all animal aggregations, it seems likely that topological interaction is a fundamental ingredient also of other instances of collective animal behaviour. New empirical observations of different systems are necessary to confirm this idea. Location and materials. Images were taken in Rome, from the terrace of Palazzo Massimo, Museo Nazionale Romano, facing the roost trees situated in the square in front of Termini railway station. The apparatus was located 30m above ground level. Wind speed never exceeded 12ms -1 . Average distance of birds was 100m. We used Canon EOS 1D Mark II digital cameras (3504¥2336 pixels), mounting Canon 35-mm lenses. Focal length, optical centre, radial and tangential distortion were calibrated by Menci-Software s.r.l.. Aperture was between f2.0 and f4.0; shutter speed between 1/1000s and 1/250s; ISO between 100 and 800. We used Manfrotto-400 micrometric heads and Manfrotto-475 tripods. Cameras' tilt-up (between 35% and 40%) was measured by means of a Suunto clinometer. Experimental technique. We used stereo photography (32, 33) . The distance between stereo cameras (baseline) was d=25m. A third trifocal camera was placed at 2.5m from the right stereo camera (Fig. S5) . The error dz on the relative distance of two nearby targets located at distance z from the cameras is dominated by the error ds in the determination of the images positions. For parallel focal planes we have, where W=4335 is the focal length (measured in pixels) of our cameras, and nominally ds=1pixel. For birds at a distance z=100m we thus get a nominal error dz=0.09m. The error Dz on the absolute distance of a target at distance z is dominated by the error da on the convergence angle between the focal planes of the stereo cameras, † Each stereo camera was mounted on and aligned to a 680mm-long aluminium bar. A thin (∅0.25mm) line run along the bars and connected the stereo pair (Fig. S5) . The nominal alignment error was thus da=0.25/680=3.7¥10 -4 radiant, thus giving a nominal error Dz=0.14m (targets at 100m). Regular tests, performed with laser-metered targets gave: ds<0.4pixel fi error on relative distance dz<0.04m; da<2.3¥10 -3 radiants fi error on absolute distance Dz<0.92m (for z=100m). Stereo cameras were slightly convergent (0.22 radiants), to have maximal overlap of the fields of view (Fig. S5 ). Temporization. The shutter release cables were connected to a timer, which fired the cameras simultaneously at 5 frames-per-second (fps). Synch error was measured in lab and resulted smaller than 10ms. At rates faster than 5 fps the release time lag of the cameras became erratic. To increase shooting rate two interlaced cameras were mounted on each bar (Fig.S5) . Thus, our apparatus was shooting at 10fps. Buffers of the cameras filled up after 40 photographs. Therefore each flocking event lasts at most 8 seconds. Stereo Matching. After subtraction of the background, a segmentation algorithm locates birds' positions on the photographs (34). To perform the 3D reconstruction, each bird's image on the left photo must be matched to its corresponding image on the right photo (Fig.1) . For large and compact sets of featureless points this problem becomes extremely severe, and it has been the main bottleneck in the 3D reconstruction of animal aggregations. Our matching procedure involves 3 cameras, A, B and C (Fig. S5 ) and has four steps: first, a newly developed algorithm, exploiting pattern-recognition and epipolar invariance (33), matches approximately 20% of the birds on the stereo pair (A-C). Secondly, the same algorithm matches approximately 90% of the birds on the two nearby cameras (A-B). Third, these matches are used to calculate the nonlinear trifocal tensor (35). Fourth, by means of the trifocal tensor and of an optimization assignment algorithm (36), the (A-B) matches are transferred to the pair (A-C). In the cases we analyzed, we match on average 88% of the birds, and never less than 80%. Tests with synthetic data (distance and density as in the biological case) gave less than 5% of mismatches (outliers). A framework software developed by Nergal s.r.l. coordinated the various parts of the code. Our algorithms use some routines from the LTI-lib (http://ltilib.sourceforge.net) and CGAL (http://www.cgal.org) libraries. We collected approximately 500 flocking events. The vast majority of these events had to be discarded either because they were not included in the field of view of all 6 cameras, or because they were too far (our photographic resolution requires that flock are closer than 250m). Moreover, many events were recorded in too severe light conditions. These criteria are non-biased, and do not affect the biological features of the flocks, so that the ~50 events remaining are a fair sampling of roost's 9 flocks. We then narrowed our target of investigation by selecting 10 out of these 50 events. We chose flocks with sharp borders, strong spatial cohesion and a large number of birds (>400). We also had to discard flocks that were too dense, since our matching algorithm put a limit to the maximum density (the constraint on density will be relaxed as newer versions of our software are developed). Therefore, the final 10 analyzed events are representative of the typical cohesive flocks over the roost. We finally checked on synthetic data that the reconstruction software does not introduce any significant bias in the flock's shape and structure. All the reconstructions belonging to a single event are statistically homogeneous, and were thus used to build statistics for that particular flock. The problem of the border. Flocks are not necessarily convex. Therefore the so-called convex hull is not a suitable tool to define their border. In order to define the border we used the a-shape algorithm (37): basically one excavates the set of points with spheres of radius a. For a=• the border coincides with the convex hull, whereas for finite a concavities of size a are detected. Once the border's points are defined, one has to take care of the bias introduced by them. All methods to eliminate such bias basically require excluding the border points from the analysis, and for this reason having large aggregations is essential. We used the Hanish method (38). According to this method, when computing a certain average quantity at a given scale r, only the points having a distance from the border greater than r are considered. We checked all our tools by using them in test cases (as the Poisson and the hard-spheres distribution) where the analytic results were known. In these test cases one gets wrong results if the border's bias is not eliminated. Acknowledgements We thank E. Alleva for several crucial discussions and for the invaluable help he gave us on all ornithological issues, together with C. Carere and D. Santucci. We are indebted to C.
A field study of European starlings, Sturnus vulgaris, indicates that the swarm uses a topological, rather than a range limited model REF .
Interaction Ruling Animal Collective Behaviour Depends on Topological rather than Metric Distance: Evidence from a Field Study
PNAS, 105, 1232-1237 (2008)
Mathematics Biology Physics Medicine