Advanced Search
Article Contents
Article Contents

Detecting phase transitions in collective behavior using manifold's curvature

  • *Corresponding author

    *Corresponding author 
The authors were supported by the NSF grant CMMI-1129859. Erik M. Bollt was supported by the Army Research Office grant W911NF-12-1-276 and Office of Naval Research grant N00014-15-2093.
Abstract Full Text(HTML) Figure(9) Related Papers Cited by
  • If a given behavior of a multi-agent system restricts the phase variable to an invariant manifold, then we define a phase transition as a change of physical characteristics such as speed, coordination, and structure. We define such a phase transition as splitting an underlying manifold into two sub-manifolds with distinct dimensionalities around the singularity where the phase transition physically exists. Here, we propose a method of detecting phase transitions and splitting the manifold into phase transitions free sub-manifolds. Therein, we firstly utilize a relationship between curvature and singular value ratio of points sampled in a curve, and then extend the assertion into higher-dimensions using the shape operator. Secondly, we attest that the same phase transition can also be approximated by singular value ratios computed locally over the data in a neighborhood on the manifold. We validate the Phase Transition Detection (PTD) method using one particle simulation and three real world examples.

    Mathematics Subject Classification: Primary: 53C15, 53C21; Secondary: 58D15.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  An abrupt phase change of the crowd behavior where a walking crowd suddenly starts running [2]. (a) The first phase of the motion (walking) is embedded onto the blue colored manifold, while the second phase (running) is embedded onto the red colored manifold. Two snapshots showing walking and running at time steps $t_1$ and $t_2$ are embedded onto points $\boldsymbol{p}^{(t_1)}$ and $\boldsymbol{p}^{(t_2)}$, respectively, in the corresponding manifolds. The locus of singularities ($\mathcal{L}$) is represented by orange color. (b) The scaled residual variance versus the dimensionality, that gives the dimensionality of the underlying manifold by an elbow, is obtained by running Isomap upon frames in each phase with 6 nearest neighbors. Embedding dimensionalities of sub-manifolds representing walking (blue circle) and running (red square) of the crowd are three and four, respectively

    Figure 2.  (a) Superimposing a neighborhood of the curve $C$ at point $\boldsymbol{p}$ with an arc $\boldsymbol{p}_1\boldsymbol{p}\boldsymbol{p}_2$ which subtend an small angle of $2T$ at the origin of a translating circle. (b) Zoomed and rotated secular sector $\boldsymbol{p}_1\boldsymbol{p}_2\boldsymbol{O}$ such that the blue arrow is horizontal

    Figure 3.  Local distribution of data around the point $\boldsymbol{p}$ on a two dimensional manifold ($\mathcal{M}^2$). Principal sections $\Pi^{(1)}_{\boldsymbol{p}}$ and $\Pi^{(2)}_{\boldsymbol{p}}$ are created by using the shape operator at $\boldsymbol{p}$, and curves $C^{(1)}$ and $C^{(2)}$ are produced by intersecting $\Pi^{(1)}_{\boldsymbol{p}}$ and $\Pi^{(2)}_{\boldsymbol{p}}$ with $\mathcal{M}^2$, respectively

    Figure 4.  (a) A three dimensional sombrero-hat of 2000 points consisting two sub-manifolds (blue and green) and locus of singularities (red) is intersected with the plane $\{\beta_1\hat{\boldsymbol{i}}+\beta_2\hat{\boldsymbol{k}} \vert \beta_1, \beta_2 \in \mathbb{R}\}$ to produce (b) a curve in $\mathbb{R}^3$. (c) Isomap residual plots those show embedding dimensionalities by elbows reveal that the dimensionalities of two sub-manifolds are two while the dimensionality of the locus is three

    Figure 5.  Detecting phase transitions in a particle swarm simulated using the Vicsek model with alternating noise levels. (a) The distribution of $(\sigma_4/\sigma_1)_{n}$ versus frame numbers. Therein, the range of frames for each sub-manifold is represented by a left-right arrow and the frame number at each phase transition is represented by a red circle along with the frame number associated. (b) The plot of 20 largest phase changes including frame numbers of three phase transitions. (c) Isomap residual variance versus dimensionality of each sub-manifold

    Figure 6.  Detecting a phase transition between phases of walking and running in a human crowd [3]. (a) The distribution of $(\sigma_3/\sigma_1)_{n}$ versus frame numbers. Therein, while the snapshots show instances of the crowd in each phase, left-right arrows and the red circle represent ranges of frames in each sub-manifold and the frame at the phase transition, respectively. (b) The plot of 20 largest phase changes representing the phase transition in red along with its frame number

    Figure 7.  Detecting a transition in a bird flock between phases sitting and flying [1]. (a) The distribution of $(\sigma_3/\sigma_1)_{n}$ shows ranges of frames representing two sub-manifolds by left-right arrows and instances phases of the flock by snapshots. (b) The plot of 20 largest phase changes. The frame at the phase transition is represented by red in Figures (a) and (b)

    Figure 8.  Detecting phase transitions in a fish school. (a) The distribution of $(\sigma_6/\sigma_1)_{n}$ with left-right arrows showing ranges of frames in sub-manifolds and red dots showing frames at phase transitions. (b) Snapshots of the school before (left) and after (right) each phase transition. (c) The plot of 20 largest phase changes consisting four phase transitions marked in red with their frame numbers

    Figure 9.  Two dimensional saddle surface $\mathcal{M}^2$, described by the Equation (28) for $x_1, x_2 \in \mathbb{U} [-2,2]$

  • [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. AbaidE. Bollt and M. Porfiri, Topological analysis of complexity in multiagent systems, Physical Review E, 85 (2012), 041907.  doi: 10.1103/PhysRevE.85.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. doi: 10.1109/SIBGRAPI.2013.18.
    [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. doi: 10.1109/ICPR.2006.621.
    [8] M. BalleriniN. CabibboR. CandelierA. CavagnaE. CisbaniI. GiardinaA. OrlandiG. ParisiA. Procaccini and M. Viale, et al., Empirical investigation of starling flocks: A benchmark study in collective animal behavior, Animal Behaviour, 76 (2008), 201-215.  doi: 10.1016/j.anbehav.2008.02.004.
    [9] C. BeccoN. VandewalleJ. Delcourt and P. Poncin, Experimental evidences of a structural and dynamical transition in fish school, Physica A: Statistical Mechanics and its Applications, 367 (2006), 487-493.  doi: 10.1016/j.physa.2005.11.041.
    [10] M. BeekmanD. J. T. Sumpter and 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.  doi: 10.1073/pnas.161285298.
    [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. doi: 10.1007/978-1-4419-8963-5.
    [13] I. D. Couzin, Collective cognition in animal groups, Trends in cognitive sciences, 13 (2009), 36-43.  doi: 10.1016/j.tics.2008.10.002.
    [14] I. D. CouzinJ. KrauseN. R. Franks and S. A. Levin, Effective leadership and decision-making in animal groups on the move, Nature, 433 (2005), 513-516.  doi: 10.1038/nature03236.
    [15] A. Deutsch, Principles of biological pattern formation: Swarming and aggregation viewed as self organization phenomena, Journal of Biosciences, 24 (1999), 115-120.  doi: 10.1007/BF02941115.
    [16] J. H. FriedmanJ. L. Bentley and R. A. Finkel, An algorithm for finding best matches in logarithmic expected time, ACM Transactions on Mathematical Software, 3 (1977), 209-226.  doi: 10.1145/355744.355745.
    [17] K. GajamannageS. ButailbM. Porfirib and E. M. Bollt, Model reduction of collective motion by principal manifolds, Physica D: Nonlinear Phenomena, 291 (2015), 62-73.  doi: 10.1016/j.physd.2014.09.009.
    [18] K. GajamannageS. ButailbM. Porfirib and E. M. Bollt, Identifying manifolds underlying group motion in Vicsek agents, The European Physical Journal Special Topics, 224 (2015), 3245-3256.  doi: 10.1140/epjst/e2015-50088-2.
    [19] J. J. Gerbrands, On the relationships between SVD, KLT and PCA, Pattern recognition, 14 (1981), 375-381.  doi: 10.1016/0031-3203(81)90082-0.
    [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.  doi: 10.3390/molecules15042609.
    [21] G. H. Golub and C. Reinsch, Singular value decomposition and least squares solutions, Numerische Mathematik, 14 (1970), 403-420.  doi: 10.1007/BF02163027.
    [22] D. HelbingJ. Keltsch and 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. doi: 10.1007/b98852.
    [24] J. M. Lee, Introduction to Smooth Manifolds, Graduate Texts in Mathematics, 218. Springer-Verlag, New York, 2003. doi: 10.1007/978-0-387-21752-9.
    [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. doi: 10.1109/CVPR.2009.5206641.
    [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. doi: 10.1007/978-3-7091-6874-5_3.
    [28] M. NagyZ. ÁkosD. Biro and T. Vicsek, Hierarchical group dynamics in pigeon flocks, Nature, 464 (2010), 890-893.  doi: 10.1038/nature08891.
    [29] B. O'neillElementary 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. doi: 10.1063/1.1427476.
    [31] B. L. Partridge, The structure and function of fish schools, Scientific American, 246 (1982), 114-123.  doi: 10.1038/scientificamerican0682-114.
    [32] W. RappelA. NicolA. SarkissianH. Levine and W. F. Loomis, Self-organized vortex state in two-dimensional dictyostelium dynamics, Physical Review Letters, 83 (1999), p1247. 
    [33] E. M. RauchM. M. Millonas and D. R. Chialvo, Pattern formation and functionality in swarm models, Physics Letters A, 207 (1995), 185-193.  doi: 10.1016/0375-9601(95)00624-C.
    [34] V. Y. Rovenskii, Topics in Extrinsic Geometry of Codimension-one Foliations, Springer, 2011. doi: 10.1007/978-1-4419-9908-5.
    [35] S. T. Roweis and L. K. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science, 290 (2000), 2323-2326.  doi: 10.1126/science.290.5500.2323.
    [36] R. V. SoléS. C. ManrubiaB. LuqueJ. Delgado and 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. SumpterJ. BuhlD. Biro and I. Couzin, Information transfer in moving animal groups, Theory in Biosciences, 127 (2008), 177-186.  doi: 10.1007/s12064-008-0040-1.
    [39] J. B. TenenbaumV. De Silva and J. C. Langford, A global geometric framework for nonlinear dimensionality reduction, Science, 290 (2000), 2319-2323.  doi: 10.1126/science.290.5500.2319.
    [40] E. ToffinD. D. PaoloA. CampoC. Detrain and J. Deneubourg, Shape transition during nest digging in ants, Proceedings of the National Academy of Sciences, 106 (2009), 18616-18620.  doi: 10.1073/pnas.0902685106.
    [41] C. M. Topaz and A. L. Bertozzi, Swarming patterns in a two-dimensional kinematic model for biological groups, SIAM Journal on Applied Mathematics, 65 (2004), 152-174.  doi: 10.1137/S0036139903437424.
    [42] T. VicsekA. CziróE. Ben-JacobI. Cohen and O. Shochet, Novel type of phase transition in a system of self-driven particles, Physical Review Letters, 75 (1995), 1226-1229.  doi: 10.1103/PhysRevLett.75.1226.
    [43] E. Witten, Phase transitions in m-theory and f-theory, Nuclear Physics B, 471 (1996), 195-216.  doi: 10.1016/0550-3213(96)00212-X.
    [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. doi: 10.1109/CVPR.2004.1315192.
  • 加载中



Article Metrics

HTML views(399) PDF downloads(259) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint