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.