Topological analysis of group fragmentation in multiagent systems

In social animals, the presence of conflicts of interest or multiple leaders can promote the emergence of two or more subgroups. Such subgroups are easily recognizable by human observers, yet a quantitative and objective measure of group fragmentation is currently lacking. In this paper, we explore the feasibility of detecting group fragmentation by embedding the raw data from the individuals' motions on a low-dimensional manifold and analyzing the topological features of this manifold. To perform the embedding, we employ the isomap algorithm, which is a data-driven machine learning tool extensively used in computer vision. We implement this procedure on a data set generated by a modified à la Vicsek model, where agents are partitioned into two or more subsets and an independent leader is assigned to each subset. The dimensionality of the embedding manifold is shown to be a measure of the number of emerging subgroups in the selected observation window and a cluster analysis is proposed to aid the interpretation of these findings. To explore the feasibility of using this approach to characterize group fragmentation in real time and thus reduce the computational cost in data processing and storage, we propose an interpolation method based on an inverse mapping from the embedding space to the original space. The effectiveness of the interpolation technique is illustrated on a test-bed example with potential impact on the regulation of collective behavior of animal groups using robotic stimuli.

Figure 1

Two-dimensional embedding manifolds generated by the isomap algorithm (a–c) and scaled residual variance (d–f) for one (a, d), two (b, e), and three (c, f) leaders and $\eta =0.005$. Residual variances for dimension 1 are $2.20\times {10}^{-5}$, 0.24, and 0.34 for one, two, and three subsets, respectively.

Figure 2

Time trace of the polarization for one (a), two (b), and (c) three leaders and $\eta =0.005$.

Figure 3

Results for simulations involving two agents' subsets with $\eta =0.025$: two-dimensional embedding manifolds generated by the isomap algorithm (a), scaled residual variance (b), and time trace of the polarization (c). Residual variance for dimension 1 is 0.26.

Figure 4

Comparison of the distribution of the number of clusters for simulations in the presence of two agents' subsets: (a) $\eta =0.005$ and (b) $\eta =0.025$.

Figure 5

Assessment of the control algorithm performance: (a) headings of leader 1 [solid (blue) line] and leader 2 [dashed (red) line], in radians; (b) time trace of the polarization of the whole system; (c) time trace of the polarization for subset 1 [solid (blue) line] and subset 2 [dashed (red) line].

Figure 6

Scaled residual variance for the isomap algorithm for the time windows $\left[12000\right]$ (a), $\left[1800120000\right]$ (b), and $\left[3800140000\right]$ (c) of the control example implemented on all the available 2000 samples. Residual variances for dimension 1 are 0.38, 0.23, and 0.01 for time windows $\left[12000\right]$, $\left[1800120000\right]$, and $\left[3800140000\right]$, respectively.

Figure 7

Distribution of the number of clusters for the control example computed over the time windows $\left[12000\right]$ (a) and $\left[1800120000\right]$ (b).

Figure 8

Scaled residual variance for the isomap algorithm executed on varying time windows of the control example and based on 500 samples obtained through uniform downsampling. Results in (a–c) are implemented on a data set of only 500 samples, while findings in (d–f) use 2000 synthetic samples obtained from the 500 uniformly downsampled data points. The time windows are $\left[12000\right]$ (a), $\left[1800120000\right]$ (b), and $\left[3800140000\right]$ (c), with residual variances for dimension 1 equal to 0.92, 0.61, and 0.99, respectively, and $\left[12000\right]$ (d), $\left[1800120000\right]$ (e), and $\left[3800140000\right]$ (f), with residual variances for dimension 1 equal to 0.45, 0.34, and 0.01, respectively.