New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study

Contributed by G. Parisi, December 4, 2007 (received for review September 25, 2007)
Abstract
Numerical models indicate that collective animal behavior 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 threedimensional positions of individual birds in airborne flocks of a few thousand members, we show 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 discovered that each bird interacts on average with a fixed number of neighbors (six to seven), rather than with all neighbors within a fixed metric distance. We argue that a topological interaction is indispensable to maintain a 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 with a standard metric one.
Collective behavior of large aggregations of animals is a truly fascinating natural phenomenon (1). Particularly interesting is the case when aggregations selforganize into complex patterns with no need of an external stimulus (2). Prominent examples of such behavior are bird flocks (3), fish schools (4) and mammal herds (5). Apart from its obvious relevance in ethology and evolutionary biology, collective behavior is a key concept in many other fields of science, including control theory (6), economics (7), and social sciences (8).
How does collective behavior emerge? Numerical models of selforganized motion, inspired both by biology (9–15) and physics (16–20), support the idea that simple rules of interaction among the individuals are sufficient to produce collective behavior. 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 behavior.
The main goal of the interaction among individuals is to maintain cohesion of the group. This cohesion is a very strong biological requirement, shaped by the evolutionary pressure for survival: Stragglers and small groups are significantly more prone to predation than animals belonging to large and highly cohesive aggregations (4). 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?”
To grant cohesion, models make the sound assumption that individuals align and attract each other, and that such interaction decays with increasing distance between individuals. The vast majority of models adopt a definition of “distance” that is the same as in physics, i.e., metric distance. In a metric context, two birds 5 m apart attract each other less than two birds 1 m 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, an interaction based on metric distance may be unable to reproduce the density changes typical of animal aggregations, because one would expect cohesion to be lost when mutual distances become too large compared with the interaction range. An alternative is topological distance: The relevant quantity is how many intermediate individuals separate two birds, not how far apart they are. In this case, each individual interacts with a fixed number of neighbors, irrespective of their metric distance. The crucial difference between metric and topological interaction really comes in when the density varies: In the topological case, two birds 5 m apart in a sparse flock attract each other as much as two birds 1 m apart in a denser flock, provided that the number of individuals between the two birds is the same. Thus, in the topological hypothesis, the strength of the interaction remains the same at different densities. This interaction seems more suitable to keep cohesion in the face of strong density fluctuations. By means of empirical observations, we will show that the topological paradigm is, in fact, more suitable.
Results
Structure is the foremost effect of interaction, and, conversely, interaction is ciphered in the interindividual spatial structure. Hence, to learn something about the interaction ruling collective behavior, it is necessary to analyze the structural organization of individuals within the group. To do this, however, it is essential to have data on the 3D positions of individuals in large groups. Collective behavior is a qualitatively different phenomenon, with emerging complex patterns, only when the number of individuals is big. Moreover, in small aggregations, the surfacetovolume 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 (a few tens) and loose group arrangements (22–25), at variance with the huge, highly cohesive natural aggregations.
Using stereometric and computer vision techniques, we measured 3D individual birds positions in compact flocks of up to 2,600 European Starlings (Sturnus vulgaris) in the field. This number is an advance of almost two orders of magnitude compared with former experiments. A typical flock and its 3D reconstruction are shown in Fig. 1[see also supporting information (SI) Fig. 5]. Although not all birds form groups, starlings habitually organize in flocks, and their aerial display provides a paradigmatic case of collective behavior. These birds gather in the evening over the roost and form sharp bordered, strongly cohesive flocks, ranging from a few hundreds to tens of thousands of birds (see SI Figs. 6 and 7). We reconstructed and analyzed 10 independent flocking events recorded at the roosting site of Termini railway station (Rome, Italy) between December 2005 and February 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. Observations were made at dusk.
The clearest characterization of the structure of birds within a flock is given by the spatial distribution of the nearest neighbors. Given a reference bird, we measure the angular orientation of its nearest neighbor with respect to the flock's direction of motion, i.e., the neighbor'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 angular position of nearest neighbors (see Fig. 2's legend). This map (Fig. 2a) shows a striking lack of nearest neighbors 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 (starlings have lateral visual axis), are discussed in the SI Text. The crucial point, however, is that this anisotropy is the effect of the interaction among individuals, whatever this interaction is. To support this claim, we compute the distribution of neighbors very far apart from the reference bird (Fig. 2b). This distribution is uniform, as for a completely isotropic, noninteracting aggregation of points. This observation 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 the SI Text on this point). In fact, if we compute the angular map for the second nearest neighbor, third nearest neighbor, and so on, we observe that the anisotropic structure progressively fades away as the order of the neighbor increases.
To quantify the decay of the anisotropy, we define a function γ(n) that measures to what extent the spatial distribution of the nth nearest neighbor around a reference bird is anisotropic (see Fig. 3's legend). The value of γ for an isotropic, noninteracting aggregation is 1/3 (see the SI Text). A value larger than 1/3 indicates that the interaction among the birds makes the structure anisotropic. In Fig. 3a, we show that γ(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 γ becomes 1/3. By definition, birds farther than the n_{c}th nearest neighbor are isotropically distributed around the reference bird and do not interact with it. Fig. 3a is an empirical determination of how the interaction decays in a real instance of collective behavior in the field. Previous work (26) was limited to 2D projections of very small groups (≈10) in the laboratory.
The nth nearest neighbor 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 3206 (Fig. 3b) the sixth nearest neighbor of a bird is found, on average, at 1.25 m from it. Clearly, the relation between n and r depends on the specific density of the flock. Whereas 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 3206, we have n_{c} = 6, and r_{c} = 1.25 m (Fig. 3a).
The flocks we analyzed differ greatly from one another in density (the density not depending on the number of birds or on the velocity of the flock). This difference implies that the topological and metric ranges, n_{c} and r_{c}, cannot both be 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 two flocks, although the number of individuals n_{c} within this range is large in the denser flock, and small in the sparser flock. Conversely, if the interaction depends on the topological distance, the range in units of birds n_{c} is constant in the two flocks, although the distance r_{c} of the n_{c}th nearest neighbor is small in the denser flock, and large in the sparser flock. The difference between topological and metric hypotheses is stark: In the topological scenario, the number of interacting individuals is fixed, whereas in the metric scenario, the 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. 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 nth nearest neighbor grows with n according to the relation r ∼ r_{1} n^{1/3} (see Fig. 3b). In this equation, r_{1} is the average nearestneighbors distance, which is a direct measure of sparseness (the inverse of density); r_{1} varies from 0.68 m in the densest flock to 1.51 m in the sparsest flock (see SI Table 1). The equation above simply means that the number n of individuals within a sphere of radius r is proportional to r^{3}. The two ranges are linked by the same relation, r_{c} ∼ r_{1} n_{c}^{1/3}. In a metric scenario, r_{c} is a constant, and thus n_{c}^{−1/3}∼ r_{1}. Conversely, in the topological scenario n_{c} is a constant, and thus r_{c} ∼ r_{1}. We have measured n_{c} and r_{c} in each flock and have studied how these two quantities depend on the flocks' sparseness r_{1}. The experimental evidence clearly supports the topological scenario: There is no significant correlation between n_{c}^{−1/3} and r_{1}, whereas a clear linear correlation exists between r_{c} and r_{1} (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 structure, and thus indirectly the interaction causing it, depends on the topological distance rather than the metric distance. The interaction between two birds 1 m apart in flock A is as strong as that between two birds 5 m apart in flock B, provided that flock A is denser than flock 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 cutoff, or numerical preference, in the number of interacting neighbors (so that this number is fixed), they still “weight” these neighbors metrically (18, 27). 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 cutoff, 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 neighbors (28), because such aerodynamic advantage would decay within a well defined metric length scale (see SI Text). In fact, we believe that the only mechanism compatible with our result is vision.
Discussion
Why six to seven neighbors? This range is significantly smaller than the number of visually unobstructed neighbors 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. To keep a fixed number of neighbors under control, it is necessary for the individuals to have some prenumeric ability, or, more precisely, an objecttracking, or “subitizing,” ability (29). 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 seven objects (30). In our field study, we find a range of six to seven neighbors. 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 neighbors and therefore would be an essential ingredient of collective animal behavior. The existence of a perceptual limit in numerosity is also found in 2D experiments on shoaling fish, and it is estimated at approximately three to five individuals (31). An alternative interpretation of the interaction range we find is that the specific value of n_{c} may be functional to optimize antipredatory response: If each individual interacts with too few neighbors, information is nonnoisy, but it is too shortranged; conversely, if the interaction involves too many neighbors, information is averaged over several illinformed individuals, and it is too noisy (32). A recent model for collective behavior (14) locates the optimal range for antipredatory response in 2D between three and five individuals, to be compared with our 3D value of six to seven.
Why a topological, and not a metric, interaction? Animal collective behavior 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 interindividual distance became larger than the metric range, interaction would vanish, cohesion would be lost, and stragglers would “evaporate” from the aggregation. A topological interaction, in contrast, is very robust, because its strength is the same at different densities. By interacting within a fixed number of individuals the aggregation can be either dense or sparse, change shape, fluctuate and even split, yet maintain the same degree of cohesion.
To support this hypothesis, we analyze topological vs. metric interaction in the context of one of the simplest 2D flocking models, the selfpropelled particles (SPP) model of ref. 16 (see caption of Fig. 4 for the equations defining the model). The original SPP model is strictly metric: Each individual interacts with all neighbors 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 neighbors, 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. 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. Therefore, the higher the cohesion of the aggregations, the lower the number of components M after the attack. We performed the numerical experiment a large number of times, with different initial conditions, and computed 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. 4 b and d). This finding 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. 4 c and 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 by using an interindividual interaction that decays as the inverse of the distance, either metric (1/r) or topological (1/n). Results were exactly the same (SI Fig. 8). This finding 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 because of the larger number of individual degrees of freedom. Simulations in 3D would also allow us to investigate the possible link between the empirical interaction range n_{c} = 6–7 and the antipredatory optimum.
We note that for starlings the visual sensing range is well beyond the average distance of the seventh neighbor even in the sparsest flock we analyzed. Thus, we can exclude that the metric sensing range is cutting off the topological interaction range. However, in extremely sparse flocks (not analyzed in our study), as well as in species (such as fishes) living in less transparent medium, the metric sensing range may fall within the topological range. These cases may in fact be modeled by a topological interaction complemented with a metric cutoff, which describes the sensing limit (see, for example, refs. 14 and 18).
In conclusion, we presented largescale 3D empirical data on a paradigmatic instance of collective animal behavior, namely starlings' aerial display over the roost. Our results show that the interindividual 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 also a fundamental ingredient of other instances of collective animal behavior. Further empirical observations of different systems are necessary to confirm this idea.
Materials and Methods
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 30 m above ground level. Wind speed never exceeded 12 ms^{−1}. The birds' average distance was 100 m. We used Canon EOS 1D Mark II digital cameras (3,504 × 2,336 pixels), mounting Canon 35mm calibrated lenses. Aperture was in the interval: f2.0–4.0; shutter speed: 1/1,000–1/250 s; ISO: 100–800; cameras' tiltup: 35–40%.
Experimental Technique.
We used stereo photography (33, 34). The distance between stereo cameras (baseline) was d = 25 m. A third trifocal camera was placed 2.5 m from the right stereo camera (SI Fig. 9). The error δz on the relative distance of two nearby targets located at distance z from the cameras is dominated by the error δs in the determination of the images' positions. For parallel focal planes we have, δz = δs z^{2}/Ωd, where Ω = 4,335 is the focal length in pixels of our cameras, and nominally δs = 1 pixel. For birds at z = 100 m, we thus get a nominal error δz = 0.09 m. The error Δz on the absolute distance of a target at distance z is dominated by the error δα on the convergence angle between the focal planes of the stereo cameras, Δz = δα z^{2}/d. Each stereo camera was mounted on a 680mmlong bar. A thin (0.25mm diameter) line run along the bars and connected the stereo pair (SI Fig. 9). The nominal alignment error was thus δα = 0.25/680 = 3.7 × 10^{−4} rad, thus giving a nominal error Δz = 0.14 m (targets at 100 m). Regular tests, performed with lasermetered targets, gave: δs < 0.4 pixel ⇒ error on relative distance δz < 0.04 m; δα < 2.3 × 10^{−3} radiants ⇒ error on absolute distance Δz < 0.92 m (for z = 100 m). Stereo cameras had a 0.22rad convergence (SI Fig. 9).
Temporization.
The shutter release cables were connected to a timer that fired the cameras simultaneously at 5 framespersecond (fps). Synch error was smaller than 10ms. To increase shooting rate two interlaced cameras were mounted on each bar (SI Fig. 9). Thus, our apparatus was shooting at 10 fps. 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 (35). 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 three cameras, A–C (SI Fig. 9), and has four steps. First, a newly developed algorithm, exploiting pattern recognition and epipolar invariance (34), matches ≈20% of the birds on the stereo pair (A–C). Second, the same algorithm matches ≈90% of the birds on the two nearby cameras (A and B). Third, these matches are used to calculate the nonlinear trifocal tensor (36). Fourth, by means of the trifocal tensor and an optimization assignment algorithm (37), the (A and B) matches are transferred to the pair (A–C). In the cases we analyzed, we match, on average, 88% of the birds and never <80%. Tests with synthetic (computer generated) images gave <5% of mismatches.
Events Selection.
We collected ≈500 independent flocking events, the vast majority of which was discarded because they were (i) not included in the field of view of all six cameras; (ii) too far for our photographic resolution (<250 m); or (iii) recorded in too severe light conditions. These criteria do not affect biological features, and the 50 events remaining were a fair sampling of the roost's flocks. We then selected 10 of these 50 events. We chose flocks with sharp borders, strong spatial cohesion, and a large number of birds (>400). We discarded too dense flocks, because our algorithms put a limit to the maximum density. We checked on synthetic data that the reconstruction software does not introduce any bias in the flock's shape and structure. All of the reconstructions belonging to a single event are statistically homogeneous and were thus used to build statistics for that particular flock.
Border.
It is essential to take care of the bias introduced by the aggregation's border. Flocks are not necessarily convex, and thus the standard convex hull is not suitable to define their border. To do this, we used the αshape algorithm (38): A set of 3D points is excavated with spheres of radius α, so that all concavities of size larger than α are detected. The border points must then be excluded from the analysis, and, for this reason, having large aggregations is essential. We used the Hanisch method (39): When computing a certain average quantity at a given scale r, only the points having a distance from the border >r are considered. We checked all our tools by using them in testpoint distributions, where the analytic results were known.
Acknowledgments
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; C. Agrillo, E. Branchini, F. Cecconi, M. Cencini, I. D. Couzin, M. Fiani, A. Gabrielli, R. James, T. Joerg, J. Krause, N. Leonard, B. Marcos, E. Marinari, M. Montuori, R. Sarno, F. SylosLabini, and all members of the STARFLAG project for discussions; S. Cabasino, F. Ceccaroni, A. Cimarelli L. Menci, C. Piscitelli, R. Santagati, and F. Stefanini for technical help; R. Paris and M. Petrecca for granting the indispensable access to Palazzo Massimo, Museo Nazionale Romano; P. Corezzola, G. Loffredo, M. Marchetti, and B. Pernati for administrative assistance; and G. A. Cavagna for carefully reading the manuscript and for the advice. V.L. thanks the Department of Physics, University of Rome La Sapienza, where part of this study was performed, for their kind hospitality. This work was financed by a grant from the European Commission to the STARFLAG project, within the NESTPATHFINDER initiative under Framework Program 6.
Footnotes
 **To whom correspondence may be addressed. Email: andrea.cavagna{at}roma1.infn.it or giorgio.parisi{at}roma1.infn.it

Author contributions: N.C., A.C., I.G., and G.P. designed research; M.B., R.C., A.C., I.G., V.L., A.O., A.P., and V.Z. performed research; M.B., N.C., A.C., E.C., I.G., A.O., G.P., and M.V. contributed new reagents/analytic tools; A.C., I.G., A.O., G.P., and A.P. analyzed data; and A.C. wrote the paper.

↵^{¶}Present address: GIT/SPEC/DRECAM, Bat. 772, Orme des Merisiers, CEA Saclay, 91191 Gif sur Yvette, France.

↵^{‡‡}Present address: DPMC, Université de Genève, 24 Quai Ernest Ansermet, 1211 Genève, Switzerland.

↵^{§§}Present address: Dipartimento di Fisica, Universita' di Roma 3, via della Vasca Navale 84, 00146 Roma, Italy.

The authors declare no conflict of interest.

This article contains supporting information online at www.pnas.org/cgi/content/full/0711437105/DC1.

Freely available online through the PNAS open access option.
 © 2008 by The National Academy of Sciences of the USA
References
 ↵
 Parrish JK,
 EdelsteinKeshet L
 ↵
 Krause J,
 Ruxton GD
 ↵
 Emlen JT
 ↵
 Pitcher TJ
 Pitcher TJ,
 Parrish JK
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 Krasner S
 Heppner FH,
 Grenander U
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 Buhl J,
 et al.
 ↵
 ↵
 ↵
 ↵
 ↵
 Pomeroy H,
 Heppner F
 ↵
 Aoki I
 ↵
 Parrish JK,
 Viscido SV,
 Grünbaum D
 ↵
 Lissaman PBS,
 Shollenberger CA
 ↵
 ↵
 HP,
 Zeigler,
 Bischof HJ.
 Emmerton JD,
 Delius J
 ↵
 Tegeder RW,
 Krause J
 ↵
 ↵
 ↵
 ↵
 Forsyth D,
 Ponce J
 ↵
 ↵
 Gabow HN
 ↵
 Edelsbrunner H,
 Mucke EP
 ↵
 Stoyan D,
 Stoyan H