Detecting phase transitions in collective behavior using manifold's curvature

  • Received: 23 September 2015 Revised: 19 July 2016 Published: 01 April 2017
  • MSC : Primary: 53C15, 53C21; Secondary: 58D15

  • 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.

    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

    Related Papers:

    [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
  • 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.


    1. Introduction

    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, in an abstract higher-dimensional space which describes the collective behavior of a group such that each frame partitioned from the collective behavior video corresponds to a point p on the manifold [4]. In this setup, the whole group evolves according to the underlying flow

    Φ:MM ;  Φ(p(t1))=p(t2), (1)

    where p(t1) and p(t2) are two points representing two consecutive frames at time-steps t1 and t2, respectively [17]. Due to an abrupt behavioral change of the group, this mapping switches from one phase space to another and indicates a phase transition of the motion. Thus, in the presence of a phase transition, the system can be represented as two distinct sub-manifolds, M(j) for j=1 and 2, along with singularities where the phase transition physically exists [18]. Herein, the most salient scenario is that the sub-manifolds intersect and make a locus L of singularities as

    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.

    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 t1 and t2 are embedded onto points p(t1) and p(t2), respectively, in the corresponding manifolds. The locus of singularities (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.

    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.


    2. Phase Transition Detection (PTD) method

    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.


    2.1. Approximating the curvature of a curve

    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 p on the curve with an arc p1pp2 of a translating circle such that the arc subtends a small angle of 2T at the center O. We consider the curvature of a translating circle instead of that of the curve since they are similar in aforesaid setup. Thus, we prove the assertion providing the relationship between curvature and singular value ratios over the data sampled on a circle.

    Figure 2. (a) Superimposing a neighborhood of the curve C at point p with an arc p1pp2 which subtend an small angle of 2T at the origin of a translating circle. (b) Zoomed and rotated secular sector p1p2O such that the blue arrow is horizontal.

    Theorem 2.1. Given a circle centered at the origin with radius r, let α number of points are uniformly distributed with density ρ on an arc which subtends an angle of 2T at the center. Let σ1 and σ2 (σ1>σ2), are two singular values computed upon the data on the curve, then σ2/σ1Mκ where κ=1/r and M=α215ρR+.

    Proof. We rotate the circular sector p1p2O such that the line bisecting the angle p1pp2 which is shown by a blue arrow in Figure 2(a) is horizontal. We consider this blue arrow as the horizontal axis and compute the singular values of the data sampled from the arc. A point p(x1,x2) on the arc is given by x1=rcost, x2=rsint for t[T,T]. Expected values of variables x1 and x2 are computed as

    μx1=12TTTrcost dt=1TrsinT (3)

    and

    μx2=12TTTrsint dt=0, (4)

    respectively. We then compute pairwise covariance between variables as

    cov(x1,x1)=12TTT(rcostμx1)2dt=r22T(T+12sin2T+2Tsin2T), (5)
    cov(x1,x2)=12TTT(rcostμx1)(rsintμx2)dt=0, (6)
    cov(x2,x1)=12TTT(rsintμx2)(rcostμx1)dt=0, (7)

    and

    cov(x2,x2)=12TTT(rsintμx2)2dt=r24T(2Tsin2T). (8)

    The covariance matrix Σ, of the data is

    Σ=(r22T(T+12sin2T+2Tsin2T)00r24T(2Tsin2T)). (9)

    The covariance matrix which is approximated to 5th order of T by using the Taylor's expansion is

    ˜Σ=(r2T44500r2T23(1T25))+O(T6). (10)

    Let eigenvalues of ˜Σ are λ1 and λ2 (λ1>λ2), then

    λ1r2T23(1T25) and  λ2r2T445. (11)

    As eigenvalues are computed upon the covariance matrix, they also relate to principal components. We denote singular values associated with principal components by σ1 and σ2 (σ1>σ2) and relate them to eigenvalues as σ2/σ1=λ2/λ1 [19]. Then,

    λ2λ1T23(5T2)σ2σ1T3(5T2). (12)

    Further,

    σ2σ1T15 (13)

    since T is small. Let, α points are uniformly distributed with the density ρ on the arc, then,

    T=α2ρκ where κ=1r. (14)

    By (13) and (14),

    σ2σ1Mκ where M=α215ρR+. (15)

    2.2. Approximating the curvature of a manifold

    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 Mm=(f1(x1,,xm),,fm(x1,,xm)) represents the parametric form of the manifold embedded in the Euclidean space Rm+1. For j=1,,m,

    v(j)p=Mmxjandˆv(j)p=v(j)pv(j)p (16)

    provide mutually orthogonal tangential vectors and unit tangential vectors of Mm at p, respectively. Thus, {ˆv(j)p|  j} is an orthonormal basis for the tangential space at p. The shape operator Sp, of the manifold Mm at the point p is defined as

    Sp=(xj1Npˆv(j2)p)j1,j2forj1,j2=1,,m (17)

    [29,34].

    Let (κ(u(j)p),u(j)p) for j=1,,m denote eigenpairs of Sp, then magnitudes and directions of principal curvatures are given by κ(u(j)p) and u(j)p, respectively [5]. The two-dimensional plane in Rm+1 which is spanned by the principal direction u(j)p and the unit normal at p, Np, is defined as the j-th principal section,

    Π(j)p={βu(j)p+γNp|β,γR}. (18)

    Thus, for j=1,,m, Π(j)p are mutually orthogonal planes. An example of computing principal sections is attached in Appendix A. Intersection of Π(j)p's with the manifold makes curves C(j)Rm+1 such that each passes through the point p. Figure 3 illustrates principal sections and curves made through that when m=2.

    Figure 3. Local distribution of data around the point p on a two dimensional manifold (M2). Principal sections Π(1)p and Π(2)p are created by using the shape operator at p, and curves C(1) and C(2) are produced by intersecting Π(1)p and Π(2)p with M2, respectively.

    Without loss of generality, for j=1,,m, we assume that the data is distributed uniformly with a sufficient density on C(j) to contain α points in a neighborhood at the point p. For all j, singular values σ(j)1 and σ(j)2 (σ(j)1>σ(j)2) are computed upon the data sampled in the neighborhood of p on C(j). By Theorem 2.1, curvature κ(j) on the curve C(j) is approximated as σ(j)2/σ(j)1M(j)κ(j) for some M(j)R+. A phase transition differentiates the manifold into two sub-manifolds such that each map with a different Euclidean space [24]. Thus, under a phase transition, geometry permits that the curvature of some curves, C(j)'s, undergo abrupt changes which also result abrupt changes of the ratios σ(j)2/σ(j)1.

    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={4R2,if R2,0,if R>2, (19)
    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 {β1ˆi+β2ˆk|β1,β2R} to produce (b) a curve in R3. (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.

    for RU[0,4] and θU[0,π]. This sombrero-hat intersects two sub-manifold, brim (green) and crown (blue) at the locus of singularities (red) representing a phase transition. Instead of constructing principal sections using the shape operator, for simplicity, we intuitively find a principal section in this example at the point (0,0,4). Since the curvature of the manifold is same in all tangential direction at this point, we choose one principal direction to be ˆi, the unit vector along x1-axis. The unit normal at this point is ˆk which is the unit vector along x3-axis. Thus, we define the plane {β1ˆi+β2ˆk|β1,β2R} as the principal section. Intersection of this principal section with the sombrero-hat gives a curve as shown in Figure 4(b) which has a high curvature at red points. Isomap residual plots indicate different embedding dimensionalities at the locus than those of two sub-manifolds.


    2.3. Phase transition via local data distribution on the manifold

    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 NpRm+1 at each point p, such that it contains αN points by using nearest neighbor search algorithm given in [16,44]. Then, we perform singular value decomposition1 for data in each Np and denote the descending order by σ1,,σα for some αN. Without loss of generality, we assume that the data distribution in each C(j) is dense enough for Np to contain data from each curve C(j), j=1,,m, made in Section 2.2. However, Np contains at least the point p, from each C(j) as shown in Figure 3 which depicts the same scenario for a two dimensional manifold M2, in R3.

    1Singular value decomposition finds singular values σ1,,σα for some αN, and two unitary matrices U and V, such that UU=VV=Iα, those provide the decomposition Dαn=UΣV for Σ=diag(σ1,σ2,σα) with σ1>>σα [21]

    According to this setting, we assert that an abrupt change which is detected by the ratio σ(j)2/σ(j)1 in some curves created through p is also detected by the ratio σα/σ1 computed over the data in Np on the manifold Mm. In this study, we use frames partitioned from a collective motion video as data. A group of agents evolving with mutual interaction can be explained in terms of a hidden manifold structure such that each frame corresponds to a single data point on the manifold. Thus, we consider the point p on the manifold corresponds to the n-th frame of the video. Let consider N frames are embedded on the manifold, thus the distribution

    {(σα/σ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,,N1. (21)

    As the distribution tn is highly volatile, we utilize α-points moving sum

    Σαn=i[nα2,n+α2]Nti;n[α2,N1α2]N, (22)

    where α/2 is the ceiling function2, and smooth the distribution. After a phase transition occurs, manifold curvature is abruptly changed and then so the singular values. Thus, a phase transition between n-th and (n+1)-th frames can be quantified by the magnitude of Σαn.

    2Ceiling function of x, denoted by x, is the smallest integer greater than or equal to x


    3. PTD algorithm

    This algorithm requires two inputs, one is the parameter α for number of nearest neighbors and the other is the data matrix D constructed next. We assume input data is gray-scale images partitioned from a video of collective behavior. We reshape each frame into a row matrix and produce the data matrix D by concatenating each row matrix vertically such that n-th row in D represents the pixel intensities of the n-th frame for some n [11]. Since the n-th row of D, denoted by D(n,:), is the coordinates of the n-th point on the manifold, Euclidean distance, denoted by dD, between any two points n and n, on the manifold is computed as

    dD(n,n)=D(n,:)D(n,:) ; n,n=1,,N. (23)

    Based on this distance, α nearest neighbors for the n-th point are extracted and denoted as the set Nn (same as Np in Section 2.3). Then, we compute αn over Nn as explained in the Section 2.3. Algorithm outputs magnitudes of phase changes Σαn, so we can choose the largest among them as phase transitions. The method of detecting phase transitions is given as Algorithm 1.

    Algorithm 1 Detection of Phase Transition in Collective Behavior.
    Procedure PTD (α, D)
    1:Perform nearest neighbor search in [16,44] to obtain α nearest neighbors for each frame in D. Here, we denote α nearest neighbors of the n-th frame in D by the set Nn.
    2:Perform singular value decomposition [21], over Nn and denote the descending order of singular values by σ1,,σα for some αN.
    3:Compute the ratio σα/σ1 for Nn and denote by (σα/σ1)n, where n=1,,N.
    4:Compute absolute moving difference of ratios, tn=|(σα/σ1)n+1(σα/σ1)n|, for n=1,,N1.
    5:Compute αpoints moving sum, Σαn=i[nα/2,n+α/2]Nti, of ti for n[α/2,N1α/2]N, where α/2 is the ceiling function.
    6:Largest values of Σαn are extracted as phase transitions.
    end procedure

    4. Group behavioral examples

    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.


    4.1. A simulation of the Vicsek model

    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 N(i)n to denote all the nearest-neighbors of the i-th particle within a unit distance at the n-th time-step. The Vicsek model [42] updates the orientation θ(i)n of the i-th particle at the n-th time step as

    θ(i)n=arg(V(i)n1)+ϵ(i)n1,where V(i)n1=1|N(i)n1|jN(i)n1[cos(θ(j)n1)sin(θ(j)n1)], (24)

    and ϵ(i)n1 is the noise parameter sampled from the Gaussian distribution with mean zero and standard deviation σ. Here, V(i)n1 is the average direction of motion of particles in N(i)n1. The position a(i)n of the i-th particle at the n-th time step is therefore updated as

    a(i)n=a(i)n1+s(i)n1[cos(θ(i)n1)sin(θ(i)n1)]δ, (25)

    where δ is the time-step size and s(i)n1 is the speed of the i-th particle at the time-step (n1).

    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.05 and s(i)n=0.1 for all i and n. We impose three phase transitions by changing the noise ϵ(i)n, using a variable standard deviation

    σ={0.25,if n<50,1,if 51n<100,0.05,if 101n<150,0.75,if n150, (26)

    for all i, in the Gaussian distribution. For n=1,,200, we convert point-mass positions of particles at the n-th time-step, {a(i)n|i=1,,50}, into a gray-colored frame such that the position of each particle is represented by a black square of pixels 10×10. Herein, we first convert the positions of particles into a sparse matrix An, at each time step n=1,,200. Then we make a rotationally symmetric Gaussian low-pass filter B of size 10×10 pixels with standard deviation of 10 pixels and filter the matrix An by B to generate

    Cn(n1,n2)=10k1=110k2=1An(n1k1,n2k2)B(k1,k2) ;  n1,n2 (27)

    for n=1,,200 [12]. Each matrix Cn is converted into a frame and all the frames are finally converted into a one data matrix D.

    We run PTD algorithm upon D with several α values and observe that the distribution (σ4/σ1)n generated by α=4 (Fig. 5(a)) shows clear phase changes with respect to noise changes. The plot of 20 largest phase changes (Fig. 5(b)) reveals that three phase changes at frame numbers 150,99 and 50 are significant than others and we consider them as phase transitions. Thus, the manifold representing the whole motion is partitioned into phase transition free 4 sub-manifolds ranging 150,5199,100150 and 151200. We run Isomap on each range of frames with the neighborhood parameter four and obtain the residual plots given in Figure 5(c). The Isomap residual plots indicating the embedding dimensionality by an elbow, reveal that the sub-manifolds are embedded in three, six, two, and four dimensions, respectively.

    Figure 5. Detecting phase transitions in a particle swarm simulated using the Vicsek model with alternating noise levels. (a) The distribution of (σ4/σ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.

    4.2. A human crowd

    A video of a human crowd available on-line at [3] containing a phase transition at the 69-th frame from walk to run is considered now.

    As in Example 4.1, we first convert all the frames into a data matrix D, and then run PTD algorithm on it. When α=3, we observe that the distribution (σ3/σ1)n given in Figure 6(a) shows clear trade-off about the frame numbers. Figure 6(b) shows that only the first phase transition having a magnitude of 0.23 is significant. The manifold representing the crowd is partitioned such that frames 169 represent one sub-manifold and frames 7090 represent the other sub-manifold. The snapshots in Figure 6(a) show the phases walking (left) and running (right) of the crowd. Isomap running on frames 169 and 7090 with α=3 reveals that the embedding dimensionalities of corresponding sub-manifolds are three and four, respectively.

    Figure 6. Detecting a phase transition between phases of walking and running in a human crowd [3]. (a) The distribution of (σ3/σ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.

    4.3. A bird flock

    We now detect a phase transition, differentiating phases of sitting and flying, at the 58-th frame in a video of a bird flock obtained on-line at [1].

    We run PTD algorithm on the data matrix with α=3 and obtain the distribution (σ3/σ1)n in Figure 7(a). The plot of 20 largest phase changes in Figure 7(b) illustrates that the video consists one phase transition at the 58-th frame and has the magnitude of 0.32. Then, the manifold is partitioned into two sub-manifolds representing frames in the ranges 158 and 59100. Isomap running on aforesaid ranges with α=3 reveals that the embedding dimensionalities of corresponding sub-manifolds are two and three, respectively.

    Figure 7. Detecting a transition in a bird flock between phases sitting and flying [1]. (a) The distribution of (σ3/σ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).

    4.4. A fish school

    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 α=6 and obtain the distribution of (σ6/σ1)n (Fig. 8(a)). The plot of phase changes (Fig. 8(c)) reveals that the first four phase changes located at frames 40,112,185 and 222 are phase transitions. Now, the manifold is partitioned into phase transition free sub-manifolds representing frames in ranges 140,41112,113185,186222 and 223250 as shown by left-right arrows in Figure 8(a). According to Figure 8(b), the pair of snapshots at the 40-th frame exhibits a large global abrupt change since the school reacts to the panic together. However, by the evidence observed through Figure 8(b) and snapshots, the second and the third phase transitions are abrupt and local while the last is gradual and local. Isomap is run on all sub-manifolds with α=6 and embedding dimensionalities are obtained as two, four, three, two, and six, respectively.

    Figure 8. Detecting phase transitions in a fish school. (a) The distribution of (σ6/σ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.

    5. Conclusions and discussion

    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 (α). Algorithm outputs the distribution (σα/σ1) and 20 largest phase changes which are ranked according their magnitudes. Based on these outputs, manifold representing the whole collective behavior is partitioned into phase transitions free sub-manifolds.

    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 (σ4/σ1)n from one frame to the other justify the sensitivity of the method. Thus, our method is capable of detecting the exact phase transitions at frames 50 and 150, however it approximates the phase transition at 100-th frame as at 99-th frame with one frame of error. Since this approximation is accurate enough, we partitioned the manifold into four sub-manifolds about frames 50, 99, and 150. Herein, we conclude that the method is adept at perceiving the nature of the collective behavior and spatial distribution of particles to approximate phase transitions.

    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 α is always important for the method to extract correct phase traditions. This is done by either using the prior-knowledge about the data or running the algorithm with several α's to determine the best value which differentiates and highlights phase transitions. We can always rely on a small α value when the data on the manifold is sufficiently dense [39]. Since the current techniques of making videos with high frame rates, we can always generate sufficiently large quantity of frames those would then be densely represented as data points on a manifold. Thus, in this study, we run PTD algorithm with small α values taken to be all natural numbers less than 10 and then decide the best value by analyzing corresponding phase change plots.

    In future, we will fabricate an automated method to determine the best α value which will give the best phase change plot to extract phase transitions. We will also establish a novel approach of detecting phase transitions under gradual changes of the behavior of a multi-agent system which is not addressed in this work.

    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.


    Acknowledgments

    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.


    Appendix A. Computing principal sections from the shape operator

    Here, we provide an example of computing principal sections of a two dimensional manifold in R3 called a saddle surface given in the parametric form

    M2=(x1,x2,x313x1x22)R3, (28)

    shown by Figure 9.

    Figure 9. Two dimensional saddle surface M2, described by the Equation (28) for x1,x2U[2,2].

    For an arbitrary point p=(x1,x2,x313x1x22) on the surface, we compute unit tangential vectors as

    v(1)p=M2x1=(1,0,3[x21x22])ˆv(1)p=v(1)p|v(1)p|=(1,0,3[x21x22])9(x21x22)2+1, (29)

    and

    v(2)p=M2x2=(0,1,6x1x2)ˆv(2)p=v(2)p|v(2)p|=(0,1,6x1x2)36x21x22+1. (30)

    Then, while the unit normal at p, Np, is

    Np=v(1)p×v(2)p|v(1)p×v(2)p|=(3[x21x22],6x1x2,1)9(x21+x22)2+1, (31)

    tangential directions are

    x1Np=Npx1=6(x1[18x22{x21+x22}+1],x2[9{x41x42}1],3x1[x21+x22])[9(x21+x22)2+1]3/2, (32)

    and

    x2Np=Npx2=6(x2[18x21{x21+x22}+1],x1[9{x41x42}+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(x21x22)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(x21x22)2+1], (36)
    S(2,2)p=x2Npˆv(2)p=6x1[9(x21+x22)2+1][36x21x22+1]. (37)

    Particularly, the shape operator Sp=(S(1,1)pS(1,2)pS(2,1)pS(2,2)p), at p=(1,0,1) is

    S(1,0,1)=(3/5006/10). (38)

    Computed eigenpairs, (3/5,(1,0)) and (6/10,(0,1)), of S(1,0,1) describe two pairs of principal curvatures and directions in the tangential space at p=(1,0,1). These two dimensional principal directions are made to be three dimensions as (1,0,0) and (0,1,0) by introducing the third dimension. The unit normal at p=(1,0,1) is N(1,0,1)=110(3,0,1), thus the principal sections in R3 at p are given by

    Π(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.
  • This article has been cited by:

    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
  • Reader Comments
  • © 2017 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3483) PDF downloads(511) Cited by(2)

Article outline

Figures and Tables

Figures(9)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog