Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
119,459 characters · 50 sections · 72 citation commands
Coordination Event Detection and Initiator Identification in Time Series Data
\orcid{0000-0003-3131-0370} \email{[email removed]}
\email{[email removed]}
\email{[email removed]}
\email{[email removed]}
\email{[email removed]}
\email{[email removed]}
\ccsdesc[300]{Information systems Spatial-temporal systems} \ccsdesc[300]{Information systems Data mining} \ccsdesc[300]{Applied computing Sociology} \ccsdesc[200]{Applied computing Economics}
Which zebra initiated the flight from a lion? Whom does the elephant herd follow to water? Who is the trend-setter whose opinion many follow at the moment? (And is it the same person whether it's the opinion about the future of AI or the hottest lunch spot?) In all these scenarios, the initiator might not be the one who is speaking the loudest or positioned at the front of the group after the group has already agreed to follow Dyer:2009aa,Stewart:1947aa. Thus, in order to identify those initiators or trend-setters, we must also determine the moment of the group's decision to follow.
{Initiating} a group's behavior is a form of leadership WilsonSocbio,Stueckle2008. Leadership is an important aspect of the social organization, formation, and decision-making of groups of people in online and offline communities, as well as other social animals. Understanding the dynamics of emerging leadership allows researchers to gain insights into how social species make decisions. Until recently, many works defined leaders by their physical or behavioral characteristics rather than by observing processes of interaction LeadershipBook.
The availability of data from physical proximity sensors, GPS, and the web opens up the possibility of measuring leadership as the process of initiation in online activities, face-to-face human interactions, animal populations, and aggregate social processes such as economic activity. This paper presents the new computational problem of inferring leader identity in the context of successful initiation of coordinated activities among groups of individuals or other entities, as well as proposes the first automated method for unsupervised leader identification. The method uses only time series activity data of entities, with no additional information. The proposed approach automatically determines (1) the time interval of group coordination, (2) the time when the (possibly implicit) decision for that coordinated activity was made, (3) the identity of the coordination initiator, and (4) the mechanism by which the group came to follow the initiator.
Coordinating patterns of individual activity is a challenge that all social organisms face. Diverse strategies--from democratic to dictatorial--have emerged to allow members of groups to reach consensus Conradt:2003aa. Leadership plays a key role in organizing the collective (i.e. group) behaviors of social organisms ranging from humans Dyer:2009aa to hymenoptera Weinstein:1997. It potentiates complex patterns of cooperation and conflict (e.g., lions Heinsohn1260, hyaenas Boydston:2001, meerkat Mares3989, chimpanzees Gilby:2015, humans Glowacki:2015), organizes group movements Couzin:2005aa,Dyer:2009aa, and may prevent free-riding Hooper2010633.
In the context of group behavior and decision-making in biology and sociology, leaders are individuals who successfully induce a group of others to follow them to a common goal, state, or behavior WilsonSocbio,Stueckle2008,Couzin:2005aa,Petit2010635. Biological studies showed that leaders may be context-specific Song2014crowdmodel,Couzin:2005aa and the important initiators of particular group activities are not necessarily the individuals found at the top of their group's social dominance hierarchy Brent2015746,Strandburg-Peshkin1358.
Substantial interest currently exists in identifying leaders and determining how they influence the behavior of others in their social environment. Previous work in several domains defined leadership according to physical characteristics ({\em e.g.,} size, sex WilsonSocbio), positions in location-based social networks PhamICDE2016, rule-based modelsSong2014crowdmodel, physical trajectory and association patterns lusseau2009emergence,andersson2008reporting.
Computationally, most previous work uses a global notion of leadership and creates a global, static leadership ranking over the entirety of the input data goyal2008discovering, Bakshy:2011:EIQ:1935826.1935845. Other domain-specific methods infer leadership from implicit pairwise dyadic dominance or leader-follower interactions andersson2008reporting, PhamICDE2016,kjargaard2013time. Some methods define an explicit network over the dyadic interactions or use a known network topology Sun2011 and use network measures, such as PageRank and HITS, or cascade size to identify leaders Bakshy:2011:EIQ:1935826.1935845.
Leadership has also been studied in explicit social network settings. From a social network perspective, leaders can be characterized as influential individuals who have many followers that imitate the leader's actions goyal2008discovering, and, thus, successfully take a group from one behavioral state to another. Much of the computational work has focused on the problem of influence maximization (IM)--i.e. how individuals are able to maximize their impact on the behavior of the group as a whole by iteratively affecting local network neighborhoods kempe2003maximizing, goyal2010learning. This approach assumes that the network structure is known.
Alternatively, leadership can be viewed as the causal effect for the followers' actions. Granger Causality 10.2307/1912791 is one of the methods used for inferring cause and effect within a set of time series. The idea is that if we can use time series $Y$ to significantly improve the prediction of the future activity of time series $X$, compared to using only the past information from $X$, then $Y$ Granger causes $X$. Certainly, this approach does not distinguish between a direct causality and confounding effects. There is a large body of work using Granger Causality to infer temporal dependency among time series Arnold:2007:TCM:1281192.1281203,liu2009nonparanormal,liu2012sparse. However, there is no explicit work using Granger Causality to infer leaders in time series, though it is certainly a fruitful direction to explore.
There is a clear gap between the biosociological definitions of leadership in group decision-making and the existing computational approaches. Currently, there are no computational approaches that (1) view leaders as initiators of group behavior change, which can (2) identify the timing of the process of the change initiation and the group's decision-making in (3) arbitrary contexts, under (4) a variety of leadership models.
In our previous version of this paper in flicaMilets, we focus on the definition of leadership as the initiation of coordinated activities. We aim to close the gap between the biosociological view of the role of leaders in group decision-making, the computational formalism, and the methodology.
Therefore, the first part of our contribution is establishing and formalizing this {\bf new computational problem of coordination initiation inference}. We call it the {\sc Coordination Initiator Inference Problem}\xspace. Our formulation is a generalization of many related leadership inference computational problems. We explicitly relate existing leadership and influence propagation problems as special cases of our formulation. The new formulation uses only the time series of individual behavior as input, with no assumption of additional information such as demography, prior historic data, dominance hierarchy, or a network structure. The problem formulation aims to identify different local instances of behavior initiation, allows the identity of the initiator to be instance-specific, and makes no assumption on the leadership or behavioral model.
Our additional contribution is in proposing a computational {\bf solution framework} to this new {\sc Coordination Initiator Inference Problem}\xspace. We propose a general, scientifically grounded, unsupervised, and extendable framework with few assumptions for identifying individuals who lead a group to a state of coordinated activity (or, more generally, an entity that induces group coalescence). Our framework is capable of:
We demonstrate the framework's ability to analyze leadership in coordinated activity on synthetic and real datasets over several domains. We compare our framework with state-of-the-art methods for leadership identification for the special cases of our problem where such methods are applicable. For many instances of our new problem, there are no existing methods. We demonstrate that existing solutions fail and do not extend to these instances. We use synthetic simulated data to validate each aspect of the framework. We analyze two biological datasets -- GPS tracks of a baboon troop and video-tracking of fish schools -- as well as stock market closing price data of the NASDAQ index. The results are consistent with ground-truthed biological data. Moreover, the framework finds many known events in financial data, which are not otherwise reflected in the aggregate NASDAQ index. Our approach is easily generalizable to any coordinated activity in time series data of interacting entities. \\
In addition, in this paper, we propose a new group activity classification method based on the {\em following network} framework. We use it to classify group activity in a dataset of GPS tracking of a troop of baboons. There are four group activities in the baboon dataset: sleeping, hanging-out, coordinated non-progression, and coordinated progression. By using only the network density as a feature, our simple classifier performed better than the state-of-the-art classifier method which used 24 features in baboon activities classification task li2016adversarial.
The Influence Maximization problem is closely related to {\sc Coordination Initiator Inference Problem}\xspace. In fact, {\em successful} Influence Maximization, where a large fraction of the population is influenced, is a special case of {\sc Coordination Initiator Inference Problem}\xspace. When the influence is spread to a majority of the population, that population is now in a coordinated state, with the decision period starting at the initiation of the influence and the initiators being that source of influence. However, {\sc Coordination Initiator Inference Problem}\xspace goes beyond Influence Maximization in every aspect of the framework and can capture different models of decision-making, coordinated activity, as well as repeated and context-specific dynamics of coordination.
Given a collection of time series, we want to find initiators of highly coordinated patterns. To formally state the {\sc Coordination Initiator Inference Problem}\xspace, we need to formalize notions of “coordination” and “initiation.”
First, we define an intuitive notion of a {\sc following relation}, as “two individuals performing the same sequence of actions (or generating time series values) with some fixed delay (Fig. (ref)).” Formally:
In periodic time series, such as a sine wave, we use Lemma (ref). If we have two sine waves that have the same frequency but different phase, then we consider them as a pair of time series that follow each other, from which it can be concluded that they are equivalent. For instance, in Fig. (ref), $U$ and $W$ are two sine waves, which have the same frequency but different phase. Because $U \prec W$ with time delay $\Delta t_{U \prec W} > 0$ and $W \prec U$ with $\Delta t_{W \prec U} > 0$ , by the second case in Lemma (ref) above, $U \equiv W$.
Next, {\sc coordination}, or intuitively “all individuals performing the same sequence of actions, at possibly varying delays (Fig. (ref)),” is formally defined as:
Finally, the {\sc initiator} is intuitively “an individual who first performs a sequence of actions, and all other individuals follow,” formally defined as:
In Fig. (ref), $Q$ is an initiator of coordination. The coordination interval starts at the beginning of $W$. We are now ready to precisely state the problem of identifying the individual who initiates a coordinated behavior:
Let $\mathcal{U}$ be a coordinated set of time series and $L \in \mathcal{U}$ be the initiator. Since $\mathcal{U}$ is a partial order set and $\forall U_i \in \mathcal{U},\; L \prec U_i$, then, by definition, $L$ is the minimal element. Moreover, $\mathcal{U}$ is a linear order set since for every pair $U_i,U_j \in \mathcal{U}$, either $U_i \prec U_j$ or $U_j \prec U_i$.
Recall that PageRank PageRank_Brin1998107 score, $\pi_i$, of a node $i$ in a network $G$ is defined as follows:
Where $\pi_i \in [0,1]$, \; $d\in (0,1]$ is a constant number, $e_{k,i} \in \{0,1\}$ is one if $e_{k,i} \in E$, $\mathcal{N}^{in}_i$ is a set of neighbor nodes of $i$ such that $k \in\mathcal{N}^{in}_i$ if $e_{k,i} \in E$, and $\mathcal{N}^{out}_i$ is a set of outgoing neighbor nodes of $i$ such that $k \in\mathcal{N}^{out}_i$ if $e_{i,k} \in E$.
As a corollary of Lemma (ref), since all the time series follow the initiator $L$ within the coordination interval $[t_1,t_2]$, then $L$ has the highest PageRank score in ${\mathcal U}$ during that coordination period. Moreover, Lemma (ref) allows us to infer the order of following among the time series within the coordination period, as defined by the PageRank values.
In real situations, Def. (ref) requires the exact match, which rarely happens. Therefore, we provide relaxation of following relation to deal with noise in realistic situations below.
The difference between a following relation in Def. (ref) and Def. (ref) is that the notion of $\sigma$-following relation lacks the transitivity property\footnote{This is similar to non-transitive dice: \url{https://en.wikipedia.org/wiki/Nontransitive_dice}}. Fig (ref) shows the example of three time series and their $\sigma$-following relation with some unknown $\sigma>0.5$. In this example, $Q$ is similar to $U$ and $U$ is similar to $V$ greater than 0.5. However, $Q$ and $V$ are not similar at all. Therefore, the $\sigma$ following relation does not possess the transitivity property.\\
Next, we can define a notion of coordination by using $\sigma$-following relation as follows.
Even though an initiator of $\sigma$-Coordination interval is not a minimum element anymore due to $\sigma$-following relation does not possess transitivity property, an initiator suppose to have a highest number of followers. Hence, PageRank is still an appropriate measure for finding an initiator.
In this section, we present a Framework for Leader Identification in Coordinated Activity (FLICA) as the solution for the {\sc Coordination Initiator Inference Problem}\xspace. On real data, the above formalization is very restrictive, so we relax the exact {\sc following relation}, and full {\sc coordination} to identify `following' and partial `coordination' in real applications. Furthermore, multiple coordination events often exist within a set of real time series data. Constructing a single aggregated network would not capture the dynamics of these events. Therefore, FLICA uses a dynamic network approach.
Fig. (ref) shows the framework overview. At each time step, we infer following relations to construct a sequence of following networks. We then use network density to detect intervals of coordination, and the time series of PageRank values to identify the initiators of these coordination intervals.
Fig. (ref) presents a key example and a brief introduction to our framework, on real GPS trajectory data of olive baboons (Papio anubis). Fig. (ref)-(ref) show the leadership of movement of the group by baboon ID3 (Black). Fig. (ref) shows the `following' network in the coordination interval. Individual ID3 has the largest PageRank in the first two snapshots but the PageRank of individual ID1 (Blue) surpasses ID3 when the network is `coordinated' (e.g. moving together). If we measure the initiator ranking after the network has coalesced, then we miss that ID3 initiated coordination and `built' the network in the pre-coordination interval (to the left of the first dotted red line).\\
We now present each step of the computational framework of FLICA. We will discuss the following relation inference in Section (ref), the construction of the following network in Section (ref), identification of the coordination interval and the preceding decision-making period in Section (ref), the identification of the initiator in Section (ref) and the details of model and parameter choices at each step.
Given a pair of time series $U,Q$, our task here is to find a following relation between $U$ and $Q$. However, we relax a notion of following relation in Def. (ref) to allow some degree of distortion between two time series that follows each other. A measures we need should satisfy two properties. First, a measure must be able to identify common pattern between $U$ and $Q$. A common pattern might not happens in $Q$ the same time as $U$ and the common pattern might have some degree of distortion. Second, a measure must be able to infer a time delay between common patterns in $U$ and $Q$. With these properties, for a $(U, Q)$ pair of time series, we use Dynamic Time Warping ($\mathrm{DTW}$) Sakoe1978 to measure whether $U$ follows $Q$. DTW is shown to perform better than several other methods in inferring following relation in time series kjargaard2013time and it is tolerant to noise doi:10.1137/1.9781611974010.33. Fig. (ref) (Left) shows two time series, where time-shifting $Q$ ahead in time produces a better match to $U$, illustrated in the warping path in Fig. (ref) (Right). Let $P_{U,Q}$ be a sequence of index pairs $(i,j)$ which comprise the $\mathrm{DTW}$ optimal warping path of $(U, Q)$. We compute the mean of the signed index difference over this sequence of index pairs:
This function measures the extent of warping between two time series. If time series cannot be shifted one-onto-the-other with a consistent positive or negative sign, $|\mathrm{s}(P_{U,Q})| \approx 0$, then there is no following relation between $U$ and $Q$. When $\mathrm{s}(P_{U,Q})$ is positive, $Q$ follows $U$, otherwise, $U$ follows $Q$. In Fig. (ref), $\mathrm{s}(P_{U,Q}) \approx -3$.
As shown in Section (ref), a coordinated activity is dynamic in the aspect of who leads a group at each time step. Using only summary statistics of static following network to represent the entire coordinated activity cannot capture dynamics of coordinated activity. Therefore, we deploy a dynamic network procedure to analyze coordinated activities in time series, which is a common technique to deal with dynamics of data holme2014temporal.
In our setting, the set of $n$ $m$-multidimensional time series $\mathcal{D}$ ({\em e.g.,} a matrix of size $[n \times m \times t^* ]$), a window size parameter $\omega$, and a window shift parameter $\delta$ (default is $0.1\omega$) are the inputs for our framework.
\IncMargin{1em}
\DecMargin{1em}
Let the $i$th time interval be given by: $w(i) = [(i-1) \times \delta,(i-1) \times \delta + \omega]$. For each $w(i)$, we extract a set of sub time series $\mathcal{Q}_i$ from $\mathcal{D}$. The $\mathcal{Q}_i$ is the $[n \times m \times \omega ]$ dimensional matrix of the time series set. Then we construct a following network $G=(V,E)$ as defined in Def. (ref). The nodes represent the time series from $\mathcal{Q}_i$ and $E$ is a set of edges between time series nodes such that if $U,W \in \mathcal{Q}_i$ and $U$ follows $W$ according to Eq. (ref), then $e_{U,W} \in E$ with the edge weight $|\mathrm{s}(P_{U,W})|$. We calculate a following network for each $w(i)$ to construct a dynamic following network $G^*=(V,E^*)$. The pseudo code is given in Procedure (ref).
Network density of the following network serves as the measure of the extent of coordination over all time series pairs (by Def. (ref), during the coordination interval {\em every} pair has a following relation.) We can use this observation to identify times of approximate coordination.
Given a time series of network densities, denoted by $\mathrm{d}$, over a dynamic following network $G^*$, and a density threshold parameter $\lambda$, the time interval $[t_i,t_j]$ is a $\lambda$-coordination interval if $\mathrm{d}(t) > \lambda$ for all $t \in [t_i,t_j]$. The pre-coordination interval of coordination $[t_i,t_j]$ is the interval $ [t_k,t_i-1]$, where the discrete derivative $\mathrm{d}(t) -\mathrm{d}(t-1) \geq 0$ for all $t \in [t_k,t_i-1]$. Together, these intervals are one coordination event, represented by the 3-tuple of time indices $I=(t_k,t_i,t_j)$. The collection of coordination events is a set $C=\{I_l\}$. All complete event intervals $[t_k, t_j]$ are mutually disjoint in $C$, and $|C|$ denotes the total number of 3-tuples. Fig. (ref) illustrates the definition of a coordination event as a pair of time intervals. To reduce the number of intervals generated near the threshold $\lambda$, we apply a greedy merging of nearby coordination intervals (taking the range from the window size $\omega$).
On each coordination {event} $I=(t_k,t_i,t_j)$, let $R_I$ be some ranking of individuals within the pre-coordination interval $[t_k,t_i-1]$. We focus on ranking within pre-coordination because this is the interval where coordination is initiated. The {\em global} rank order of pre-coordination, denoted by $\hat{R}$, is the average of all $R_I$ where $I \in C$.
We measure {\bf initiator ranking} according to three different methods: PageRank PageRank_Brin1998107, velocity convex hull (VCH), and position convex hull (PCH). Recall, that by Lemma (ref), if $U$ follows $V$, then the PageRank of $U$ is less than that of $V$. Thus, the initiator is expected to have the highest PageRank. VCH measures how often an individual moves faster than others. It represents a model of leadership for movement. This model can be found in many social species Dyer:2009aa,Stueckle2008. PCH measures how often an individual moves to an area before others. For example, in a flock model andersson2008reporting, a leader is positioned at the front of the group's trajectory.
PageRank is a standard method for measuring the importance of a node recursively by the importance of the nodes linking to it. In a directed network where a link represents a following relations between nodes, PageRank measures `following' paths passing through a particular node. Thus, it fits well with our definition of leadership.
PageRank returns a weight vector of length $n$, with a sum of 1. For each time step $t$, we calculate PageRank for each static graph $G_t$ within a dynamic following network $G^*=(V,E^*)$. Let $\mathcal{R}=(R_{pr, 1},\dots, R_{pr,t^*})$ be a sequence of $n$-length PageRank Order vectors where $R_{pr, t} = \mathrm{argsort}(PageRank(G_t))$ such that $R(i)_{pr, t}$ represents the rank of individual $i$ and $R(i)_{pr, t}<R(j)_{pr, t}$ if the PageRank value in Eq. (ref) of $i$ is greater than the value of j ( $\pi_i>\pi_j$.) The leader $L$ at time $t$ is the individual who has the highest value of PageRank $\pi_L$ or $R(L)_{pr, t}=1$ . Note that $\mathrm{argsort}(\bullet)$ returns the index list of sorted values w.r.t. descending order.
In the next two sections, the $s$-energy work by Chazelle doi:10.1137/100791671 motivates the use of the convex hull as the measure of the level of initiation of a state change for the group. Chazelle showed that if every agent in a group remains within the convex hull of its neighbors (even if the neighbors change) at each time step, then the system converges to an equilibrium. Thus, to change the steady state, somebody needs to break out of the convex hull of their neighbors. In the initial state, all individuals states such as velocity or position are inside the group's convex hulls of that state. Then after the group decides to change its state, some individuals must step outside the group convex hull to make the change. Hence, by using convex hull analysis, we can measure whether the initiators are also state changers. Specifically, we use convex hull (of position and velocity) analysis to characterize leadership models.\\
The velocity convex hull measures the frequency with which the discrete time series derivative ($dQ/dt$) associated with a node $i$ is outside the bounds of the population's discrete derivative distribution (including node $i$) in the previous time step. In aggregate, a high rank of this measure indicates which node first `moves' in the group.
The convex hull can be computed on arbitrary $m$ dimensions of a multidimensional time series, or their derivatives, jointly or independently. The convex hull function $ \mathrm{CH}(\bullet)$ returns an $m$-dimensional surface represented as lines between points in the input data, which encompass all other points.
Let $\mathbb{V}$ be a $[n \times t-1]$-sized matrix measuring individual velocity over time, on time series dataset $\mathcal{D}$, which is a $[n \times m \times t^* ]$-sized matrix . For an individual $i$ at time-step $t$, we define the following indicator function: \footnote{ We use `*' subscript notation in matrices to indicate slicing in the dimension(s).}
For time step $j$ we output an $n$-length rank order vector as $R_{v, t} = \mathrm{argsort}((\mathrm{VCH}(\mathbb{V}, i, t))_{i=1...n})$.
The position convex hull is analogous to velocity, except that our indicator function measures an individual's position relative to the convex hull containing the population at the previous time step. Rather than look at velocity of initiation, this measure captures an individual's frequency of moving outside the geometric boundaries of the group in the time series space, and close to the average heading of the group (e.g. in `front' of the group).
We compute the convex hull function on time-step $t$, $H_{t}$ = $\mathrm{CH}(\mathcal{D}_{*, *, t})$, and also introduce the heading vector of individual $i$: $\vec{v}_{i,t} = (\mathcal{D}_{i,*,t-1}, D_{i,*,t})$, and the population heading vector: $\vec{v}_{t}$ = $(1/n)\sum_{i=1..n} \vec{v}_{i,t}$. We define the function $\mathrm{IN}(\text{A, B})$ to denote standard `B contains A' spatial queries between two geometry objects, and $\measuredangle(\vec{v_1}, \vec{v_2})$ to measure the angle between two vectors $\vec{v_1}$ and $\vec{v_2}$.
Using these definitions, we define the position convex hull indicator function for individual $i$ at time $t$:
For time step $t$ we output an $n$-length rank order vector as $R_{p, t} = \mathrm{argsort}((\mathrm{PCH}(D, i, t))_{i=1...n})$.
Let the global rank ordering of pre-coordination for PageRank be denoted by $\hat{R}_{pr}$, for VCH by $\hat{R}_{v}$, and for PCH by $\hat{R}_{p}$. To measure global leadership of pre-coordination in our framework, we order individual nodes $i$ based on initiation support with respect to one of these ranking methods, $R_{\bullet, I}$ , over all coordination events $I \in C$. For example, $R_{pr, I}$ is PageRank-rank-ordered list at the coordination event $I$. If an individual $i$ is at 1st rank at $I$, then $(i, 1) \in R_{pr, I}$; $i$ is an initiator. The initiation support for a node $i$ is the fraction of coordination events at which it was ranked 1 (by a ranking measure $R_{\bullet}$):
We use the Kendall rank correlation coefficient $\tau()$ Kendall1938 to compare event-local and global rank-orders. To compare global and local rank orders, we use the mean Kendall rank correlation over all coordination events against the global by Eq. (ref). For example, $\mathrm{corr}_{v}$ compares local and global velocity-convex-hull-rank orders.
Similarly, we compute the mean Kendall correlation between local rankings associated with different measures (e.g. VCH, PCH) by Eq. (ref).
$\mathrm{corr}_{\bullet}$ formalizes our intuition that leaders consistently move outside of the spatial extent ($\mathrm{corr}_{p}$), or the distribution of velocity over the population ($\mathrm{corr}_{v}$). By comparing the global vs. local correlation in rank ordering, we measure the stability of the global ranking is over time.
$\mathrm{corr}_{\bullet, \bullet}$ measures the relationship between higher-order graph structure and simple time series features. Using this measure, we can gain a better understanding of the high-level aspects of initiating coordination. For example, we see whether changing velocity ($\mathrm{corr}_{v, pr}$), or position ($\mathrm{corr}_{p, pr}$) within the group is correlated with network rank position.
Our proposed framework uses local alignment on time series subsequences, rather than global alignment on the full time series. Fig. (ref) presents a motivation for this choice. Suppose we intend to match sparse `following' events represented as the pair of spikes with relatively low magnitude at the end of the red and blue time series. In Fig. (ref), the time series is shifted to match one of the two patterns, depending on the cost. This forces a mismatch of the `following' event. Similarly, Fig. (ref) has a low cost matching by shifting the entire time series at a constant rate. By matching only local subsequences, we can recover both of these `following' events.
We evaluate our framework on eight synthetic movement trajectory models and three real datasets.
In this model, we fix a single initiator who initiates movement from initial positions of the population. At the start of the pre-coordination interval, the initiator moves in a fixed direction and acceleration. Other individuals wait for a randomly sampled lag, before following the initiator at a fixed acceleration (with sampled noise in the heading). After a fixed duration of coordinated movement over the entire population, individuals decelerate at random, until stopping. Fig. (ref) (left) shows the example of DM. The Switching Dictatorship model (DM-S) selects two fixed individuals over each trial: a single individual as an initiator during pre-coordination, and another single individual as `initiator' during coordination. Fig. (ref) shows an example of following-network-density time series of DM-S.
This model is a variation of DM, where we fix a number of individuals (n=4) to follow the previous individual in the sequence, after a sampled lag. The remainder of individuals in the population follow exactly one of these high-ranking individuals, allocated in decreasing proportion per rank. Fig. (ref) (right) shows the example of HM. The Switching Hierarchical model (HM-S), similarly to DM-S, selects unique pairs of individuals for each hierarchy level, switching after the pre-coordination interval as in DM-S.
This model is a variation of the Dictatorship model where each coordination event has a different, unique initiator. For example, in one of our applications, a troop of baboons may follow an initiator to a food source in the morning, and follow a different initiator in the evening to the sleeping site. No existing methods can infer these two situations except our framework. Fig. (ref) shows an example of following-network-density time series of EM.
In this model, we fix $k$ initiators who initiate movement from random initial positions of the population. At the start of the pre-coordination interval, all initiators move on a single target. Non-initiators move in randomly sampled directions with a fix velocity, then follow their initiators after a random time lag. After the pre-coordination period, all individuals move toward a single target, without following their initiators. The example of INIT-k model is at Fig. (ref). We run simulations for INIT-1 and INIT-4 initiator models.
This model Song2014crowdmodel is a collective movement model where $k$ (=4) informed individuals move toward a target, and the remaining (=16) uninformed individuals move in a linear combination of a direction toward the group's centroid, and the average direction of the group. The example of CM is at Fig. (ref).
This model kempe2003maximizing initiates individual movement by propagation of a linear threshold process on the dynamic network, defined by the $k$-nearest neighbors at the current time-step. The model is parameterized by $\rho$, the proportion of these $k$ neighbors required to be infected in order to initiate movement. Once activated, the individual follows a single initiator. The initial probability of activation for each individual is $0.5$. We explore the parameter space on combinations of: $k \in \{3,5,10\}$ and $\rho \in \{0.25,0.50,0.75\}$. The example of LT is at Fig. (ref).
This model kempe2003maximizing is another propagation process similar to LT. At each time step, each active individual moves toward the initiator and independently attempts to activate its $k$-nearest neighbors with the probability of $\rho$. If the individual fails to activate a neighbor, it cannot attempt to activate the same neighbor again. We explore the same sample parameter space as in the LT model.
In this model, there is no `following' relations. At the start of the pre-coordination interval, all individuals start moving to a fixed direction, independently of others in the population. We expect the relative positions of individuals to yield some following relations only by chance.
For each of the above models, we generate a trial of synthetic data consisting of $20$ individuals, and $20$ separate coordination events, for a total of 12,000 time-steps. Each coordination event has pre-coordination and coordination intervals of $200$ time-steps each. Following the coordination interval is another $200$ time steps of a post-coordination before repeating. We generate $100$ trials for each of models. In total, we have 2,700 simulation datasets.
High-resolution GPS collars track 26 individuals of a troop of olive baboons (Papio anubis) living in the wild in Mpala Research Centre, Kenya crofoot2015data,Strandburg-Peshkin1358. The data consists of latitude-longitude location pairs for each individual at one observation per second. We analyze a subset of $16$ individuals whose collars remained functional for a ten day period (419,095 time steps). In addition, in the first two days of baboon tracking, there are four group activities labeling by experts: sleeping, hanging out, coordinated progression, and coordinated non-progression li2016adversarial. We show later that by using only following network density as a feature to perform activity classification, we can get high accurate results of activity prediction.
The movement of a fish school of golden shiners (Notemigonus crysoleucas) are recorded by video in order to study information propagation over the visual fields of fish strandburg2013visual. Each population contains $70$ fish, with $10$ trained, labeled fish who are able to lead the school to feeding sites over $24$ separate coordination events. The task is to correctly identify trained fish by initiator ranking.
We collected daily closing price data for stocks listed in NASDAQ, using Yahoo! Finance.\footnote{http://finance.yahoo.com/} These time series are from January 2000 to January 2016 (4169 time-steps). We remove symbols with a large amount of missing data, leaving a total of $1443$ symbols in our dataset. Our analysis focuses on discovering large, known events and crises in an unsupervised way, and to explore initiators and sectors involved in these coordination events.
For synthetic datasets, we use three evaluation approaches:
We demonstrate the performance of our framework by comparing with previous works on influence and leadership andersson2008reporting,kjargaard2013time,kempe2003maximizing as well as creating the Granger-Causality framework based on the work by Liu et al. liu2012sparse to illustrate the potential of using Granger Causality to infer leaders in time series. These methods can infer only global initiator ranking, while our proposed framework (FLICA) can detect individual coordination events, handles switching initiator, and performs leadership model classification. Therefore, we use the global leadership identification task to compare FLICA's performance with the prior works. We report the best results under varying parameters for competing frameworks. The time complexity of each method is shown in Table (ref).
First, the FLOCK model andersson2008reporting identifies leaders who move toward the norm direction vector of the group and also in the front of the group. Second, LPD kjargaard2013time creates an aggregate `following' network from time-lag features. A node is scored by breadth-first traversal on reversed `following' edges. Visited neighbors' contribution is inverse-proportional to the geodesic distance. For the purposes of our simulation, we use sliding Euclidean distance alignment (e.g. analogous to cross-correlation) because LPD does not scale to the size of our simulations under DTW (see Table (ref)). Finally, for influence maximization (IM), we use the independent cascade model for the $1$-seed selection problem kempe2003maximizing, on the network derived from andersson2008reporting. The network describes the probability of any individual $A$ sharing the same direction as $B$, and in the front of $B$.
For the Granger Causality method, we used the Copula-Granger approach that can be found in liu2012sparse to infer a causal network. Then, we convert the causal network to be a following network by designating $X$ follows $Y$ if the weight of $Y$ Granger causes $X$ is larger than the weight of $X$ Granger causes $Y$.
To make leadership comparison possible, we report the global leadership rank ordered list for each method as follows. First, we create rank order lists for FLICA under PageRank. The FLOCK model, however, does not have the explicit ranking score, so we rank individuals based on decreasing time duration of leadership. Third, LPD assigns individuals with higher scores a higher rank. Finally, since IM uses the probabilistic network of influence, we construct the realization of this influence network. A node influences any node to which it has a directed path in the realized network. We rank individuals based on the expectation of nodes influenced by that node over 1000 realized networks. Lastly, for the Copula-Granger leadership framework, we use PageRank to evaluate the leadership ranking on the following network we created from the causal network.
Typically, real-world datasets are noisy. The high degree of noise can affect results of leadership inference. However, the effects of noise on leadership inference is unclear. Moreover, in our leadership framework, the main parameter is the time window $\omega$. Using the wrong value of time window may affect the results as well. Hence, in this section, we consider the approach to measure the robustness of our framework.
To measure the accuracy of initiator inference, we use a support value of being a leader of factions for each individual. A faction interval of $L$ is defined as a sub-coordinated interval within a coordination event such that $L$ leads a group. Given $\mathcal{F}=\{I_L\}$ is a set of faction intervals where $I_L$ is a faction interval lead by $L$ (The consecutive time interval that $L$ leads the group) and a time window $\omega$, a coordination event $E_k$ is defined to be a combined interval of consecutive faction intervals. Specifically, if a faction interval $I_i$ finishes at time $t'_i$ while $I_j$ starts at time $t_j \leq t'_i+\omega$, then both $I_i$ and $I_j$ factions are in the same coordination event.
Given $\mathcal{E}=\{E_k\}$ is a set of coordination events and $\mathcal{F}_L=\{I_i\}$ is a set of faction intervals lead by $L$, the support value of an individual $L$ leading factions is defined as follows.
The support value, $\mathrm{sup}(L)$, tells us the level of consistency that $L$ happens to initiate its faction for any coordination event. If $\mathrm{sup}(L)\approx 1$, then it means $L$ always initiates factions when coordination events occur. In contrast, if $\mathrm{sup}(L)\approx 0$, then there is a low chance that $L$ initiates any faction.
Moreover, we can calculate a confident value of having $A$'s and $B$'s factions in the same coordination event given that $A$'s faction occurs at the event as follows.
Fig. (ref) shows the toy example of coordination events in the form of density time series of following network. $\mathcal{E}=\{[t_1,t_3],[t_4,t_6],[t_7,t_9]\}$ is a set of coordination events. A set of faction intervals lead by $A$ is $\mathcal{F}_A=\{[t_1,t_2],[t_4,t_5],[t_7,t_8]\}$, a set of faction intervals lead by $B$ is $\mathcal{F}_B=\{(t_2,t_3],(t_5,t_6]\}$, and a set of faction intervals lead by $C$ is $\mathcal{F}_C=\{(t_8,t_9]\}$. The support values of $A,B$ and $C$ are $\mathrm{sup}(A) = 1$, $\mathrm{sup}(B) = 2/3$, and $\mathrm{sup}(C) = 1/3$ respectively. The confident values of having $B$'s faction within a coordination event that has $A$'s faction is $\mathrm{Conf}(B|A)=2/3$. But $\mathrm{Conf}(A|B)=1$ and $\mathrm{Conf}(A|C)=1$.
To measure the robustness of framework w.r.t. two tasks above, we consider two types of noises: position noise and direction noise. For a direction noise, instead of moving to a target direction at degree $D$ compared to $X$-axis, an individual moves toward a direction $D+a$. The direction noise $a$ is drawn randomly from a normal distribution with zero mean and $\gamma$ standard deviation. For position noise, suppose $(x,y)$ is the next position that an individual should move to, with position noise, the actual position that the individual moves is $(x+b_1,y+b_2)$. The position noise $b_1,b_2$ are drawn randomly from a normal distribution with zero mean and $\beta$ standard deviation.
A time window parameter $\omega$ is the main parameter of our leadership framework. we report the performance of framework when the time window is vary from the optimal time window. If the framework is robust, then it should perform well even when the time window value is set significantly different from the optimal value.
In each simulation, we have the label of the true initiator(s). For each of the simulation trials, our method identifies the `initiator' and `rank ordered lists' (see Section (ref)). We set a window size $\omega$ by the TWIN heuristic sulo2010meaningful on the network density, window shift size $\delta = 0.1\omega$, and the $\lambda$ threshold at the mean of the network density time series $\mathrm{d}(t)$.
Table (ref) reports precision on PageRank rank ordered lists over all synthetic model simulations. We compare against previous works--FLOCK andersson2008reporting, IM kempe2003maximizing, LPD kjargaard2013time, and Copula-Granger Causality Inference models liu2012sparse--which produce a single ranking over the entire trial.
The white rows in Table (ref) report precision of leadership identification for a fixed initiator across all coordination events (global leadership). Gray rows report precision of initiator leadership where leaders change between pre-coordination and coordination intervals in the event (DM-S, HM-S), or precision of local leadership where the initiator changes per coordination event (EM). The rows labeled `Top-4' report precision in identifying any of the multiple unordered initiators (CM, INIT-4) or precision for the correct hierarchical order (HM, HM-S).
On the white rows, FLICA is robust across all simulation models, while FLOCK, IM, and LPD perform well other than on INIT-4 simulations (e.g. with multiple initiators). However, in gray rows (“initiator switching”) previous methods fail almost completely since they are unable to detect leadership prior to coordination. When the coordination state is more prevalent than the pre-coordination decision-point, ranking will favor an individual who happens to lead the dynamics in the coordination state (but may not have initiated the state). For Copula-Granger framework, it can infer correct initiators with high accuracy in Dictatorship model, while it fails for the most of models except INIT-4. This indicates that the Copula-Granger approach has a potential to infer leaders even though it is not designed to perform leadership inference.
The row reporting EM results is a special case of precision. Because we know each coordination event has a unique initiator, ranking individuals across all coordination events will fail. Instead, we report precision in identifying the initiator of each coordination event. Since previous work generates only aggregate rankings, precision for these methods are not reported.
We identify the top-$k$ global initiators of the fish school trajectory dataset (see Section (ref)), where we have the labels of `trained' individuals expected to lead the school to feeding sites. Table (ref) reports precision of identifying trained fish as initiators over $24$ trials. The Initiator column is precision of predicting a trained fish as a global initiator. The Top-4 rank column is precision of identifying trained fish as the top-4 ranking individuals. Similar to the simulation models, FLICA performs best overall, again suggesting that dynamic following network representation captures `following' better than other features.
We apply our leadership framework to stock market closing price data of the NASDAQ index. An `initiator' in this context measures the extent that a stock increases or decreases in value before a large group of other stocks (e.g. a coordinated group). We apply the framework without any special consideration to the domain, only to qualitatively validate that we can discover known, large events.
Fig. (ref) shows the network density of the inferred `following' network over time, where we discover coordination events with $\lambda$ threshold at the 75th percentile of the network density time series. Pre-coordination and coordination intervals are shown in red and green, respectively. We find significant economic events such as the 2000 tech collapse, and 9/11. More interestingly, we discover known events which are reflected in the network density signal but not the NASDAQ index. For example, we discover a technical econometric event, where the “TED Spread” (a surrogate of national credit risk) begins fluctuating in July 2007, and a small market failure in August 2011. Matching our intuition, the top-ranked companies in the coordination event associated with the year 2000 collapse are primarily in IT and semiconductors, including eBay and SanDisk in the top 10.
For the sanity check, we provided the results of the comparison between the following network density of NASDAQ stock market and a random walk one in Fig. (ref). We generated random-walk time series from the original NASDAQ closing price time series. Both original and random-walk versions shared the same distribution of difference between time steps, length, and the number of time series.
For each time series of closing price $X$, we inferred the distribution $\mathcal{D}_X$ of the differences between the time steps. We created random-walk time series $\hat{X}$ that starts as the same price as the original time series, then we updated the next value of $\hat{X}$ by normally sampling a different value from $\mathcal{D}_X$. Hence, both $X$ and $\hat{X}$ share the same $\mathcal{D}_X$.
We found that our following network density of NASDAQ is different from the random-walk one (Fig. (ref)). Moreover, random-walk network density does not have any coordination events. This indicates that our network density can tell the difference between random-walk time series and the actual dataset that contains coordination events.
In this section, we demonstrate that our coordination events, which defined by following network density time series, corresponding to coordinated progression activity labeled by experts in baboon dataset (see Section (ref)).
For each time step, a group of baboon has an activity label as either sleeping, hanging out, coordinated progression, or coordinated non-progression. The group of baboons is considered to have a sleeping label when they are at their home tree to sleep. Hanging out activity happens when baboons stay around the same place without moving far away from the group. Coordinated progression is when a group of baboons having a strong coordinated movement to somewhere. Lastly, in coordinated non-progression, a group has a weaker coordinated movement than coordinated progression.
Fig. (ref) shows the distribution of network density for each activity. Sleeping and hanging out activities have low values of network density, which implies that the group rarely has following relations. On the contrary, coordinated progression and coordinated non-progression have high values of network density on average, which is similar to our coordination intervals. This result illustrates that a following network density is informative with respect to the task of activity classification.
In the dataset, there are two days of baboon activity labels. We used the first day data to train a classifier to predict the second day activities as well as using the second day to train a classifier to predict the first day activities. We used Linear discriminant analysis (LDA) as our classifier and used only network density as a feature. We compared our result with Adversarial Sequence Tagging (AST) li2016adversarial, with is the state-of-the-art method that performed activity labeling classification in the same dataset. Our aim is to show that a following network density is informative enough to make a simple classifier performs better than the state-of-the-art classifier method that used 24 features in the group activity classification task.
The classification result is shown in Table (ref). The accuracy results were calculated by the complement of hamming loss the same as li2016adversarial. By using only following network density as a feature, our simple classifier performs better than AST in both days.
Recall, that we proposed several initiator rankings and ranking correlations (Section (ref)). Here, we do leadership model classification on each simulation trial using the proposed features derived from the rank correlations: $\mathrm{corr}_{p}$, $\mathrm{corr}_{v}$, $\mathrm{corr}_{p, pr}$, $\mathrm{corr}_{v, pr}$ and $\mathrm{sup}_{pr}$. A classifier takes these features and produces a leadership model label, one per trial of the simulation model in the evaluation hold-out. We use 10-fold cross validation on Random Forests ho1998random over the 2700 total trials and report mean precision and recall across folds. Table (ref) reports the classification results for each simulation model. We combine some models into a shared label because they share similar characteristics when we project them into our feature spaces. For example, DM, and DM-S models always have high $\mathrm{corr}_{v}$ but low $\mathrm{corr}_{p}$.
Fig. (ref) visualizes sub-spaces of the full feature-space. Fig. (ref) (Top) shows the maximum support ($\mathrm{sup}_{pr}$) over all individuals for this trial vs. the $\mathrm{corr}_{v}$ (the rank correlation between global and local VCH ranking) and $\mathrm{corr}_{p}$. The $\mathrm{sup}_{pr}$ axis (x-axis) describes how `dictatorial' (e.g. consistent) the leadership is across coordination events. DM therefore has high support, while EM (distinct leaders per coordination event) has low $\mathrm{sup}_{pr}$. The $\mathrm{corr}_{v}$ and $\mathrm{corr}_{p}$ axes describe consistency between local and global convex hull rankings. HM has high velocity ranking because leaders accelerate in a consistent sequence, yielding consistent individuals movement outside of the VCH in the previous time step. The random model produces high $\mathrm{corr}_{p}$ because relative positions within the group are somewhat consistent. Therefore, a consistent set of individuals expand the PCH from the previous time step.
Fig. (ref) (Bottom-Right) reports the mean rank correlation between PageRank rank ordering, against PCH and VCH ranking in each coordination event. At the origin (0, 0), ranking from the inferred `following' network is uncorrelated with time series feature rankings in position or velocity. Following our intuition, the Random simulation has the lowest cross-domain feature correlation, while DM and HM have highest correlation between these domains. As the simplest simulations, DM and HM both dictate that leaders will have regular position (e.g. the front of the group), or velocity (accelerating in sequence before others). Simulations such as CM, LT, IC have indirect relationships between relative position and velocity vs. the following network ranking.
A key aspect of our simulation modeling is that we can characterize real datasets according to how they map into these feature-spaces, compared to synthetic models. We compute each rank correlations over high-confidence baboon events, labeled “Baboon” in Fig. (ref), thresholded at the $99$th percentile of density. We observe that within different sub-spaces, the baboon ranking is similar to Random or Linear Threshold, and has low maximum support for global vs. local rank correlation features (e.g. $\mathrm{corr}_{p}$). We see this rank correlation between both cross-domain axes (Fig. (ref) (Bottom-Right)). This suggests that in aggregate, baboon leadership is heterogeneous and context-driven, though overall closer to the Linear Threshold influence model (as biologically expected). This analysis provides a strategy for hypothesis testing and generation on contrasting time-scales and sub-spaces.
In this section, we provided the results of the network density changes when individuals are removed from the datasets, either the high-rank ones or (uniformly) at random.
In the baboon dataset, we used leadership ranking during pre-coordination intervals to choose the top-$k$ rank individuals. In the fish datasets, we used leadership ranking to choose top-$k$ ranked individuals, which are also informed fish. For the randomly chosen individuals, we uniformly and randomly chose $k$ individuals from the population. We repeated the random choice process 100 times and report the average of these results.
Table (ref) shows the average difference of the network density before and after removing $k$ individuals from the baboon dataset. In the 'High-Rank' row, the network density decreases with the removal of high-ranked individuals. In contrast, in the 'Random' row, the network density is largely unaffected by the uniformly random removal of the individuals.
In the fish data, Table (ref) shows the results of the network density difference after removing $k$ individuals. In the 'High-Rank' row, the network density decreases with the removal of high-ranked individuals, albeit less so than in the baboon dataset. In the random case, the network density is still largely unaffected by the uniformly random removal of the individuals.
The results above show that by removing high-rank individuals in both baboon and fish datasets, the network density decreases significantly compared to randomly removed individuals. Moreover, we found that removing high-rank individuals in the baboon dataset resulted in a larger decrease of the network density than in the fish datasets. This suggests that baboons have a stronger following hierarchy than schools of fish.
We conducted the sensitivity analysis based on Section (ref) to demonstrate the robustness of our framework. We used simulation datasets that have the time delay for following relations less than 30 time steps. Hence, the optimal time window $\omega$ is 30 time steps. In the initiator inference, the results of loss values of the initiator-support prediction are shown in Fig. (ref). Each cell in these three sub figures represents a loss value which is the difference between the ground-truth and the predicted value of the initiator support (Eq. (ref)). In general, unsurprisingly, the loss value increases with noise.
Fig. (ref) (below) illustrates that both the position and direction noise affect the prediction performance. In top-left and top-right plots, they show that when we set the time window below the optimal value ($\omega<30$), the loss of support inference is significantly higher than setting the time window above the optimal time window. This suggest us to try to guess the possibly maximum time delay in datasets and avoid setting the time window parameter below this value if the ground truth regarding time delay is not available.
Fig. (ref) shows the loss values of the initiator-confidence prediction. Each value in these three sub figures represents a loss value, which is a difference between the ground-truth and the predicted confidence values. Similar to the support result, higher levels of noise results in higher loss values. Similarly, setting the time window below the optimal value also severely affects the framework performance in confidence prediction.
In the coordination inference task, Fig. (ref) shows the F1 scores of the coordination inference for different levels of noise and time window sizes. Each value in these three sub figures represents the F1 score of the prediction. Similar to the previous results in the initiator inference, higher levels of noise reduce prediction performance. Setting the time window below the optimal value also decreases the prediction performance severely.
In conclusion, when we increase the amount of noise in the datasets, the framework performance decreases. Moreover, we found that if we set the time window parameter below the optimal, it severely affects the framework performance in both initiator and coordination inference tasks. In contrast, when we set the time window above the optimal value, the framework performance drops only slightly. The optimal time window is, then, a value above the possible highest time delay that two individuals can follow each other in the dataset. This suggests that the users of our framework should try to come with an educated guess of the possible values of time delays that are relevant for the application context and set the time window parameter accordingly.
We narrow the gap between the biosociological view of leadership in group decision-making and the computational approaches to leadership inference. The work presented in this paper formalizes a {\bf new computational problem}, namely {\sc Coordination Initiator Inference Problem}\xspace, and proposes the concrete, simple yet powerful, unsupervised general framework as a solution. The framework is capable of (1) identifying events of coordinated group behavior, (2) identifying leaders as initiators of these events, and (3) classifying the type of leadership process at play. We validate the accuracy of our framework in performing all three of these tasks using 2,700 simulated datasets. Since there are no methods for local leadership inference and leadership model classification, we compared our framework with the state-of-the-art methods for global leadership identification. Our method performance is consistently competitive and its abilities go beyond other approaches in all datasets. We further show that the framework can provide insights on real-world data, including data on collective animal movement and the economy. The methodology presented here is general and applicable to a wide variety of domains where coordination across many individuals or entities is observed. Moreover, our framework is highly flexible, and can easily be extended to incorporate other models of leadership or other features used in model classification, depending on the details of the system being analyzed. For reproducibility, we provide our code and simulation datasets at FLICAwebsite.