Topological analysis of complexity in multiagent systems

Social organisms at every level of evolutionary complexity live in groups, such as fish schools, locust swarms, and bird flocks. The complex exchange of multifaceted information across group members may result in a spectrum of salient spatiotemporal patterns characterizing collective behaviors. While instances of collective behavior in animal groups are readily identifiable by trained and untrained observers, a working definition to distinguish these patterns from raw data is not yet established. In this work, we define collective behavior as a manifestation of low-dimensional manifolds in the group motion and we quantify the complexity of such behaviors through the dimensionality of these structures. We demonstrate this definition using the ISOMAP algorithm, a data-driven machine learning algorithm for dimensionality reduction originally formulated in the context of image processing. We apply the ISOMAP algorithm to data from an interacting self-propelled particle model with additive noise, whose parameters are selected to exhibit different behavioral modalities, and from a video of a live fish school. Based on simulations of such model, we find that increasing noise in the system of particles corresponds to increasing the dimensionality of the structures underlying their motion. These low-dimensional structures are absent in simulations where particles do not interact. Applying the ISOMAP algorithm to fish school data, we identify similar low-dimensional structures, which may act as quantitative evidence for order inherent in collective behavior of animal groups. These results offer an unambiguous method for measuring order in data from large-scale biological systems and confirm the emergence of collective behavior in an applicable mathematical model, thus demonstrating that such models are capable of capturing phenomena observed in animal groups.

Figure 1

Sample model trajectories with AP and SO parameters and $\eta =0.005$, $0.05$, and $0.5$. We define $N=40$ agents traveling in the complex plane with $s=0.25$, $L=5$, $r=1$, and $r_a=3$ and we display the first 75 time steps out of a $10000$ time step simulation of the model. For AP simulation data, $p=0.01$. For SO simulation data, the source position is $-2.15+2.23\iota$ when $\eta =0.005$, $1.96+2.30\iota$ when $\eta =0.05$, and $-1.56+1.92\iota$ when $\eta =0.5$. Horizontal and vertical axes refer to the real and imaginary parts of $x\left(k\right)$, respectively, for different values of $k$.

Figure 2

Sample simulation trajectories with RW parameters and $\eta =0.005$, $0.05$, and $0.5$. We use $r=0$ and the same time steps and other protocol parameter values for $N$, $s$, $L$ as in Fig. 1. Horizontal and vertical axes refer to the real and imaginary parts of $x\left(k\right)$, respectively, for different values of $k$.

Figure 3

Polarization of simulation trajectories with AP (top) and SO (bottom) parameters and $\eta =0.005$, $0.05$, and $0.5$. We display the first 100 time steps of the $10000$ time step simulations in Fig. 1.

Figure 4

Cohesion of simulation trajectories with AP (top) and SO (bottom) parameters and $\eta =0.005$, $0.05$, and $0.5$. We display the first 100 time steps of the $10000$ time step simulations in Fig. 1.

Figure 5

Polarization (top) and cohesion (bottom) of simulation trajectories with RW parameters and $\eta =0.005$, $0.05$, and $0.5$. We display the first 100 time steps of the $10000$ time step simulations in Fig. 2.

Figure 6

Illustration of the main steps for implementation of the ISOMAP algorithm.

Figure 7

Downsampled two-dimensional embedding manifolds for model with AP and SO parameters and $\eta =0.005$, $0.05$, and $0.5$. Simulations are those which are shown truncated in Fig. 1, here sampled at every other time step, and thus use the same model parameters.

Figure 8

Downsampled two-dimensional embedding manifolds for model with RWparameters and $\eta =0.005$, $0.05$, and $0.5$. Simulations are those which are shown truncated in Fig. 2, here sampled at every other time step, and thus use the same model parameters.

Figure 9

Scaled residual variances for model with AP, SO, and RW parameters and $\eta =0.005$, $0.05$, and $0.5$. Residual variances are scaled with respect to those corresponding to dimension one.

Figure 10

Images of fish schooling experiment. Sample frames of a 52 s movie of a fish school making a circuit of the aquarium.

Figure 11

Data from fish schooling experiment. Scaled residual variances (left) and two-dimensional embedding manifold (right) for movie frame data. The residual variances are scaled with respect to that corresponding to dimension one, which equals $0.5894.$ The movie was filmed at 30 frames/s for 1580 frames and frame size is $480\times 640$ pixels.