Citation: Kelum Gajamannage, Erik M. Bollt. Detecting phase transitions in collective behavior using manifold's curvature[J]. Mathematical Biosciences and Engineering, 2017, 14(2): 437-453. doi: 10.3934/mbe.2017027
[1] | Roman Czapla, Vladimir V. Mityushev . A criterion of collective behavior of bacteria. Mathematical Biosciences and Engineering, 2017, 14(1): 277-287. doi: 10.3934/mbe.2017018 |
[2] | Tatyana S. Turova . Structural phase transitions in neural networks. Mathematical Biosciences and Engineering, 2014, 11(1): 139-148. doi: 10.3934/mbe.2014.11.139 |
[3] | Nikolaos Kazantzis, Vasiliki Kazantzi . Characterization of the dynamic behavior of nonlinear biosystems in the presence of model uncertainty using singular invariance PDEs: Application to immobilized enzyme and cell bioreactors. Mathematical Biosciences and Engineering, 2010, 7(2): 401-419. doi: 10.3934/mbe.2010.7.401 |
[4] | Yong Yao . Dynamics of a delay turbidostat system with contois growth rate. Mathematical Biosciences and Engineering, 2019, 16(1): 56-77. doi: 10.3934/mbe.2019003 |
[5] | Honghua Bin, Daifeng Duan, Junjie Wei . Bifurcation analysis of a reaction-diffusion-advection predator-prey system with delay. Mathematical Biosciences and Engineering, 2023, 20(7): 12194-12210. doi: 10.3934/mbe.2023543 |
[6] | Changgui Gu, Ping Wang, Tongfeng Weng, Huijie Yang, Jos Rohling . Heterogeneity of neuronal properties determines the collective behavior of the neurons in the suprachiasmatic nucleus. Mathematical Biosciences and Engineering, 2019, 16(4): 1893-1913. doi: 10.3934/mbe.2019092 |
[7] | Paula Mercurio, Di Liu . Identifying transition states of chemical kinetic systems using network embedding techniques. Mathematical Biosciences and Engineering, 2021, 18(1): 868-887. doi: 10.3934/mbe.2021046 |
[8] | Alexej Tschumak, Frank Feldhoff, Frank Klefenz . The switching and learning behavior of an octopus cell implemented on FPGA. Mathematical Biosciences and Engineering, 2024, 21(4): 5762-5781. doi: 10.3934/mbe.2024254 |
[9] | Jordi Ripoll, Jordi Font . Numerical approach to an age-structured Lotka-Volterra model. Mathematical Biosciences and Engineering, 2023, 20(9): 15603-15622. doi: 10.3934/mbe.2023696 |
[10] | Virginia Giorno, Amelia G. Nobile . Exact solutions and asymptotic behaviors for the reflected Wiener, Ornstein-Uhlenbeck and Feller diffusion processes. Mathematical Biosciences and Engineering, 2023, 20(8): 13602-13637. doi: 10.3934/mbe.2023607 |
Multi-agent systems such as crowds of people [22,27,45], schools of fish [20,31], flocks of birds [8,28], colonies of molds [32] and ants [33] often exhibit discrete phase transitions due to variations of interaction among members [10]. Specially, detecting phase transitions in crowds of people [6] is a popular research problem [7]. Abrupt changes upon variation of some parameters such as speed, coordination, and structure [9,26,42] shift the phase of the system from one state to another [15,36]. Numerous types of swarm decisions which determine the group dynamics are not only influenced by the intrinsic social interaction among members [14], but also influenced by some outside factors such as threats [38] and presence of predators or food sources [40]. However, with a majority of data is recorded as videos, the classical approach of detecting phase transitions by means of tracking individuals and monitoring their dynamics is constrained by the size of the group and the scale of the problem [25]. Being inspired by manifold representation of collective behavior, here we develop a method of detecting phase transitions in a multi-agent system.
In manifold theory, we can reveal an invariant manifold
Φ:M→M ; Φ(p(t1))=p(t2), | (1) |
where
L=∩M(j). | (2) |
As an example, we estimate dimensionalities of two distinct phases, walking and running, of a crowd of people in [2]. Two phases of the motion are embedded into two distinct manifolds as shown in Figure 1(a). We utilize an established dimensionality reduction routine called Isomap [39] to obtain corresponding scaled residual variances of two embedding spaces (Fig. 1(b)) of each phase. Figure 1(b) shows that the two phases are embed on manifolds with different dimensionalities. This example acts as a proof-of-concept for developing an routine to detect phase transitions. Detecting phase transitions should be naively implemented on videos before utilize dimensionality reduction schemes such as Isomap [39], Local Linear Embedding [35], as those may otherwise contain phase transitions.
A phase transition in a multi-agent system is defined as switching of the current smooth embedding manifold into another smooth manifold with a different dimensionality as trajectories of agents evolve in the phase space. Our approach of detecting phase transitions is based on revealing high curvature on the manifold which differentiate phases of the motion. We hypothesize that a phase transition is manifested in the form of change in local curvature that can be detected by ratio of singular values computed on points sampled on the manifold. We first formulate this concept in two dimensions by proving a relation between curvature and singular value ratio in a curve, and then extend it to higher-dimensions by using the shape operator. Then, we justify that the same phase transition can also be detected by analyzing the ratios of the smallest singular value to the largest singular value which are computed locally upon neighborhoods of points sampled on the manifold. Based on the distribution of a moving sum of absolute difference of the singular value ratios, phase transitions are detected and their magnitudes are ordered.
This paper is organized as follows: Section 2 describes the method of detecting phase transitions. In Section 3, the method along with the detailed algorithm of detecting phase transitions in collective behavior is presented. Section 4 describes the performance of the method using one synthetic dynamical simulation of the Vicsek model and three natural experimental data sets, a crowd of human, a flock of birds, and a school of fish. We conclude the work in Section 5 with a discussion of the method including the performance and future work.
We declare that, in presence of a phase transition, the curvature of the underlying manifold is abruptly changed. Therein, we first approximate the point-wise curvature of a curve in two dimensions and then extend it to higher dimensions using the shape operator. Finally, we attest that the same phase transition can also be approximated locally by singular value ratios computed over the data sampled on the manifold.
Point-wise curvature of a curve is approximated by using singular value ratio computed over the data sampled in a neighborhood at the point. We assume that the data is evenly distributed along the curve. As in Figure 2(a), we can superimpose a neighborhood at any given point
Theorem 2.1. Given a circle centered at the origin with radius
Proof. We rotate the circular sector
μx1=12T∫T−Trcost dt=1TrsinT | (3) |
and
μx2=12T∫T−Trsint dt=0, | (4) |
respectively. We then compute pairwise covariance between variables as
cov(x1,x1)=12T∫T−T(rcost−μx1)2dt=r22T(T+12sin2T+2Tsin2T), | (5) |
cov(x1,x2)=12T∫T−T(rcost−μx1)(rsint−μx2)dt=0, | (6) |
cov(x2,x1)=12T∫T−T(rsint−μx2)(rcost−μx1)dt=0, | (7) |
and
cov(x2,x2)=12T∫T−T(rsint−μx2)2dt=r24T(2T−sin2T). | (8) |
The covariance matrix
Σ=(r22T(T+12sin2T+2Tsin2T)00r24T(2T−sin2T)). | (9) |
The covariance matrix which is approximated to
˜Σ=(r2T44500r2T23(1−T25))+O(T6). | (10) |
Let eigenvalues of
λ1≈r2T23(1−T25) and λ2≈r2T445. | (11) |
As eigenvalues are computed upon the covariance matrix, they also relate to principal components. We denote singular values associated with principal components by
λ2λ1≈T23(5−T2)⟹σ2σ1≈T√3(5−T2). | (12) |
Further,
σ2σ1≈T√15 | (13) |
since
T=α2ρκ where κ=1r. | (14) |
By (13) and (14),
σ2σ1≈Mκ where M=α2√15ρ∈R+. | (15) |
We extend the two dimensional assertion into higher dimensions by intersecting principal sections, made by the shape operator, with the manifold. Extrinsic curvatures of a manifold in orthogonal tangential directions are measured using eigenvalues and eigenvectors of the shape operator [29,34], such that eigenvalues provide magnitudes and eigenvectors provide directions of principal curvatures along tangential directions [5]. Bellow we explain the computation of the shape operator and principal sections.
Let
v(j)p=∂Mm∂xjandˆv(j)p=v(j)p‖v(j)p‖ | (16) |
provide mutually orthogonal tangential vectors and unit tangential vectors of
Sp=(−∇xj1Np⋅ˆv(j2)p)j1,j2forj1,j2=1,…,m | (17) |
Let (
Π(j)p={βu(j)p+γNp|β,γ∈R}. | (18) |
Thus, for
Without loss of generality, for
A generic example. As a simple geometric example to illustrate high curvature on a manifold at a phase transition, we use a three-dimensional joined-manifold that we call a 'sombrero-hat' (Fig. 4(a)) of 2000 points produced by the equations
x1=R cosθ,x2=R sinθ,and x3={4−R2,if R≤2,0,if R>2, | (19) |
for
As the construction of the shape operator at a neighborhood of each point on the manifold is computationally expensive, we present an alternative approach to compute the singular value ratios and detect phase transitions. Herein, we first make a neighborhood
1Singular value decomposition finds singular values
According to this setting, we assert that an abrupt change which is detected by the ratio
{(σα/σ1)n | n=1,…,N}, | (20) |
provides the magnitudes of the phase at each frame. Phase changes between consecutive frames are measured by moving differences of singular value ratios computed over neighborhoods of corresponding points as
tn=(σα/σ1)n+1−(σα/σ1)n for n=1,2,…,N−1. | (21) |
As the distribution
Σαn=∑i∈[n−⌈α2⌉,n+⌈α2⌉]∩Nti;n∈[⌈α2⌉,N−1−⌈α2⌉]∩N, | (22) |
where
2Ceiling function of
This algorithm requires two inputs, one is the parameter
dD(n,n′)=‖D(n,:)−D(n′,:)‖ ; n,n′=1,…,N. | (23) |
Based on this distance,
Algorithm 1 Detection of Phase Transition in Collective Behavior. |
Procedure PTD ( |
1:Perform nearest neighbor search in [16,44] to obtain |
2:Perform singular value decomposition [21], over |
3:Compute the ratio |
4:Compute absolute moving difference of ratios, |
5:Compute |
6:Largest values of |
end procedure |
In this section, we evaluate PTD algorithm on four datasets: a synthetic dynamical simulation of the Vicsek model and three natural data sets; a crowd of people, a flock of birds, and a school of fish.
A swarm of self propelled particles with three imposed phase transitions simulated by the Vicsek model [42] is examined to investigate the sensitivity of the algorithm. This model outputs two-dimensional positions and orientations of particles in each time-step.
We modify the notation for set of nearest neighbors used in Section 2.3 as
θ(i)n=arg(V(i)n−1)+ϵ(i)n−1,where V(i)n−1=1|N(i)n−1|∑j∈N(i)n−1[cos(θ(j)n−1)sin(θ(j)n−1)], | (24) |
and
a(i)n=a(i)n−1+s(i)n−1[cos(θ(i)n−1)sin(θ(i)n−1)]δ, | (25) |
where
We run a simulation of this model and generate a synthetic data set of a particle swarm of 50 particles in 200 time-steps with periodic boundary conditions. We set
σ={0.25,if n<50,1,if 51≤n<100,0.05,if 101≤n<150,0.75,if n≥150, | (26) |
for all
Cn(n1,n2)=10∑k1=110∑k2=1An(n1−k1,n2−k2)B(k1,k2) ; ∀ n1,n2 | (27) |
for
We run PTD algorithm upon
A video of a human crowd available on-line at [3] containing a phase transition at the
As in Example 4.1, we first convert all the frames into a data matrix
We now detect a phase transition, differentiating phases of sitting and flying, at the
We run PTD algorithm on the data matrix with
Finally, we use a video of a fish school having few phase transitions to validate the method. This school is stimulated with panics and the behavior is recorded.
We execute PTD algorithm on the data matrix with
In this study, we proposed a robust method to detect phase transitions in collective behavior using ratio of singular values encountering high curvature of the corresponding underlying manifold. We empirically observe that a phase transition in collective behavior is represented as a locus of singularities on the manifold where the curvature is significantly high. Thus, we first introduced an assertion to approximate the curvature of a curve by means of singular value ratios computed on it and then we extended the assertion to higher dimensions using the shape operator. Finally, we asserted that the same phase transition can also be detected through singular value ratios computed over the local data distribution on the manifold.
We validated the method through four diverse examples; one from a simulation of the Vicsek model [42] containing three phase transitions, and the other three from natural instances of a crowd of people, a flock of birds, and a school of fish. We ran PTD algorithm on each data set with a predetermined nearest neighbor parameter (
In Example 4.1, we simulated a training data set of a particle swam consisting known phase transitions to test the method's performance. Noteworthy shifts of the distribution
The algorithm running on a fish school consisting four phase transitions (Ex. 4.4) ranked their magnitudes such that it provides a good comparison between them. Embedding dimensionalities of sub-manifolds in each example revealed by isomap affirm that the data is embedded in distinct smooth sub-manifolds which are joined at singularities. Examples ensure the applicability of the method for variety of data sets ranging from simulations to natural, as it requires one input parameter
As we detect phase transitions based on the curvature which is a local property on the manifold, choosing the best value
In future, we will fabricate an automated method to determine the best
Here we presented a method to detect phase transitions in multi-agent systems using the curvature of the manifold representing the system. The method was validated on several instances ranging from simulation to natural to justify the broad applicability and the accuracy.
Kelum Gajamannage and Erik M. Bollt are supported by the National Science Foundation under the grant number CMMI-1129859. Erik M. Bollt is also supported by the Army Research Office under the grant number W911NF-12-1-276 and Office of Naval Research under the grant number N00014-15-2093.
Here, we provide an example of computing principal sections of a two dimensional manifold in
M2=(x1,x2,x31−3x1x22)∈R3, | (28) |
shown by Figure 9.
For an arbitrary point
v(1)p=∂M2∂x1=(1,0,3[x21−x22])⟹ˆv(1)p=v(1)p|v(1)p|=(1,0,3[x21−x22])√9(x21−x22)2+1, | (29) |
and
v(2)p=∂M2∂x2=(0,1,−6x1x2)⟹ˆv(2)p=v(2)p|v(2)p|=(0,1,−6x1x2)√36x21x22+1. | (30) |
Then, while the unit normal at
Np=v(1)p×v(2)p|v(1)p×v(2)p|=(−3[x21−x22],6x1x2,1)√9(x21+x22)2+1, | (31) |
tangential directions are
∇x1Np=∂Np∂x1=−6(x1[18x22{x21+x22}+1],x2[9{x41−x42}−1],3x1[x21+x22])[9(x21+x22)2+1]3/2, | (32) |
and
∇x2Np=∂Np∂x2=6(x2[18x21{x21+x22}+1],x1[9{x41−x42}+1],−3x2[x21+x22])[9(x21+x22)2+1]3/2. | (33) |
By Equations (29), (30), (32), and (33), we compute
S(1,1)p=−∇x1Np⋅ˆv(1)p=6x1√[9(x21+x22)2+1][9(x21−x22)2+1], | (34) |
S(1,2)p=−∇x1Np⋅ˆv(2)p=−6x2√[9(x21+x22)2+1][36x21x22+1], | (35) |
S(2,1)p=−∇x2Np⋅ˆv(1)p=−6x2√[9(x21+x22)2+1][9(x21−x22)2+1], | (36) |
S(2,2)p=−∇x2Np⋅ˆv(2)p=−6x1√[9(x21+x22)2+1][36x21x22+1]. | (37) |
Particularly, the shape operator
S(1,0,1)=(3/500−6/√10). | (38) |
Computed eigenpairs,
Π(1)(1,0,1)={β(1,0,1)+γ(−3,0,1)|,∀ γ,β∈R}andΠ(2)(1,0,1)={β(0,1,1)+γ(−3,0,1)|,∀ γ,β∈R}. | (39) |
[1] | [ Birds flying away, shutterstock. Available from: https://www.shutterstock.com/video/clip-3003274-stock-footage-birds-flying-away.html?src=search/Yg-XYej1Po2F0VO3yykclw:1:19/gg. |
[2] | [ Data set of detection of unusual crowd activity available at robotics and vision laboratory, Department of Computer Science and Engineering, University of Minnesota. Available from: http://mha.cs.umn.edu/proj_events.shtml. |
[3] | [ Data set of pet2009 at Computational Vision Group, University of Reading, 2009. Available from: http://ftp.pets.reading.ac.uk/pub/. |
[4] | [ N. Abaid,E. Bollt,M. Porfiri, Topological analysis of complexity in multiagent systems, Physical Review E, 85 (2012): 041907. |
[5] | [ G. Alfred, Modern Differential Geometry of Curves and Surfaces with Mathematica, CRC press, 1998. |
[6] | [ I. R. de Almeida and C. R. Jung, Change detection in human crowds, in Graphics, Patterns and Images (SIBGRAPI), 2013 26th SIBGRAPI-Conference on, IEEE, (2013), 63-69. |
[7] | [ E. L. Andrade, S. Blunsden and R. B. Fisher, Hidden markov models for optical flow analysis in crowds, in Pattern Recognition, 2006. ICPR 2006. 18th International Conference on, IEEE, 1(2006), 460-463. |
[8] | [ M. Ballerini,N. Cabibbo,R. Candelier,A. Cavagna,E. Cisbani,I. Giardina,A. Orlandi,G. Parisi,A. Procaccini,M. Viale, Empirical investigation of starling flocks: A benchmark study in collective animal behavior, Animal Behaviour, 76 (2008): 201-215. |
[9] | [ C. Becco,N. Vandewalle,J. Delcourt,P. Poncin, Experimental evidences of a structural and dynamical transition in fish school, Physica A: Statistical Mechanics and its Applications, 367 (2006): 487-493. |
[10] | [ M. Beekman,D. J. T. Sumpter,F. L. W. Ratnieks, Phase transition between disordered and ordered foraging in pharaoh's ants, Proceedings of the National Academy of Sciences, 98 (2001): 9703-9706. |
[11] | [ A. C. Bovik, Handbook of Image and Video Processing, Academic press, 2010. |
[12] | [ R. Bracewell, Fourier Analysis and Imaging, Springer Science & Business Media, 2010. |
[13] | [ I. D. Couzin, Collective cognition in animal groups, Trends in cognitive sciences, 13 (2009): 36-43. |
[14] | [ I. D. Couzin,J. Krause,N. R. Franks,S. A. Levin, Effective leadership and decision-making in animal groups on the move, Nature, 433 (2005): 513-516. |
[15] | [ A. Deutsch, Principles of biological pattern formation: Swarming and aggregation viewed as self organization phenomena, Journal of Biosciences, 24 (1999): 115-120. |
[16] | [ J. H. Friedman,J. L. Bentley,R. A. Finkel, An algorithm for finding best matches in logarithmic expected time, ACM Transactions on Mathematical Software, 3 (1977): 209-226. |
[17] | [ K. Gajamannage,S. Butailb,M. Porfirib,E. M. Bollt, Model reduction of collective motion by principal manifolds, Physica D: Nonlinear Phenomena, 291 (2015): 62-73. |
[18] | [ K. Gajamannage,S. Butailb,M. Porfirib,E. M. Bollt, Identifying manifolds underlying group motion in Vicsek agents, The European Physical Journal Special Topics, 224 (2015): 3245-3256. |
[19] | [ J. J. Gerbrands, On the relationships between SVD, KLT and PCA, Pattern recognition, 14 (1981): 375-381. |
[20] | [ R. Gerlai, High-throughput behavioral screens: The first step towards finding genes involved in vertebrate brain function using zebra fish, Molecules, 15 (2010): 2609-2622. |
[21] | [ G. H. Golub,C. Reinsch, Singular value decomposition and least squares solutions, Numerische Mathematik, 14 (1970): 403-420. |
[22] | [ D. Helbing,J. Keltsch,P. Molnar, Modelling the evolution of human trail systems, Nature, 388 (1997): 47-50. |
[23] | [ J. M. Lee, Riemannian Manifolds: An Introduction to Curvature, volume 176, Springer, 1997. |
[24] | [ J. M. Lee, Introduction to Smooth Manifolds, Graduate Texts in Mathematics, 218. Springer-Verlag, New York, 2003. |
[25] | [ R. Mehran, A. Oyama and M. Shah, Abnormal crowd behavior detection using social force model, in Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, IEEE, (2009), 935-942. |
[26] | [ M. M. Millonas, Swarms, Phase Transitions, and Collective Intelligence, Technical report, Los Alamos National Lab., New Mexico, USA, 1992. |
[27] | [ S. R. Musse and D. Thalmann, A model of human crowd behavior: Group inter-relationship and collision detection analysis, in Computer Animation and Simulation, Springer, (1997), 39-51. |
[28] | [ M. Nagy,Z. Ákos,D. Biro,T. Vicsek, Hierarchical group dynamics in pigeon flocks, Nature, 464 (2010): 890-893. |
[29] | [ B. O'neill, null, Elementary Differential Geometry, Academic press, New York, 1966. |
[30] | [ T. Papenbrock and T. H. Seligman, Invariant manifolds and collective motion in many-body systems, AIP Conf. Proc. , 597(2001), p301, arXiv: nlin/0206035. |
[31] | [ B. L. Partridge, The structure and function of fish schools, Scientific American, 246 (1982): 114-123. |
[32] | [ W. Rappel,A. Nicol,A. Sarkissian,H. Levine,W. F. Loomis, Self-organized vortex state in two-dimensional dictyostelium dynamics, Physical Review Letters, 83 (1999): p1247. |
[33] | [ E. M. Rauch,M. M. Millonas,D. R. Chialvo, Pattern formation and functionality in swarm models, Physics Letters A, 207 (1995): 185-193. |
[34] | [ V. Y. Rovenskii, Topics in Extrinsic Geometry of Codimension-one Foliations, Springer, 2011. |
[35] | [ S. T. Roweis,L. K. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science, 290 (2000): 2323-2326. |
[36] | [ R. V. Solé,S. C. Manrubia,B. Luque,J. Delgado,J. Bascompte, Phase transitions and complex systems: Simple, nonlinear models capture complex systems at the edge of chaos, Complexity, 1 (1996): 13-26. |
[37] | [ D. Somasundaram, Differential Geometry: A First Course, Alpha Science Int'l Ltd., 2005. |
[38] | [ D. Sumpter,J. Buhl,D. Biro,I. Couzin, Information transfer in moving animal groups, Theory in Biosciences, 127 (2008): 177-186. |
[39] | [ J. B. Tenenbaum,V. De Silva,J. C. Langford, A global geometric framework for nonlinear dimensionality reduction, Science, 290 (2000): 2319-2323. |
[40] | [ E. Toffin,D. D. Paolo,A. Campo,C. Detrain,J. Deneubourg, Shape transition during nest digging in ants, Proceedings of the National Academy of Sciences, 106 (2009): 18616-18620. |
[41] | [ C. M. Topaz,A. L. Bertozzi, Swarming patterns in a two-dimensional kinematic model for biological groups, SIAM Journal on Applied Mathematics, 65 (2004): 152-174. |
[42] | [ T. Vicsek,A. Cziró,E. Ben-Jacob,I. Cohen,O. Shochet, Novel type of phase transition in a system of self-driven particles, Physical Review Letters, 75 (1995): 1226-1229. |
[43] | [ E. Witten, Phase transitions in m-theory and f-theory, Nuclear Physics B, 471 (1996): 195-216. |
[44] | [ P. N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, (1993), 311-321. |
[45] | [ T. Zhao and R. Nevatia, Tracking multiple humans in crowded environment, in Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, IEEE, (2004), Ⅱ-406. |
1. | K. Gajamannage, D. I. Jayathilake, Y. Park, E. M. Bollt, Recurrent neural networks for dynamical systems: Applications to ordinary differential equations, collective motion, and hydrological modeling, 2023, 33, 1054-1500, 013109, 10.1063/5.0088748 | |
2. | Mary Isangediok, Kelum Gajamannage, 2022, Fraud Detection Using Optimized Machine Learning Tools Under Imbalance Classes, 978-1-6654-8045-1, 4275, 10.1109/BigData55660.2022.10020723 |