The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
119,443 characters
Coordination Event Detection and Initiator Identification in Time Series Data
\title{Coordination Event Detection and Initiator Identification in Time Series Data}
\author{Chainarong Amornbunchornvej}
\orcid{0000-0003-3131-0370}
\affiliation{
\institution{University of Illinois at Chicago}
\streetaddress{851 S Morgan St}
\city{Chicago}
\state{IL}
\postcode{60607-7101}
\country{USA}}
\email{[email removed]}
\author{Ivan Brugere}
\affiliation{
\institution{University of Illinois at Chicago}
\streetaddress{851 S Morgan St}
\city{Chicago}
\state{IL}
\postcode{60607-7101}
\country{USA}}
\email{[email removed]}
\author{Ariana Strandburg-Peshkin}
\affiliation{
\institution{Max Planck Institute for Ornithology}
\streetaddress{Am Obstberg 1}
\city{Radolfzell}
\postcode{78315}
\country{Germany}}
\email{[email removed]}
\author{Damien R. Farine}
\affiliation{
\institution{Max Planck Institute for Ornithology}
\streetaddress{Universitätsstrasse 10}
\city{Konstanz}
\postcode{78464}
\country{Germany}}
\email{[email removed]}
\author{Margaret C. Crofoot}
\affiliation{
\institution{University of California, Davis}
\streetaddress{1 Shields Ave}
\city{Davis}
\state{CA}
\postcode{95616}
\country{USA}}
\email{[email removed]}
\author{Tanya Y. Berger-Wolf}\thanks{This work was supported in part by the NSF grants III-1514126 (Berger-Wolf, Crofoot), III-1514174 (Crofoot), IOS-1250895 (Crofoot), SMA-1620391 (Crofoot) , CNS-1248080 (Berger-Wolf), and the David \& Lucile Packard Foundation 2016-65130 (Crofoot). }
\affiliation{
\institution{University of Illinois at Chicago}
\streetaddress{851 S Morgan St}
\city{Chicago}
\state{IL}
\postcode{60607-7101}
\country{USA}}
\email{[email removed]}
\begin{abstract} \small\baselineskip=9pt
Behavior initiation is a form of leadership and is an important aspect of social organization that affects the processes of group formation, dynamics, and decision-making in human societies and other social animal species. In this work, we formalize the {\sc Coordination Initiator Inference Problem}\xspace and propose a simple yet powerful framework for extracting periods of coordinated activity and determining individuals who initiated this coordination,
based solely on the activity of individuals within a group during those periods.
The proposed approach, given arbitrary individual time series, automatically (1) identifies times of coordinated group activity, (2) determines the identities of initiators of those activities, and (3) classifies the likely mechanism by which the group coordination occurred, all of which are novel computational tasks. We demonstrate our framework on both simulated and real-world data: trajectories tracking of animals as well as stock market data. Our method is competitive with existing global leadership inference methods but provides the first approaches for local leadership and coordination mechanism classification. Our results are consistent with ground-truthed biological data and the framework finds many known events in financial data which are not otherwise reflected in the aggregate NASDAQ index. Our method is easily generalizable to any coordinated time-series data from interacting entities.
\end{abstract}
\begin{CCSXML}
<ccs2012>
<concept>
<concept_id>10002951.10003227.10003236</concept_id>
<concept_desc>Information systems~Spatial-temporal systems</concept_desc>
<concept_significance>300</concept_significance>
</concept>
<concept>
<concept_id>10002951.10003227.10003351</concept_id>
<concept_desc>Information systems~Data mining</concept_desc>
<concept_significance>300</concept_significance>
</concept>
<concept>
<concept_id>10010405.10010455.10010461</concept_id>
<concept_desc>Applied computing~Sociology</concept_desc>
<concept_significance>300</concept_significance>
</concept>
<concept>
<concept_id>10010405.10010455.10010460</concept_id>
<concept_desc>Applied computing~Economics</concept_desc>
<concept_significance>200</concept_significance>
</concept>
</ccs2012>
\end{CCSXML}
\ccsdesc[300]{Information systems~Spatial-temporal systems}
\ccsdesc[300]{Information systems~Data mining}
\ccsdesc[300]{Applied computing~Sociology}
\ccsdesc[200]{Applied computing~Economics}
\keywords{Leadership, Time series, Coordination, Influence}
\maketitle
\section{Introduction}
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 \textit{after} the group has already agreed to follow~\cite{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.
\begin{framed}
\noindent {{\sc Coordination Initiator Inference Problem}\xspace:} {An agreement of a group to follow a common purpose is manifested by its coalescence into a \textit{coordinated} behavior. The process of initiating this behavior and the period of decision-making by the group members necessarily precedes the coordinated behavior. {\bf Given time series of group members' behavior, the goal is to find these periods of decision-making and identify the initiating individual, if one exists.}}
\end{framed}
{Initiating} a group's behavior is a form of leadership~\cite{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~\cite{LeadershipBook}.
\begin{figure}[ht!]
\centering
\includegraphics[width=1\columnwidth]{FIG/DyNetLeadership_edit}
\caption{A high-level overview of the proposed framework}
\label{fig:processingSteps}
\end{figure}
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.
\subsection{Related work}
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~\cite{Conradt:2003aa}. Leadership
plays a key role in organizing the collective (i.e. group) behaviors of social organisms ranging from humans ~\cite{Dyer:2009aa}
to hymenoptera~\cite{Weinstein:1997}. It potentiates complex patterns of cooperation and conflict
(e.g.,
lions~\cite{Heinsohn1260},
hyaenas~\cite{Boydston:2001},
meerkat~\cite{Mares3989}, chimpanzees~\cite{Gilby:2015}, humans~\cite{Glowacki:2015}),
organizes group movements
~\cite{Couzin:2005aa,Dyer:2009aa}, and may prevent free-riding~\cite{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~\cite{WilsonSocbio,Stueckle2008,Couzin:2005aa,Petit2010635}. Biological studies showed that leaders may be context-specific~\cite{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~\cite{
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~\cite{WilsonSocbio}), positions in
location-based social networks \cite{PhamICDE2016}, rule-based models\cite{Song2014crowdmodel}, physical trajectory and association patterns \cite{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 \cite{goyal2008discovering,
Bakshy:2011:EIQ:1935826.1935845}. Other domain-specific methods infer leadership from implicit pairwise dyadic dominance or leader-follower interactions~\cite{andersson2008reporting, PhamICDE2016,kjargaard2013time}. Some methods define an explicit network over the dyadic interactions or use a known network topology~\cite{Sun2011} and use network measures, such as PageRank and HITS, or cascade size to identify leaders~\cite{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~\cite{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~\cite{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~\cite{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~\cite{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.
\subsection{Our contributions}
In our previous version of this paper in ~\cite{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 \textbf{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:
\begin{list}{$\bullet$}
{ \setlength{\itemsep}{-.1ex} \setlength{\parsep}{0ex}
\setlength{\topsep}{0ex} \setlength{\partopsep}{0ex}
\setlength{\leftmargin}{.8em} \setlength{\labelwidth}{1em}
\setlength{\labelsep}{0.5em} }
\item {\bf Detecting coordinated activity events:} discovering coordination intervals and decision-making periods leading to that coordination;
\item {\bf Identifying initiators:} identifying the initiators of this coordinated behavior, that is, the individuals who succeeded in leading the group to coordination, specifically locally to each coordination instance; and
\item {\bf Classifying the group coordination model:} characterizing the type of the group's transition behavior to coordination according to interpretable, dynamic models.
\end{list}
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~\cite{li2016adversarial}.
\subsection{Influence Maximization vs. Coordination Initiator Inference Problem}
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.
\begin{list}{$\bullet$}
{ \setlength{\itemsep}{-.1ex} \setlength{\parsep}{0ex}
\setlength{\topsep}{0ex} \setlength{\partopsep}{0ex}
\setlength{\leftmargin}{.8em} \setlength{\labelwidth}{1em}
\setlength{\labelsep}{0.5em} }
\item {\bf Coordination Model:} In Influence Maximization, the majority of papers focus on Linear Threshold and Independent Cascade models as main coordination mechanisms. However, there are other models that can be represented as a coordination mechanism, such as Dictatorship and Hierarchy models, as well as non-network based models at all. Our new problem formulation, {\sc Coordination Initiator Inference Problem}\xspace, generalizes to all types of models that can be represented as a coordination mechanism. To recognize difference types of coordination mechanisms, we also provide the model classification approach to classify these coordination models based on some proposed features.
\item {\bf Coordinated Activity:} Influence Maximization focuses on only one kind of state changing, which is an information spreading event. In a coordinated activity, any state that the group coalesces to, a posteriori, is a coordinated state, and it may change from one time to another. Coordinated activity can represent multiple types of coalesced states over multiple time points. For example, a coordinated movement of animals to a feeding site is considered to be a coordinated activity for that group, but so is sudden jumping up and down in agitation, or all looking in the same direction, or all falling sick. And the coordinated movement can be different and look different in the morning versus in the evening. In {\sc Coordination Initiator Inference Problem}\xspace, the problem focuses on not only which individuals initiate coordinated activities, but also {\bf when} coordinated activities occur, without the explicit prescription of the type of coordinated activity. To analyze coordinated activities in time series, we provide a framework to detect coordination intervals as well as initiators of these coordination events.
\item {\bf Coordination Based on Context:} The original Influence Maximization assumes that there is only one coordination event of information spreading. However, in reality, information spreading or coordination events can occur many times. For instance, within a day, a group of animals can have many coordinated movement events to many places. Our work here aims to infer the multiple coordination events, which might have different initiators.
\end{list}
\section{Problem formalization}
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.''
\begin{figure}[ht!]
\centering
\includegraphics[width=.75\columnwidth]{FIG/FollRelation}
\caption{(Left) The example of time series $U$ follows $Q$. (Right) the following network w.r.t. $U$ follows $Q$ relation.}
\label{fig:FollRelation}
\end{figure}
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{fig:FollRelation}).'' Formally:
\begin{definition}[{\sc following relation}]
\label{followRDef}
Let $U = (\vec{u}_1,\dots,\vec{u}_t,\dots)$ and $W = (\vec{w}_1,\dots,\vec{w}_t,\dots)$ be $m$-dimensional, arbitrary-length time series. If for all $ t \in \mathbb{N}$, there is a fixed time delay $\Delta t \in \mathbb{Z^+} \cup\{0\}$ such that $\vec{w}_t=\vec{u}_{t+\Delta t}$
, then $U$ follows $W$ denoted as $W \preceq U$. We denote $W \prec U$ if $\Delta t>0$.
\end{definition}
\begin{lemma}
\label{EquivR}
Let $U$ and $W$ be time series such that $W \preceq U$ and $U \preceq W$, then $U$ and $W$ are equivalent time series denoted $U \equiv W$.
\end{lemma}
\begin{proof}
There are two cases when both $W \preceq U$ and $U \preceq W$. First, $W = U$ and $U = W$ (that is, $\Delta t = 0$ in both following relations). Clearly, $W \equiv U$.
Second, $W \prec U$ with $\Delta t_w > 0$ and $U \prec W$ with $\Delta t_u > 0$. Then, by definition, $\vec{w}_t=\vec{u}_{t+\Delta t_w}$ and $\vec{u}_t=\vec{w}_{t+\Delta t_u}$. Therefore, $\vec{w}_t=\vec{w}_{t+\Delta t_w+\Delta t_u}$. Thus, if $W \preceq U$ and $U \preceq W$ then $W \preceq W$ (and similarly $U \preceq U$). Thus, the two time series are identical periodic with a different starting point and therefore equivalent.
\end{proof}
In periodic time series, such as a sine wave, we use Lemma~\ref{EquivR}. 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{fig:sineTS}, $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{EquivR} above, $U \equiv W$.
\begin{figure}[ht!]
\centering
\includegraphics[width=.75\columnwidth]{FIG/sineTS}
\caption{$U$ and $W$ are sine waves that have the same frequency but different phase. $U$ follows $W$ with time delay $\Delta t_{W \prec U}$ and $W$ follows $U$ with time delay $\Delta t_{U \prec W}$.}
\label{fig:sineTS}
\end{figure}
\begin{lemma}
The {\sc following relation} is a partial order over time series~\cite{partialOrder}.
\end{lemma}
\begin{proof}
Antisymmetry: if $W\preceq U$ and $U\preceq W$, then $W \equiv U$ by Lemma~\ref{EquivR}.
The {\sc following relation} is also trivially reflexive and transitive, which, by definition is a partial order.
\end{proof}
Next, {\sc coordination}, or intuitively ``all individuals performing the same sequence of actions, at possibly varying delays (Fig.~\ref{fig:CoorInterval}),'' is formally defined as:
\begin{definition}[{\sc Coordination}]
\label{CoorDef}
Given a set of $m$-dimensional time series $\mathcal{U} = \{U_1, \dots, U_n\}$. The set $\mathcal{U}$ is {\em coordinated} at time $t$ if for every ${n \choose 2}$ pairs $U_i, U_j \in \mathcal{U}$, either $U_i \prec U_j$ or $U_j \prec U_i$.
The {\em coordination interval} is the maximal contiguous time interval $[t_1, t_2]$ such that $\mathcal{U}$ is coordinated for every $t \in [t_1, t_2]$.
\end{definition}
\begin{figure}[ht!]
\centering
\includegraphics[width=.75\columnwidth]{FIG/CoorInterval}
\caption{(Left) the example of coordination interval in time series where $Q\prec U\prec V \prec W$. (Right) the following network w.r.t. these following relations. In this example, $Q$ is an initiator.}
\label{fig:CoorInterval}
\end{figure}
Finally, the {\sc initiator} is intuitively ``an individual who first performs a sequence of actions, and all other individuals follow,'' formally defined as:
\begin{definition}[{\sc Initiator}]
\label{InitiatorDef}
Let $\mathcal{U} = \{U_1, \dots, U_n\}$ be a coordinated set of $m$-dimensional time series within some coordination interval $[t_1, t_2]$. Then the time series $L \in \mathcal{U}$ is the {\em initiator} time series for the coordination interval if for each time series $U \in \mathcal{U} \setminus \{L\}$, $L \prec U$.
\end{definition}
In Fig.~\ref{fig:CoorInterval}, $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:
\begin{problem}[h!]
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\Input{Set $\mathcal{U} = \{U_1, U_2, \dots, U_n\}$ of time series.}
\Output{A coordination interval $[t_1, t_2]$ and the initiator time series $L\in \mathcal{U}$ that initiated the coordination.}
\caption{{{\sc Coordination Initiator Inference Problem}\xspace}}
\label{initCoProb}
\end{problem}
\subsection{Useful observations}
\label{sec:usefulobs}
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$.
\begin{definition}[{\sc Following network}]
\label{followNetDef}
Let $\mathcal{U} = \{U_1, \dots, U_n\}$ be a set of time series. The {\em following network} $G = (V,E)$ is defined as a directed graph where the set of nodes $V$ has a one-to-one correspondence to the set of time series $\mathcal{U}$, and each edge in $E$ represents a {\sc following relation} between two time series: $\forall U_i, U_j \in \mathcal{U}$ the edge $e_{i,j} \in E$ if $U_j \prec U_i$.
\end{definition}
Recall that PageRank~\cite{PageRank_Brin1998107} score, $\pi_i$, of a node $i$ in a network $G$ is defined as follows:
\begin{equation}
\pi_i=d\sum_{k \in \mathcal{N}^{in}_i} e_{k,i}\pi_k/| \mathcal{N}^{out}_k|+(1-d)
\label{eq:PReq}
\end{equation}
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$.
\begin{lemma}
\label{PageRankLemma}
Let $G=(V,E)$ be a following network of time series set $\mathcal{U} = \{U_1, \dots, U_n\}$. If $U_i \preceq U_j$ then $\pi_i \geq \pi_j$.
\end{lemma}
\begin{proof}
By transitivity, if $U_j$ follows $U_i$ then the followers of $U_j$ are also the followers of $U_i$. Thus, since $\forall k \in \mathcal{N}_j$, $U_j \preceq U_k$ and $U_i \preceq U_j$, then $\mathcal{N}^{in}_j \subseteq \mathcal{N}^{in}_i$. Hence, $\pi_i - \pi_j = d\sum_{k \in \mathcal{N}^{in}_i \setminus \mathcal{N}^{in}_j} e_{k,i}\pi_k/| \mathcal{N}^{out}_k| \geq 0$.
\end{proof}
As a corollary of Lemma~\ref{PageRankLemma}, 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{PageRankLemma} allows us to infer the order of following among the time series within the coordination period, as defined by the PageRank values.
\subsection{Following relation with noise}
\begin{figure}[ht!]
\centering
\includegraphics[width=.75\columnwidth]{FIG/RelaxTransv}
\caption{(Top-left) A time series $Q$, (bottom-left) a time series $U$, and (top-right) a time series $V$. In this example, $U$ partially follows $Q$, $V$ partially follows $U$ but $V$ does not follow $Q$. The following network of these time series is at the bottom-right of the figure.)}
\label{fig:RelaxTransv}
\end{figure}
In real situations, Def.~\ref{followRDef} requires the exact match, which rarely happens. Therefore, we provide relaxation of following relation to deal with noise in realistic situations below.
\begin{definition}[$\sigma$-following relation]
\label{def:sigFollRe}
Let $\mathcal{U}$ be a set of time series and $\mathrm{sim}: \mathcal{U}\times \mathcal{U} \to [0,1]$ be some similarity measure between two time series. For any pair of time series $U_i,U_j \in \mathcal{U}$, let $\Delta t_{max} =\mathrm{min} \mathop{\mathrm{argmax}}\limits_{\Delta t \in \mathbb{Z}} \mathrm{sim}(U_{i,1},U_{j,1+\Delta t})$ where $U_{i,t} \in \mathcal{U}$ represents a time series $U_i$ starting at time $t$, and let $\mathrm{sim}_{max}(U_i,U_j)= \mathrm{sim}(U_{i,1},U_{j,1+\Delta t_{max}})$. Then, for a threshold $\sigma \in (0,1]$, if $ \mathrm{sim}_{max}(U_i,U_j) \geq \sigma$, then we have:
\begin{list}{$\bullet$}
{ \setlength{\itemsep}{-.1ex} \setlength{\parsep}{0ex}
\setlength{\topsep}{0ex} \setlength{\partopsep}{0ex}
\setlength{\leftmargin}{.8em} \setlength{\labelwidth}{1em}
\setlength{\labelsep}{0.5em} }
\item if $\Delta t_{max} >0$ , then ${U_i \prec_{\sigma} U_j}$,
\item if $\Delta t_{max} <0$ , then ${U_j \prec_{\sigma} U_i}$,
\item if either $\Delta t_{max} = 0$ or ${U_i \prec_{\sigma} U_j}$ and ${U_j \prec_{\sigma} U_i}$, then ${U_i \equiv_{\sigma} U_j}$.
\end{list}
\label{SigmaFollwDef}
\end{definition}
The difference between a following relation in Def.~\ref{followRDef} and Def.~\ref{def:sigFollRe} 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{fig:RelaxTransv} 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.
\begin{definition}[{\sc $\sigma$-Coordinated set}]
\label{SigCoorDef}
Given a set of $m$-dimensional time series $\mathcal{U} = \{U_1, \dots, U_n\}$ and a similarity threshold $\sigma \in (0,1]$. The set $\mathcal{U}$ is {\em $\sigma$-coordinated} at time $t$ if for every ${n \choose 2}$ pairs $U_i, U_j \in \mathcal{U}$, either ${U_i \prec_{\sigma} U_j}$ or ${U_j \prec_{\sigma} U_i}$.
\end{definition}
\begin{definition}[{\sc $\sigma$-Coordination interval}]
\label{SigCoorIntvDef}
The {\em $\sigma$-coordination interval} is the maximal contiguous time interval $[t_1, t_2]$ such that $\mathcal{U}$ is coordinated for every $t \in [t_1, t_2]$.
\end{definition}
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.
\section{Methods}
\label{sec:method}
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 \textit{exact} {\sc following relation}, and \textit{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{fig:processingSteps} 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.
\begin{figure}[ht]
\centering
\subfigure{\label{fig:baboon-exbottom}\includegraphics[width=0.75\columnwidth]{FIG/BaboonAug12Result-02-12-16-Plot}}
\subfigure[t=50]{\label{fig:baboon-exa}\includegraphics[width=0.32\columnwidth]{FIG/Figure0050n}}
\subfigure[t=100]{\label{fig:baboon-exb}\includegraphics[width=0.32\columnwidth]{FIG/Figure0100n}}
\subfigure[t=250]{\label{fig:baboon-exc}\includegraphics[width=0.32\columnwidth]{FIG/Figure0250n}}
\caption{PageRank (top) and density (middle) of the `following' network over time for an event of baboons' movement which initiates by ID3. (Bottom) The locations of individuals over three different time steps ($t=50,100,250$), with the `following' network, and PageRank indicated by node size.}
\label{fig:BaboonRankOrder}
\end{figure}
\subsection{A working example}
\label{subsec:working}
Fig.~\ref{fig:BaboonRankOrder} presents a key example and a brief introduction to our framework, on real GPS trajectory data of olive baboons (\emph{Papio anubis}). Fig.~\ref{fig:baboon-exa}-\ref{fig:baboon-exb} show the leadership of movement of the group by baboon ID3 (Black). Fig.~\ref{fig:baboon-exc} 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 \emph{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{subsec:FollNet}, the construction of the following network in Section~\ref{subsec:DyNet}, identification of the coordination interval and the preceding decision-making period in Section~\ref{sec:CoorInterval}, the identification of the initiator in Section~\ref{sec:RankComp} and the details of model and parameter choices at each step.
\subsection{Following relation inference}
\label{subsec:FollNet}
\begin{figure}[ht!]
\centering
\includegraphics[width=.9\columnwidth]{FIG/UfollQ}
\caption{(Left) Toy time series showing $U$ following $Q$ with a time delay $\Delta t=3$. (Right) the optimal warping path (yellow boxes) on the $\mathrm{DTW}$ dynamic programming matrix, shifting $U$ backward in time onto $Q$.}
\label{fig:FollReCorr}
\end{figure}
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{followRDef} 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}$) \cite{Sakoe1978} to measure whether $U$ follows $Q$. DTW is shown to perform better than several other methods in inferring following relation in time series~\cite{kjargaard2013time} and it is tolerant to noise~\cite{doi:10.1137/1.9781611974010.33}. Fig.~\ref{fig:FollReCorr} (Left) shows two time series, where time-shifting $Q$ ahead in time produces a better match to $U$, illustrated in the \emph{warping path} in Fig.~\ref{fig:FollReCorr} (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:
\begin{equation}
\mathrm{s}(P_{U,Q})=\frac{\sum_{(i,j) \in P_{U,Q}}\mathrm{sign}(j-i)}{|P_{U,Q}|}
\label{eq:traCorr}
\end{equation}
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$ \emph{follows} $U$, otherwise, $U$ \emph{follows} $Q$. In Fig.~\ref{fig:FollReCorr}, $\mathrm{s}(P_{U,Q}) \approx -3$.
\subsection{Dynamic following network inference}
\label{subsec:DyNet}
As shown in Section~\ref{subsec:working}, 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 \cite{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}
\begin{alprocedure}[ht!]
\caption{\small CreateDyFollowingNetwork}
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
\Input{A set of time series $\mathcal{D}$, a time window $\omega$, and a window shift $\delta$}
\Output{An $n\times n \times t^*$ adjacency matrix $E^*$.}
\BlankLine
{\small
$K \leftarrow (t^* - \omega)/ \delta$ \;
\For{$i\leftarrow 1$ \KwTo $K$}{
\textcolor{blue}{\tcc*[h]{current time interval} } \\ $w(i)=[(i-1)\times \delta,(i-1)\times \delta + \omega]$ \;
\textcolor{blue}{\tcc*[h]{SubTimeSeries($\mathcal{D},w(i)$) returns all sub time series in $\mathcal{D}$ within the interval $w(i)$}}
$\mathcal{Q}_i \leftarrow$SubTimeSeries($\mathcal{D},w(i)$)\;
$E\leftarrow$CreateFollowingNetwork($\mathcal{Q}_i$) \;
\textcolor{blue}{\tcc*[h]{Set all edges within the time interval $[(i-1)\times\delta,i\times\delta]$ to be similar}}
$E^*_{ t \in [(i-1)\times\delta,i\times\delta]}\leftarrow E$ \;
}
$\mathcal{Q} \leftarrow$SubTimeSeries($\mathcal{D},[K\times\delta,t^*]$)\;
$E\leftarrow$CreateFollowingNetwork($\mathcal{Q}$) \;
$E^*_{ t \in [K\times\delta,t^*]}\leftarrow E$ \;
}
\label{algo:CreateDyFollowingNetwork3}
\end{alprocedure}\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{followNetDef}. 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{eq:traCorr}, 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{algo:CreateDyFollowingNetwork3}.
\subsection{Coordination intervals detection}
\label{sec:CoorInterval}
\begin{figure}[ht!]
\centering
\includegraphics[width=.55\columnwidth]{FIG/NetDensDBScan_new}
\caption{A \emph{coordination event} is a pair of intervals. We define the \emph{pre-coordination interval} and \emph{coordination interval} using threshold $\lambda$ on the network density time series.}
\label{fig:CoorEvent}
\end{figure}
\textit{Network density} of the following network serves as the measure of the extent of coordination over all time series pairs (by Def.~\ref{CoorDef}, during the coordination interval {\em every} pair has a following relation.) We can use this observation to identify times of \textit{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 \emph{all} $t \in [t_i,t_j]$. The \textit{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 \textit{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{fig:CoorEvent} illustrates the definition of a \emph{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$).
\subsection{Ranking comparison}
\label{sec:RankComp}
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~\cite{PageRank_Brin1998107}, velocity convex hull (VCH), and position convex hull (PCH). Recall, that by Lemma~\ref{PageRankLemma}, 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 \cite{Dyer:2009aa,Stueckle2008}. PCH measures how often an individual moves to an area before others. For example, in a flock model~\cite{andersson2008reporting}, a leader is positioned at the front of the group's trajectory.
\subsubsection{PageRank}
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 \emph{following} relations between nodes, PageRank measures `following' \emph{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{eq:PReq} 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.
\subsubsection{Velocity Convex Hull}
In the next two sections, the $s$-energy work by Chazelle~\cite{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).}
\begin{equation}
\mathrm{VCH}(\mathbb{V}, i, t)=\left\{
\begin{array}{@{}ll@{}}
1, & \mathbb{V}_{i,t} > \mathrm{max}(\mathbb{V}_{*,t-1}) \\
-1, & \mathbb{V}_{i,t} < \mathrm{min}(\mathbb{V}_{*,t-1}) \\
0, & \text{otherwise}
\end{array}\right.
\label{eq:velConvx}
\end{equation}
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})$.
\subsubsection{Position Convex Hull}
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$:
\begin{equation}
\mathrm{PCH}(D,i,t)=
\begin{cases*}
1, & $\neg\mathrm{IN}(\mathcal{D}_{i,*,t},H_{t-1}), \measuredangle(\vec{v}_{i,t}, \vec{v}_{t}) \leq 90^{\circ}$\\
-1, & $\neg\mathrm{IN}(\mathcal{D}_{i,*,t},H_{t-1}), \measuredangle(\vec{v}_{i,t}, \vec{v}_{t}) > 90^{\circ}$\\
0, & otherwise
\end{cases*}
\label{eq:posConvx}
\end{equation}
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})$.
\subsection{Leadership model features}
\label{subsec:features-rank}
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}$):
\begin{equation}
\mathrm{sup_{\bullet}}(i)= \frac{\left |{\{\forall I\in C \: (i, 1) \in R_{\bullet, I}\}}\right | }{|C|}
\label{eq:LeaderSup}
\end{equation}
We use the Kendall rank correlation coefficient $\tau()$ ~\cite{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{eq:LeaderglobalCorr}. For example, $\mathrm{corr}_{v}$ compares local and global velocity-convex-hull-rank orders.
\begin{equation}
\mathrm{corr}_{\bullet}=\frac{\sum_{I \in C} \tau(\hat{R}_{\bullet}, R_{\bullet, I})}{|C|}
\label{eq:LeaderglobalCorr}
\end{equation}
Similarly, we compute the mean Kendall correlation between local rankings associated with different measures (e.g. VCH, PCH) by Eq.~\ref{eq:LeaderPairwiseCorr}.
\begin{equation}
\mathrm{corr}_{\bullet, \bullet}=\frac{\sum_{I \in C} \tau(R_{\bullet, I}, R_{\bullet, I})}{|C|}
\label{eq:LeaderPairwiseCorr}
\end{equation}
$\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.
\subsection{Local vs. Global Matching}
\label{subsubsec:local}
\begin{figure}
\centering
\subfigure[Pattern order alignment]{\label{fig:sparse-exA}\includegraphics[width=.48\columnwidth]{FIG/DTWGlobalvsLocal_edit_a}}
\subfigure[Global shift alignment]{\label{fig:sparse-exB}\includegraphics[width=.48\columnwidth]{FIG/DTWGlobalvsLocal_edit_b}}
\caption{Dynamic Time Warping global vs. local example}
\label{fig:globalvlocal}
\end{figure}
Our proposed framework uses local alignment on time series subsequences, rather than global alignment on the full time series. Fig.~\ref{fig:globalvlocal} presents a motivation for this choice. Suppose we intend to match \emph{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{fig:sparse-exA}, 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{fig:sparse-exB} 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.
\section{Experimental setup}
We evaluate our framework on eight synthetic movement trajectory models and three real datasets.
\subsection{Simulation models}
\subsubsection{Dictatorship model (DM)}
\begin{figure}[ht!]
\centering
\includegraphics[width=0.60\columnwidth]{FIG/DMHMpic}
\caption{Examples of individual movements from Dictatorship and Hierarchical model. Nodes represent individual positions and arrows represent directions of individual's movement. (Left) in Dictatorship model, everyone follows a leader $L$, while there is a hierarchy to follow for each individuals in Hierarchical model (right). }
\label{fig:DMHMpic}
\end{figure}
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{fig:DMHMpic} (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{fig:InitDypic} shows an example of following-network-density time series of DM-S.
\begin{figure}[ht!]
\centering
\includegraphics[width=0.7\columnwidth]{FIG/InitDypic}
\caption{An example of following-network-density time series of Switching Dictatorship model . There are two coordination events where individual $A$ leads a group in both pre-coordination intervals while $B$ leads a group during coordination intervals.}
\label{fig:InitDypic}
\end{figure}
\subsubsection{Hierarchical model (HM)}
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{fig:DMHMpic} (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.
\begin{figure}[ht!]
\centering
\includegraphics[width=0.7\columnwidth]{FIG/EMpic}
\caption{An example of following-network-density time series of Event-based model. There are two coordination events where individual $A$ leads a group in the first coordination event while $B$ leads a group during the second coordination event.}
\label{fig:EMpic}
\end{figure}
\subsubsection{Event-based model (EM)}
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{fig:EMpic} shows an example of following-network-density time series of EM.
\begin{figure}[ht!]
\centering
\includegraphics[width=0.7\columnwidth]{FIG/Initpic}
\caption{Examples of individual movements from Initiator model. Nodes represent individual positions and arrows represent directions of individual's movement. (Left) during a pre-coordination interval, everyone follows a leader $L$, while, during a coordination interval, everyone knows the direction and moves to the destination directly without following a leader (right). }
\label{fig:Initpic}
\end{figure}
\subsubsection{Initiator model (INIT-k)}
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{fig:Initpic}. We run simulations for INIT-1 and INIT-4 initiator models.
\begin{figure}[ht!]
\centering
\includegraphics[width=0.7\columnwidth]{FIG/CMpic}
\caption{Examples of individual movements from Crowd model. Nodes represent individual positions and arrows represent directions of individual's movement. (Left) at time $t$, everyone follows some directions except informed individuals ($T$ nodes) which moves directly to a target. Then, at time $t+l$ (right), the group's direction, which is the average of individual's directions, gradually changes toward the target. }
\label{fig:CMpic}
\end{figure}
\subsubsection{Crowd model (CM)}
This model~\cite{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{fig:CMpic}.
\begin{figure}[ht!]
\centering
\includegraphics[width=0.7\columnwidth]{FIG/LTpic}
\caption{Examples of individual movements from Linear Threshold model. Nodes represent individual positions and arrows represent directions of individual's movement. (Left) at time $t$, only active individuals (orange color) move toward an initiator $L$. Suppose $k=3$ and $\rho=0.50$, at time $t$, an inactive individual $A$ has two active individuals $F_1,F_2$ and $L$ as its neighbors. Since 66\% of $A$'s neighbors are activated, then, at time $t+1$ (right), $A$ is active and start moving toward $L$. }
\label{fig:LTpic}
\end{figure}
\subsubsection{Linear Threshold model (LT)}
This model~\cite{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{fig:LTpic}.
\subsubsection{Independent Cascade model (IC)}
This model~\cite{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.
\subsubsection{Random 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.
\subsection{Synthetic trajectory simulation}
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.
\subsection{Real datasets}
\subsubsection{Baboon trajectories}
\label{subsubsec:baboon}
High-resolution GPS collars track 26 individuals of a troop of olive baboons (\emph{Papio anubis}) living in the wild in Mpala Research Centre, Kenya \cite{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~\cite{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.
\subsubsection{Fish schools trajectories}
\label{subsubsec:fish}
The movement of a fish school of golden shiners (\emph{Notemigonus crysoleucas}) are recorded by video in order to study information propagation over the visual fields of fish \cite{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.
\subsubsection{Stock closing-price time series}
\label{subsubsec:stocks}
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.
\subsection{Evaluation}
\label{EvalSec}
For synthetic datasets, we use three evaluation approaches:
\begin{list}{$\bullet$}
{ \setlength{\itemsep}{-.1ex} \setlength{\parsep}{0ex}
\setlength{\topsep}{0ex} \setlength{\partopsep}{0ex}
\setlength{\leftmargin}{.8em} \setlength{\labelwidth}{1em}
\setlength{\labelsep}{0.5em} }
\item {\bf Global leadership}: For each method, we extract network and/or rank statistics over the entire time series, and report only a single aggregate initiator ranking. We compare the known ground truth ranking (used to generate the data) against the ranking of each method, reporting precision. We measure precision of identifying the true initiator, on DM, LT, IC, and INIT-1 models. For the HM model, we compare the \textit{exact} top-4 ranking against the ground truth (order matters); The evaluation is the same for CM and INIT-4 models, except the \textit{exact} top-4 ranking constraint is relaxed (i.e. we compare top-4 \textit{sets}).
\item {\bf Local leadership}: For evaluation data in this case, we use the ground truth ranking for each local coordination event, and the time intervals of each event. We report average precision over each discovered pre-coordination interval. We evaluate the EM model using this approach. We report only the FLICA result, since it is the only method capable of producing local ranking.
\item {\bf Initiator leadership}: For each coordination event, we measure the initiator of coordination event before coordination occurs (e.g. in the pre-coordination interval). This individual may not be highly ranked after coordination (see Fig.~\ref{fig:BaboonRankOrder}). We report the precision of global leadership considering only the pre-coordination intervals. Since only FLICA identifies pre-coordination intervals, we compare against other methods' global leadership. This evaluation demonstrates that global leadership is distinct from coordination initiation. We evaluate DM-S and HM-S models using this approach.
\end{list}
\subsection{Compared leadership methods}
\begin{table}[h]
\caption{Time complexities of leadership inference methods where $n$ is a number of time series, $\omega$ is a time window, and $t^*$ is a length of time series. }
\label{MedCompTB}
\begin{center}
\begin{tabular}{ | c | c | c |}
\hline
{\small Method }& {\small Input } & {\small Time complexity }\\ \hline
{\small FLICA }& {\small Time series } & {\small $\mathcal{O}(n^2 \times t^* \times \omega )$ }\\ \hline
{\small FLOCK \cite{andersson2008reporting}} & {\small Trajectory } & {\small $\mathcal{O}(n^2 \times t^* )$ }\\ \hline
{\small LPD \cite{kjargaard2013time}} & {\small Time series } & { $\mathcal{O}(n^2 \times t^* \times \omega^3)$ }\\ \hline
{\small IM \cite{kempe2003maximizing}}& {\small Network } & {\small $\mathcal{O}(n^2 \times t^* )$ }\\ \hline
{\small Copula-Granger \cite{liu2012sparse}}& {\small Time series } & {\small $\mathcal{O}(n \times (\omega\times t^* )^2)$ }\\ \hline
\end{tabular}
\end{center}
\end{table}
We demonstrate the performance of our framework by comparing with previous works on influence and leadership \cite{andersson2008reporting,kjargaard2013time,kempe2003maximizing} as well as creating the Granger-Causality framework based on the work by Liu et al.~\cite{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{MedCompTB}.
First, the FLOCK model \cite{andersson2008reporting} identifies leaders who move toward the norm direction vector of the group and also in the front of the group. Second, LPD \cite{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{MedCompTB}). Finally, for influence maximization (IM), we use the independent cascade model for the $1$-seed selection problem \cite{kempe2003maximizing}, on the network derived from \cite{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 \cite{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.
\subsection{Sensitivity analysis}
\label{sec:SenAnalysis}
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.
\subsubsection{Support of faction leading}
\begin{figure}[ht!]
\centering
\includegraphics[width=0.6\columnwidth]{FIG/CoorEventSup}
\caption{An example of time series of following-network density. There are three coordination events where individual $A$ leads a group in first half of all coordination events while $B$ leads a group after $A$ for first and second coordination events. The third coordination event has $C$ leads the second half of the event. }
\label{fig:CoorEventSup}
\end{figure}
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.
\begin{definition}[Coordination event]
Let $\mathcal{F}=\{I\}$ be a set of faction intervals and $\omega$ be a time window. A coordination event $E_k=[t_1,t_2]$ is a combined interval of consecutive faction intervals from $\mathcal{F}$. Any faction interval $I_i=[t_i,t'_i]$ that occurs before another faction $I_j=[t_j,t'_j]$ are in the same coordination event if $t'_i<t_j\leq t'_i+\omega$.
\label{CoordinationEventDef}
\end{definition}
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.
\begin{equation}
\mathrm{sup}(L)= \frac{\left |{\{ E | E \in \mathcal{E}, \exists I\in \mathcal{F}_L, I \subseteq E\}}\right | }{|\mathcal{E}|}
\label{eq:LeaderFactioSup}
\end{equation}
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.
\begin{equation}
\mathrm{Conf}(B|A)= \frac{\left |{\{ E | E \in \mathcal{E}, \exists I_i \in \mathcal{F}_A, \exists I_j \in \mathcal{F}_B, I_i,I_j \subseteq E\}}\right | }{\left |{\{ E | E \in \mathcal{E}, \exists I\in \mathcal{F}_A, I \subseteq E\}}\right |}
\label{eq:LeaderFactioConf}
\end{equation}
Fig.~\ref{fig:CoorEventSup} 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$.
\subsubsection{Simulation and accuracy measure}
\begin{list}{$\bullet$}
{ \setlength{\itemsep}{-.1ex} \setlength{\parsep}{0ex}
\setlength{\topsep}{0ex} \setlength{\partopsep}{0ex}
\setlength{\leftmargin}{.8em} \setlength{\labelwidth}{1em}
\setlength{\labelsep}{0.5em} }
\item {\bf Initiator inference}: To measure the performance of framework vs. noise w.r.t. the initiator inference task, we use simulation datasets of movement time series within 2-dimensional space. A simulation dataset contains trajectories of individuals that have multiple coordination events (e.g. Fig.~\ref{fig:CoorEventSup}). Each type of simulation dataset contains different type and level of noises. The task is to predict a support of each initiators as well as confident values. The performance of framework is determined based on the error between ground truth and predicted values of support and confident measures. If the framework performs well, the predicted support and confident value of initiators should be close to the ground truth.
\item {\bf Coordination interval inference}: To measure the performance of framework vs. noise w.r.t. the coordination interval inference task, we use simulation datasets of movement time series within 2-dimensional space. we compared the predicted faction intervals of each initiators to the ground truth directly. The result of comparison are reported in the form of true positive, false positive, and false negative values. True positive will be counted at time step $t$ when a predicted and ground truth faction interval of initiator $L$ occurs at time $t$. False positive will be counted when the framework predicts that a time step $t$ is within $L$'s faction but it is not. False negative will be counted when the framework predicts that a time step $t$ is not within $L$'s faction but it is.
\end{list}
\subsubsection{Position and Direction noises}
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.
\subsubsection{Time window sensitivity}
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.
\section{Results}
\subsection{Identifying leaders}
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{EvalSec}). We set a window size $\omega$ by the TWIN heuristic \cite{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{SimPredictTB} reports precision on PageRank rank ordered lists over all synthetic model simulations. We compare against previous works--FLOCK \cite{andersson2008reporting}, IM \cite{kempe2003maximizing}, LPD \cite{kjargaard2013time}, and Copula-Granger Causality Inference models~\cite{liu2012sparse}--which produce a single ranking over the entire trial.
The white rows in Table \ref{SimPredictTB} 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 \emph{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 \emph{each} coordination event. Since previous work generates only aggregate rankings, precision for these methods are not reported.
\begin{table}
\caption{Precision of leadership identification on simulation models. (* indicates the $std\geq 0.1$).}
\label{SimPredictTB}
\begin{center}
\begin{tabular}
{| c | c | c | c | c | c | }
\hline
Models/Methods & FLICA & FLOCK & IM & LPD & Copula-Granger\\
\hline
{\small DM } & {\small\bf 1 } & {\small\bf 1 }& {\small\bf 1 }& {\small\bf 1 } & {\small\bf 0.97* }\\ \hline
{\small HM (Top-4) } & {\small\bf 1 } & {\small 0.25 }& {\small\bf 1 }& {\small\bf 1 } & {\small 0.55* }\\ \hline
{\small $LT$ } & {\small\bf 0.99 } & {\small 0.98* }& {\small 0.99* }& {\small 0.93* } & {\small 0.07* }\\ \hline
{\small $IC$ } & {\small\bf 1 } & {\small\bf 1 }& {\small\bf 1 }& {\small 0.99 } & {\small 0.45* } \\ \hline
{\small CM (Top-4) } & {\small\bf 1 } & {\small\bf 1 }& {\small\bf 1 }& {\small 0.99 } & {\small 0.69* }\\ \hline
{\small INIT-1 } & {\small\bf 1 } & {\small\bf 1 }& {\small\bf 1 }& {\small\bf 1 } & {\small 0.24* }\\ \hline
{\small INIT-4 (Top-4) } & {\small\bf 0.74* } & {\small 0.35* }& {\small 0.51* }& {\small 0.21* } & {\small\bf 0.91* }\\ \hline
\rowcolor{LightGray}{\small DM-S} & {\small\bf 1 }& {\small 0 }& {\small 0.02* }& {\small 0.25* } & {\small 0.37* } \\ \hline
\rowcolor{LightGray}
{\small HM-S (Top-4) } & {\small\bf 1 } & {\small 0 }& {\small 0.5 }& {\small 0.51 } & {\small 0.31* }\\ \hline
\rowcolor{LightGray}
{\small EM } & {\small\bf 0.92 } & {\small - }& {\small -}& {\small - } & {\small - }\\ \hline
\rowcolor{LightBlue}
{\small Random } & {\small 0.01 } & {\small 0 }& {\small 0.01 }& {\small 0.17* } & {\small 0.02* }\\ \hline
\end{tabular}
\end{center}
\end{table}
\subsection{Case study: trained initiators in fish schools}
We identify the top-$k$ global initiators of the fish school trajectory dataset (see Section \ref{subsubsec:fish}), where we have the labels of `trained' individuals expected to lead the school to feeding sites. Table \ref{FishPredictTB} 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.
\begin{table}[ht]
\caption{Initiator identification precision in fish (* indicates the $std\geq 0.1$). }
\label{FishPredictTB}
\begin{center}
\begin{tabular}{ | c | c | c |}
\hline
{\small Ranking }& {\small Initiator} & {\small Top-4 rank} \\ \hline
{\small FLICA }& {\small \bf 0.83*} & {\small \bf 0.61*} \\ \hline
{\small FLOCK \cite{andersson2008reporting} }& {\small 0.0} & {\small 0.0} \\ \hline
{\small IM \cite{kempe2003maximizing} }& {\small 0.0} & {\small 0.02} \\ \hline
{\small LPD \cite{kjargaard2013time} }& {\small 0.17*} & {\small 0.18*} \\ \hline
{\small Copula-Granger~\cite{liu2012sparse} }& {\small 0.13*} & {\small 0.10*} \\ \hline
\end{tabular}
\end{center}
\end{table}
\subsection{Case study: finding ``initiators" of stock market events}
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.
\begin{figure}[ht]
\centering
\subfigure{\label{fig:stocks-exA}\includegraphics[width=.9\columnwidth]{FIG/NASDAQ_NetDVec_02-11-16}}
\subfigure{\label{fig:stocks-exB}\includegraphics[width=.9\columnwidth]{FIG/NASDAQ_MarketPrice_02-11-16}}
\caption{(Top) NASDAQ `following' network density and (Bottom) NASDAQ index value. Pre-coordination and coordination intervals are shown in red and green, respectively. The framework detects many known events in financial data (labeled above). Many of these events are not reflected in the NASDAQ index. }
\label{fig:stockmarket}
\end{figure}
Fig.~\ref{fig:stockmarket} 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.
\begin{figure}[ht]
\centering
\includegraphics[width=1\columnwidth]{FIG/NASDAQRandNetPlot}
\caption{Comparison between time series of network density that generated from NASDAQ time series and from random walk time series. }
\label{fig:RandWalk}
\end{figure}
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{fig:RandWalk}. 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{fig:RandWalk}). 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.
\subsection{Case study: baboon activity classification by following network density}
\label{sec:ActCls}
\begin{figure}[ht]
\centering
\includegraphics[width=.8\columnwidth]{FIG/BaboonActRes}
\caption{Baboon activities from first two days of tracking vs. following network density}
\label{fig:BaboonActRes}
\end{figure}
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{subsubsec:baboon}).
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{fig:BaboonActRes} 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)~\cite{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.
\begin{table}[ht]
\caption{Activities classification prediction accuracy in first two days of baboon data. }
\label{BaboonAccPredictTB}
\begin{center}
\begin{tabular}{ | c | c | c |}
\hline
{\small Method }& {\small Baboon Day 1} & {\small Baboon Day 2} \\ \hline
{\small Linear discriminant analysis (LDA) + following network density }& {\small \bf 87.20\%} & {\small \bf 70.82\%} \\ \hline
{\small Adversarial Sequence Tagging (AST)~\cite{li2016adversarial} + 24 features }& {\small 77.30\%} & {\small 69.22\%} \\ \hline
\end{tabular}
\end{center}
\end{table}
The classification result is shown in Table~\ref{BaboonAccPredictTB}. The accuracy results were calculated by the complement of hamming loss the same as ~\cite{li2016adversarial}. By using only following network density as a feature, our simple classifier performs better than AST in both days.
\subsection{Leadership model classification}
\begin{figure}[ht]
\centering
\includegraphics[width=1\columnwidth]{FIG/FeaturePlot-02-17-17}
\caption{Comparison of feature spaces of leadership model classifications on simulations and real data}
\label{fig:ModelFeaturesMainNew}
\end{figure}
Recall, that we proposed several initiator rankings and ranking correlations (Section \ref{subsec:features-rank}). 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 \cite{ho1998random} over the 2700 total trials and report mean precision and recall across folds. Table \ref{FeaturesLCls} 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{fig:ModelFeaturesMainNew} visualizes sub-spaces of the full feature-space. Fig.~\ref{fig:ModelFeaturesMainNew} (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{fig:ModelFeaturesMainNew} (Bottom-Right) reports the mean rank correlation between PageRank rank ordering, against PCH and VCH ranking \emph{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.
\subsubsection{Baboon leadership model characterization}
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{fig:ModelFeaturesMainNew}, 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{fig:ModelFeaturesMainNew} (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.
\begin{table}[h!]
\caption{Random forest classification of synthetic leadership models using proposed features}
\label{FeaturesLCls}
\begin{center}
\begin{tabular}{ | c | c | c | c | c |}
\hline
{\small Model }& {\small Precision} & {\small Recall} & {\small F1-score} \\ \hline
{\small DM, DM-S} & {\small 0.86 } & {\small 0.80 } & {\small 0.81} \\ \hline
{\small HM, HM-S } & {\small 0.69 } & {\small 0.98 } & {\small 0.80} \\ \hline
{\small LT, IC, INIT-k} & {\small 0.99 } & {\small 0.97 } & {\small 0.98} \\ \hline
{\small CM } & {\small 0.75 } & {\small 0.94 } & {\small 0.80} \\ \hline
{\small EM } & {\small 1 } & {\small 0.54 } & {\small 0.64} \\ \hline
{\small Random } & {\small 0.98 } & {\small 0.95 } & {\small 0.97} \\ \hline
\end{tabular}
\end{center}
\end{table}
\subsection{Following network density perturbation in baboon and fish data}
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.
\begin{table}[]
\centering
\caption{The average difference of network density between before and after removing $k$ individuals on the baboon dataset. We compare the case of removing high-rank individuals vs. random individuals. An element in the table represents the difference between the original network density and the network density after removing $k$ individuals.}
\label{table:baboonPerturb}
\begin{tabular}{c|c|c|c|c|}
\cline{2-5}
& \multicolumn{4}{c|}{Number of Individuals being removed from 16 individuals (\#$k$)} \\ \hline
\multicolumn{1}{|c|}{} & \#1 & \#2 & \#3 & \#4 \\ \hline
\multicolumn{1}{|c|}{High-Rank} & $-5.45\times 10^{-03}$ & $-7.37\times 10^{-03}$ & $-9.65\times 10^{-03}$ & $-10.14\times 10^{-03}$ \\ \hline
\multicolumn{1}{|c|}{Random} & $0.057\times 10^{-03}$ & $-0.004\times 10^{-03}$ & $-0.504\times 10^{-03}$ & $0.002\times 10^{-03}$ \\ \hline
\end{tabular}
\end{table}
Table~\ref{table:baboonPerturb} 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.
\begin{table}[]
\centering
\caption{The average difference of the network density between before and after removing $k$ individuals from the fish data. We compare the case of removing high-rank individuals vs. random individuals. An element in the table represents the difference between the original network density and the network density after removing $k$ individuals.}
\label{table:fishPerturb}
\begin{tabular}{c|c|c|c|c|}
\cline{2-5}
& \multicolumn{4}{c|}{Number of Individuals being removed from 70 individuals (\#$k$)} \\ \hline
\multicolumn{1}{|c|}{} & \#2 & \#4 & \#6 & \#8 \\ \hline
\multicolumn{1}{|c|}{High-Rank} & $-20.26\times 10^{-04}$ & $-3.96\times 10^{-04}$ & $-2.45\times 10^{-04}$ & $-8.44\times 10^{-04}$ \\ \hline
\multicolumn{1}{|c|}{Random} & $-0.55\times 10^{-04}$ & $-0.04\times 10^{-04}$ & $-3.90\times 10^{-04}$ & $-3.88\times 10^{-04}$ \\ \hline
\end{tabular}
\end{table}
In the fish data, Table~\ref{table:fishPerturb} 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.
\subsection{Sensitivity analysis}
We conducted the sensitivity analysis based on Section~\ref{sec:SenAnalysis} 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{fig:SupSenAz}. 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{eq:LeaderFactioSup}). In general, unsurprisingly, the loss value increases with noise.
\begin{figure}[ht]
\centering
\includegraphics[width=1\columnwidth]{FIG/errSupSenAzPlot}
\caption{Loss values of prediction of the initiator support for different levels of noise and time window sizes. A lower value implies a better prediction result.}
\label{fig:SupSenAz}
\end{figure}
Fig.~\ref{fig:SupSenAz} (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.
\begin{figure}[ht]
\centering
\includegraphics[width=1\columnwidth]{FIG/errConfSenAzPlot}
\caption{Loss values of prediction of the initiator confidence for different levels of noise and time window sizes. A lower value implies a better prediction result.}
\label{fig:ConfSenAz}
\end{figure}
Fig.~\ref{fig:ConfSenAz} 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.
\begin{figure}[ht]
\centering
\includegraphics[width=1\columnwidth]{FIG/F1SenAzPlot}
\caption{F1 scores of coordination inference for different levels of noise and time window sizes. A higher value implies a better prediction result. }
\label{fig:F1SenAz}
\end{figure}
In the coordination inference task, Fig.~\ref{fig:F1SenAz} 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.
\section{Conclusions}
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 \cite{FLICAwebsite}.
\bibliographystyle{ACM-Reference-Format-Journals}
\begin{thebibliography}{00}
\ifx \showCODEN \undefined \def \showCODEN #1{\unskip} \fi
\ifx \showDOI \undefined \def \showDOI #1{{\tt DOI:}\penalty0{#1}\ }
\fi
\ifx \showISBNx \undefined \def \showISBNx #1{\unskip} \fi
\ifx \showISBNxiii \undefined \def \showISBNxiii #1{\unskip} \fi
\ifx \showISSN \undefined \def \showISSN #1{\unskip} \fi
\ifx \showLCCN \undefined \def \showLCCN #1{\unskip} \fi
\ifx \shownote \undefined \def \shownote #1{#1} \fi
\ifx \showarticletitle \undefined \def \showarticletitle #1{#1} \fi
\ifx \showURL \undefined \def \showURL #1{#1} \fi
\bibitem[\protect\citeauthoryear{Amornbunchornvej}{Amornbunchornvej}{2017}]
{FLICAwebsite}
{C. Amornbunchornvej}. 2017.
\newblock FLICA: A Framework for Leader Identification in Coordinated Activity
codes.
\newblock \url{https://github.com/CompBioUIC/FLICA}. (2017).
\newblock
\newblock
\shownote{Accessed: 2017-08-30.}
\bibitem[\protect\citeauthoryear{Amornbunchornvej, Brugere, Strandburg-Peshkin,
Farine, Crofoot, and Berger-Wolf}{Amornbunchornvej et~al\mbox{.}}{2017}]
{flicaMilets}
{Chainarong Amornbunchornvej}, {Ivan Brugere}, {Ariana Strandburg-Peshkin},
{Damien Farine}, {Margaret~C Crofoot}, {and} {Tanya~Y Berger-Wolf}. 2017.
\newblock \showarticletitle{Coordination Event Detection and Initiator
Identification in Time Series Data}. In {\em SIGKDD Workshop on Mining and
Learning from Time Series (MiLeTS 2017)}. 1--9.
\newblock
\bibitem[\protect\citeauthoryear{Andersson, Gudmundsson, Laube, and
Wolle}{Andersson et~al\mbox{.}}{2008}]
{andersson2008reporting}
{Mattias Andersson}, {Joachim Gudmundsson}, {Patrick Laube}, {and} {Thomas
Wolle}. 2008.
\newblock \showarticletitle{Reporting leaders and followers among trajectories
of moving point objects}.
\newblock {\em GeoInformatica\/} {12}, 4 (2008), 497--528.
\newblock
\bibitem[\protect\citeauthoryear{Arnold, Liu, and Abe}{Arnold
et~al\mbox{.}}{2007}]
{Arnold:2007:TCM:1281192.1281203}
{Andrew Arnold}, {Yan Liu}, {and} {Naoki Abe}. 2007.
\newblock \showarticletitle{Temporal Causal Modeling with Graphical Granger
Methods}. In {\em Proceedings of the 13th ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining} {\em (KDD '07)}. ACM, New York, NY,
USA, 66--75.
\newblock
\showISBNx{978-1-59593-609-7}
\showDOI{
\url{http://dx.doi.org/10.1145/1281192.1281203}}
\bibitem[\protect\citeauthoryear{Bakshy, Hofman, Mason, and Watts}{Bakshy
et~al\mbox{.}}{2011}]
{Bakshy:2011:EIQ:1935826.1935845}
{Eytan Bakshy}, {Jake~M. Hofman}, {Winter~A. Mason}, {and} {Duncan~J. Watts}.
2011.
\newblock \showarticletitle{Everyone's an Influencer: Quantifying Influence on
Twitter}. In {\em Proceedings of the Fourth ACM International Conference on
Web Search and Data Mining} {\em (WSDM '11)}. ACM, New York, NY, USA, 65--74.
\newblock
\showISBNx{978-1-4503-0493-1}
\showDOI{
\url{http://dx.doi.org/10.1145/1935826.1935845}}
\bibitem[\protect\citeauthoryear{Ben~Dushnik}{Ben~Dushnik}{1941}]
{partialOrder}
{E.~W.~Miller Ben~Dushnik}. 1941.
\newblock \showarticletitle{Partially Ordered Sets}.
\newblock {\em American Journal of Mathematics\/} {63}, 3 (1941), 600--610.
\newblock
\showISSN{00029327, 10806377}
\showURL{
\url{http://www.jstor.org/stable/2371374}}
\bibitem[\protect\citeauthoryear{Boydston, Morelli, and Holekamp}{Boydston
et~al\mbox{.}}{2001}]
{Boydston:2001}
{Erin~E. Boydston}, {Toni~Lyn Morelli}, {and} {Kay~E. Holekamp}. 2001.
\newblock \showarticletitle{Sex Differences in Territorial Behavior Exhibited
by the Spotted Hyena (Hyaenidae, Crocuta crocuta)}.
\newblock {\em Ethology\/} {107}, 5 (2001), 369--385.
\newblock
\showISSN{1439-0310}
\showDOI{
\url{http://dx.doi.org/10.1046/j.1439-0310.2001.00672.x}}
\bibitem[\protect\citeauthoryear{Brent, Franks, Foster, Balcomb, Cant, and
Croft}{Brent et~al\mbox{.}}{2015}]
{Brent2015746}
{Lauren~J.N. Brent}, {Daniel~W. Franks}, {Emma~A. Foster}, {Kenneth~C.
Balcomb}, {Michael~A. Cant}, {and} {Darren~P. Croft}. 2015.
\newblock \showarticletitle{Ecological Knowledge, Leadership, and the Evolution
of Menopause in Killer Whales}.
\newblock {\em Current Biology\/} {25}, 6 (2015), 746 -- 750.
\newblock
\showISSN{0960-9822}
\showDOI{
\url{http://dx.doi.org/10.1016/j.cub.2015.01.037}}
\bibitem[\protect\citeauthoryear{Chazelle}{Chazelle}{2011}]
{doi:10.1137/100791671}
{Bernard Chazelle}. 2011.
\newblock \showarticletitle{The Total s-Energy of a Multiagent System}.
\newblock {\em SIAM Journal on Control and Optimization\/} {49}, 4 (2011),
1680--1706.
\newblock
\showDOI{
\url{http://dx.doi.org/10.1137/100791671}}
\bibitem[\protect\citeauthoryear{Conradt and Roper}{Conradt and Roper}{2003}]
{Conradt:2003aa}
{Larissa Conradt} {and} {Timothy~J Roper}. 2003.
\newblock \showarticletitle{Group decision-making in animals}.
\newblock {\em Nature\/} {421}, 6919 (2003), 155--158.
\newblock
\bibitem[\protect\citeauthoryear{Couzin, Krause, Franks, and Levin}{Couzin
et~al\mbox{.}}{2005}]
{Couzin:2005aa}
{Iain~D Couzin}, {Jens Krause}, {Nigel~R Franks}, {and} {Simon~A Levin}. 2005.
\newblock \showarticletitle{Effective leadership and decision-making in animal
groups on the move}.
\newblock {\em Nature\/} {433}, 7025 (2005), 513--516.
\newblock
\bibitem[\protect\citeauthoryear{Crofoot, Kays, and Wikelski}{Crofoot
et~al\mbox{.}}{2015}]
{crofoot2015data}
{Margaret~C Crofoot}, {Roland~W Kays}, {and} {Martin Wikelski}. 2015.
\newblock Data from: Shared decision-making drives collective movement in wild
baboons.
\newblock (2015).
\newblock
\bibitem[\protect\citeauthoryear{Dyer, Johansson, Helbing, Couzin, and
Krause}{Dyer et~al\mbox{.}}{2009}]
{Dyer:2009aa}
{John~R.G Dyer}, {Anders Johansson}, {Dirk Helbing}, {Iain~D Couzin}, {and}
{Jens Krause}. 2009.
\newblock \showarticletitle{Leadership, consensus decision making and
collective behaviour in humans}.
\newblock {\em Philosophical Transactions of the Royal Society of London B:
Biological Sciences\/} {364}, 1518 (2009), 781--789.
\newblock
\showISSN{0962-8436}
\showDOI{
\url{http://dx.doi.org/10.1098/rstb.2008.0233}}
\bibitem[\protect\citeauthoryear{Gilby, Machanda, Mjungu, Rosen, Muller, Pusey,
and Wrangham}{Gilby et~al\mbox{.}}{2015}]
{Gilby:2015}
{Ian~C. Gilby}, {Zarin~P. Machanda}, {Deus~C. Mjungu}, {Jeremiah Rosen},
{Martin~N. Muller}, {Anne~E. Pusey}, {and} {Richard~W. Wrangham}. 2015.
\newblock \showarticletitle{{\textquoteleft}Impact hunters{\textquoteright}
catalyse cooperative hunting in two wild chimpanzee communities}.
\newblock {\em Philosophical Transactions of the Royal Society of London B:
Biological Sciences\/} {370}, 1683 (2015).
\newblock
\showISSN{0962-8436}
\showDOI{
\url{http://dx.doi.org/10.1098/rstb.2015.0005}}
\bibitem[\protect\citeauthoryear{Glowacki and von Rueden}{Glowacki and von
Rueden}{2015}]
{Glowacki:2015}
{Luke Glowacki} {and} {Chris von Rueden}. 2015.
\newblock \showarticletitle{Leadership solves collective action problems in
small-scale societies}.
\newblock {\em Philosophical Transactions of the Royal Society of London B:
Biological Sciences\/} {370}, 1683 (2015).
\newblock
\showISSN{0962-8436}
\showDOI{
\url{http://dx.doi.org/10.1098/rstb.2015.0010}}
\bibitem[\protect\citeauthoryear{Goyal, Bonchi, and Lakshmanan}{Goyal
et~al\mbox{.}}{2008}]
{goyal2008discovering}
{Amit Goyal}, {Francesco Bonchi}, {and} {Laks~V.S. Lakshmanan}. 2008.
\newblock \showarticletitle{Discovering Leaders from Community Actions}. In
{\em Proceedings of the 17th ACM Conference on Information and Knowledge
Management} {\em (CIKM '08)}. ACM, New York, NY, USA, 499--508.
\newblock
\showISBNx{978-1-59593-991-3}
\showDOI{
\url{http://dx.doi.org/10.1145/1458082.1458149}}
\bibitem[\protect\citeauthoryear{Goyal, Bonchi, and Lakshmanan}{Goyal
et~al\mbox{.}}{2010}]
{goyal2010learning}
{Amit Goyal}, {Francesco Bonchi}, {and} {Laks~VS Lakshmanan}. 2010.
\newblock \showarticletitle{Learning influence probabilities in social
networks}. In {\em Proceedings of the third ACM international conference on
Web search and data mining}. ACM, 241--250.
\newblock
\bibitem[\protect\citeauthoryear{Granger}{Granger}{1969}]
{10.2307/1912791}
{C.~W.~J. Granger}. 1969.
\newblock \showarticletitle{Investigating Causal Relations by Econometric
Models and Cross-spectral Methods}.
\newblock {\em Econometrica\/} {37}, 3 (1969), 424--438.
\newblock
\showISSN{00129682, 14680262}
\showURL{
\url{http://www.jstor.org/stable/1912791}}
\bibitem[\protect\citeauthoryear{Heinsohn and Packer}{Heinsohn and
Packer}{1995}]
{Heinsohn1260}
{Robert Heinsohn} {and} {Craig Packer}. 1995.
\newblock \showarticletitle{Complex Cooperative Strategies in Group-Territorial
African Lions}.
\newblock {\em Science\/} {269}, 5228 (1995), 1260--1262.
\newblock
\showISSN{00368075, 10959203}
\showURL{
\url{http://www.jstor.org/stable/2888011}}
\bibitem[\protect\citeauthoryear{Ho}{Ho}{1998}]
{ho1998random}
{Tin~Kam Ho}. 1998.
\newblock \showarticletitle{The random subspace method for constructing
decision forests}.
\newblock {\em IEEE Transactions on Pattern Analysis and Machine
Intelligence\/} {20}, 8 (1998), 832--844.
\newblock
\bibitem[\protect\citeauthoryear{Holme}{Holme}{2014}]
{holme2014temporal}
{Petter Holme}. 2014.
\newblock {\em Temporal networks}.
\newblock Springer.
\newblock
\bibitem[\protect\citeauthoryear{Hooper, Kaplan, and Boone}{Hooper
et~al\mbox{.}}{2010}]
{Hooper2010633}
{Paul~L. Hooper}, {Hillard~S. Kaplan}, {and} {James~L. Boone}. 2010.
\newblock \showarticletitle{A theory of leadership in human cooperative
groups}.
\newblock {\em Journal of Theoretical Biology\/} {265}, 4 (2010), 633 -- 646.
\newblock
\showISSN{0022-5193}
\showDOI{
\url{http://dx.doi.org/10.1016/j.jtbi.2010.05.034}}
\bibitem[\protect\citeauthoryear{Kempe, Kleinberg, and Tardos}{Kempe
et~al\mbox{.}}{2003}]
{kempe2003maximizing}
{David Kempe}, {Jon Kleinberg}, {and} {{\'E}va Tardos}. 2003.
\newblock \showarticletitle{Maximizing the spread of influence through a social
network}. In {\em Proceedings of the ninth ACM SIGKDD}. ACM, 137--146.
\newblock
\bibitem[\protect\citeauthoryear{Kendall}{Kendall}{1938}]
{Kendall1938}
{M.~G. Kendall}. 1938.
\newblock \showarticletitle{A New Measure of Rank Correlation}.
\newblock {\em Biometrika\/} {30}, 1/2 (1938), 81--93.
\newblock
\showISSN{00063444}
\showURL{
\url{http://www.jstor.org/stable/2332226}}
\bibitem[\protect\citeauthoryear{Kjargaard, Blunck, Wustenberg, Gronbask, Wirz,
Roggen, and Troster}{Kjargaard et~al\mbox{.}}{2013}]
{kjargaard2013time}
{Mikkel~Baun Kjargaard}, {Henrik Blunck}, {Markus Wustenberg}, {Kaj Gronbask},
{Martin Wirz}, {Daniel Roggen}, {and} {Gerhard Troster}. 2013.
\newblock \showarticletitle{Time-lag method for detecting following and
leadership behavior of pedestrians from mobile sensing data}. In {\em
Proceedings of the IEEE PerCom}. IEEE, 56--64.
\newblock
\bibitem[\protect\citeauthoryear{Li, Asif, Wang, Ziebart, and Berger-Wolf}{Li
et~al\mbox{.}}{2016}]
{li2016adversarial}
{Jia Li}, {Kaiser Asif}, {Hong Wang}, {Brian~D Ziebart}, {and} {Tanya~Y
Berger-Wolf}. 2016.
\newblock \showarticletitle{Adversarial Sequence Tagging.}. In {\em IJCAI}.
1690--1696.
\newblock
\bibitem[\protect\citeauthoryear{Liu, Lafferty, and Wasserman}{Liu
et~al\mbox{.}}{2009}]
{liu2009nonparanormal}
{Han Liu}, {John Lafferty}, {and} {Larry Wasserman}. 2009.
\newblock \showarticletitle{The nonparanormal: Semiparametric estimation of
high dimensional undirected graphs}.
\newblock {\em Journal of Machine Learning Research\/} {10}, Oct (2009),
2295--2328.
\newblock
\bibitem[\protect\citeauthoryear{Liu, Bahadori, and Li}{Liu
et~al\mbox{.}}{2012}]
{liu2012sparse}
{Yan Liu}, {Taha Bahadori}, {and} {Hongfei Li}. 2012.
\newblock \showarticletitle{Sparse-gev: Sparse latent space model for
multivariate extreme value time serie modeling}.
\newblock {\em ICML\/} (2012).
\newblock
\bibitem[\protect\citeauthoryear{Lusseau and Conradt}{Lusseau and
Conradt}{2009}]
{lusseau2009emergence}
{David Lusseau} {and} {Larissa Conradt}. 2009.
\newblock \showarticletitle{The emergence of unshared consensus decisions in
bottlenose dolphins}.
\newblock {\em Behavioral Ecology and Sociobiology\/} {63}, 7 (2009),
1067--1077.
\newblock
\bibitem[\protect\citeauthoryear{Mares, Young, and Clutton-Brock}{Mares
et~al\mbox{.}}{2012}]
{Mares3989}
{Rafael Mares}, {Andrew~J. Young}, {and} {Tim~H. Clutton-Brock}. 2012.
\newblock \showarticletitle{Individual contributions to territory defence in a
cooperative breeder: weighing up the benefits and costs}.
\newblock {\em Proceedings of the Royal Society of London B: Biological
Sciences\/} {279}, 1744 (2012), 3989--3995.
\newblock
\showISSN{0962-8452}
\showDOI{
\url{http://dx.doi.org/10.1098/rspb.2012.1071}}
\bibitem[\protect\citeauthoryear{Northouse}{Northouse}{2016}]
{LeadershipBook}
{Peter~G Northouse}. 2016.
\newblock {\em Leadership: Theory and practice}.
\newblock Sage publications.
\newblock
\bibitem[\protect\citeauthoryear{Page, Brin, Motwani, and Winograd}{Page
et~al\mbox{.}}{1999}]
{PageRank_Brin1998107}
{Lawrence Page}, {Sergey Brin}, {Rajeev Motwani}, {and} {Terry Winograd}. 1999.
\newblock {\em The PageRank Citation Ranking: Bringing Order to the Web.}
\newblock Technical Report 1999-66. Stanford InfoLab.
\newblock
\showURL{
\url{http://ilpubs.stanford.edu:8090/422/}}
\bibitem[\protect\citeauthoryear{Petit and Bon}{Petit and Bon}{2010}]
{Petit2010635}
{Odile Petit} {and} {Richard Bon}. 2010.
\newblock \showarticletitle{Decision-making processes: The case of collective
movements}.
\newblock {\em Behavioural Processes\/} {84}, 3 (2010), 635 -- 647.
\newblock
\showISSN{0376-6357}
\showDOI{
\url{http://dx.doi.org/10.1016/j.beproc.2010.04.009}}
\newblock
\shownote{Special section: Collective movements.}
\bibitem[\protect\citeauthoryear{Pham and Shahabi}{Pham and Shahabi}{2016}]
{PhamICDE2016}
{H. Pham} {and} {C. Shahabi}. 2016.
\newblock \showarticletitle{Spatial influence - measuring followship in the
real world}. In {\em ICDE16}. 529--540.
\newblock
\showDOI{
\url{http://dx.doi.org/10.1109/ICDE.2016.7498268}}
\bibitem[\protect\citeauthoryear{Sakoe and Chiba}{Sakoe and Chiba}{1978}]
{Sakoe1978}
{H. Sakoe} {and} {S. Chiba}. 1978.
\newblock \showarticletitle{Dynamic programming algorithm optimization for
spoken word recognition}.
\newblock {\em IEEE Transactions on Acoustics, Speech, and Signal Processing\/}
{26}, 1 (Feb 1978), 43--49.
\newblock
\showISSN{0096-3518}
\showDOI{
\url{http://dx.doi.org/10.1109/TASSP.1978.1163055}}
\bibitem[\protect\citeauthoryear{Shokoohi-Yekta, Wang, and
Keogh}{Shokoohi-Yekta et~al\mbox{.}}{2015}]
{doi:10.1137/1.9781611974010.33}
{M Shokoohi-Yekta}, {J Wang}, {and} {E Keogh}. 2015.
\newblock \showarticletitle{On the Non-Trivial Generalization of Dynamic Time
Warping to the Multi-Dimensional Case}. In {\em SDM'15}. 289--297.
\newblock
\bibitem[\protect\citeauthoryear{Stewart and Scott}{Stewart and Scott}{1947}]
{Stewart:1947aa}
{Jeannie~C Stewart} {and} {JP Scott}. 1947.
\newblock \showarticletitle{Lack of correlation between leadership and
dominance relationships in a herd of goats.}
\newblock {\em Journal of comparative and physiological psychology\/} {40}, 4
(1947), 255.
\newblock
\bibitem[\protect\citeauthoryear{Strandburg-Peshkin and
et~al.}{Strandburg-Peshkin and et~al.}{2013}]
{strandburg2013visual}
{A. Strandburg-Peshkin} {and} {et al.} 2013.
\newblock \showarticletitle{Visual sensory networks and effective information
transfer in animal groups}.
\newblock {\em Current Biology\/} {23}, 17 (2013), R709--R711.
\newblock
\bibitem[\protect\citeauthoryear{Strandburg-Peshkin, Farine, Couzin, and
Crofoot}{Strandburg-Peshkin et~al\mbox{.}}{2015}]
{Strandburg-Peshkin1358}
{Ariana Strandburg-Peshkin}, {Damien~R. Farine}, {Iain~D. Couzin}, {and}
{Margaret~C. Crofoot}. 2015.
\newblock \showarticletitle{Shared decision-making drives collective movement
in wild baboons}.
\newblock {\em Science\/} {348}, 6241 (2015), 1358--1361.
\newblock
\showISSN{0036-8075}
\showDOI{
\url{http://dx.doi.org/10.1126/science.aaa5099}}
\bibitem[\protect\citeauthoryear{Stueckle and Zinner}{Stueckle and
Zinner}{2008}]
{Stueckle2008}
{Sabine Stueckle} {and} {Dietmar Zinner}. 2008.
\newblock \showarticletitle{To follow or not to follow: decision making and
leadership during the morning departure in chacma baboons}.
\newblock {\em Animal Behaviour\/} {75}, 6 (2008), 1995 -- 2004.
\newblock
\showISSN{0003-3472}
\showDOI{
\url{http://dx.doi.org/10.1016/j.anbehav.2007.12.012}}
\bibitem[\protect\citeauthoryear{Sulo, Berger-Wolf, and Grossman}{Sulo
et~al\mbox{.}}{2010}]
{sulo2010meaningful}
{Rajmonda Sulo}, {Tanya Berger-Wolf}, {and} {Robert Grossman}. 2010.
\newblock \showarticletitle{Meaningful selection of temporal resolution for
dynamic networks}. In {\em Proceedings of the Eighth Workshop on Mining and
Learning with Graphs}. ACM, 127--136.
\newblock
\bibitem[\protect\citeauthoryear{Sun and Tang}{Sun and Tang}{2011}]
{Sun2011}
{Jimeng Sun} {and} {Jie Tang}. 2011.
\newblock {\em A Survey of Models and Algorithms for Social Influence
Analysis}.
\newblock Springer US, Boston, MA, 177--214.
\newblock
\showISBNx{978-1-4419-8462-3}
\showDOI{
\url{http://dx.doi.org/10.1007/978-1-4419-8462-3_7}}
\bibitem[\protect\citeauthoryear{Weinstein and Maelzer}{Weinstein and
Maelzer}{1997}]
{Weinstein:1997}
{P. Weinstein} {and} {D.~A. Maelzer}. 1997.
\newblock \showarticletitle{Leadership Behaviour in Sawfly Larvae Perga
dorsalis (Hymenoptera: Pergidae)}.
\newblock {\em Oikos\/} {79}, 3 (1997), 450--455.
\newblock
\showISSN{00301299, 16000706}
\showURL{
\url{http://www.jstor.org/stable/3546887}}
\bibitem[\protect\citeauthoryear{Wilson}{Wilson}{2009}]
{WilsonSocbio}
{Edward~O Wilson}. 2009.
\newblock \showarticletitle{Sociobiology: the new synthesis}.
\newblock {\em Philosophy of Biology: An Anthology\/} (2009), 339.
\newblock
\bibitem[\protect\citeauthoryear{Wu and Sun}{Wu and Sun}{2014}]
{Song2014crowdmodel}
{Song Wu} {and} {Quanbin Sun}. 2014.
\newblock \showarticletitle{Computer Simulation of Leadership, Consensus
Decision Making and Collective Behaviour in Humans}.
\newblock {\em PLOS ONE\/} {9}, 1 (01 2014), 1--12.
\newblock
\showDOI{
\url{http://dx.doi.org/10.1371/journal.pone.0080680}}
\end{thebibliography}