# Fast and Robust Flocking of Protesters on Street Networks

Guillaume Moinard, Matthieu Latapy

► To cite this version:

Guillaume Moinard, Matthieu Latapy. Fast and Robust Flocking of Protesters on Street Networks. 2024. hal-04594953

HAL Id: hal-04594953

https://hal.science/hal-04594953

Preprint submitted on 30 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fast and Robust Flocking of Protesters on Street Networks

Guillaume Moinard, Matthieu Latapy

<figure><img src="image_1.png" /></figure>

## To cite this version:

Guillaume Moinard, Matthieu Latapy. Fast and Robust Flocking of Protesters on Street Networks. 2025. hal-04594953v2

HAL Id: hal-04594953

https://hal.science/hal-04594953v2

Preprint submitted on 24 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fast and Robust Flocking of Protesters
on Street Networks

Guillaume Moinard, Matthieu Latapy

Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

## Abstract

We propose a simple model of protesters scattered throughout a city who want to gather into large and mobile groups. This model relies on random walkers on a street network that follow tactics built from a set of basic rules. Our goal is to identify the most important rules for fast and robust flocking of walkers. We explore a wide set of tactics and show the central importance of a specific rule based on alignment. Other rules alone perform poorly, but our experiments show that combining alignment with them enhances flocking, and that obtained groups are then remarkably robust.

*Keywords*: street networks, gathering, flocking, tactic design, robustness, protests

## 1 Introduction

Consider the following scenario. Protesters are scattered throughout a city and want to gather into groups large enough to perform significant actions. They face forces that may break up groups, block some places or streets and seize any communication devices protesters may be carrying. As a consequence, protesters only have access to local information on people and streets around them. Furthermore, formed protester groups must keep moving to avoid containment by adversary forces.

In this scenario, protesters need a distributed and as simple as possible protocol, that utilises local information exclusively and ensures the rapid formation of significantly large, mobile, and robust groups. We illustrate these objectives in Figure 1. Our goal in this paper is to identify the key building blocks for such protocols.

To do so, we model the city as a network of streets and intersections in Section 2. We then assume that protesters are biased random walkers on such a network. In Section 3, we present the set of basic rules that compose *tactics* walkers can use to move. We define, in Section 4, what flocking features groups must achieve and run extensive experiments to measure how effective each tactic is regarding those. We also explore the robustness of groups, measuring how they reform if adversary forces break them up while following an effective tactic. In Section 5, we compare our approach to related work on flocking and on formal analysis of protests. We emphasise the absence of a protocol that can solve our problem. Finally, we summarise our contributions in Section 6.

<figure><img src="image_2.png" /><figcaption>Figure 1: Walkers scattered on a street network (left) must rapidly gather (center) and subsequently flock (right).</figcaption></figure>

## 2 Framework

We need a framework to simulate displacements of protesters in a city. We model cities as undirected graphs we call street networks. Protesters are then biased random walkers on this network. They can move from node to node with simple rules we introduce in next Section.

### 2.1 Street networks

In order to model real-world cities, we leverage OpenStreetMap [1] data and the OSMnx library [2]. For a given city, we use this library with its default settings to extract the graph $G = (V, E)$ defined as follows: the nodes in $V$ represent street intersections in this city and the links in $E \subseteq V \times V$ represent pieces of streets between them. We take the undirected graph $G$, meaning there is no distinction between $(u, v)$ and $(v, u)$ in $E$. In addition, we denote by $N(v) = \{u, (u, v) \in E\}$ the set of neighbors of any node $v$ in $V$.

We performed experiments on a wide ranges of large worldwide cities of diverse sizes and structures. This led to no significant difference on obtained results. We therefore use a typical in-
# Fast and Robust Flocking of Protesters in Street Networks

Guillaume Moinard, Matthieu Latapy

Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

## Abstract

We present a simple model of protesters scattered throughout a city who want to gather into large and mobile groups. This model relies on random walkers on a street network that follow tactics built from a set of basic rules. Our goal is to identify the most important rules for fast and robust flocking of walkers. We explore a wide set of tactics and show the central importance of a specific rule based on alignment. Other rules alone perform poorly, but our experiments show that combining alignment with them enhances flocking, and that obtained groups are then remarkably robust.

**Keywords:** street networks, gathering, flocking, robustness, protests

## 1 Introduction

Consider the following scenario. Protesters are scattered throughout a city and want to gather into groups large enough to perform significant actions. They face forces that may break up groups, block some places or streets, seize communication devices carried by protesters, or even shut down or compromise communication systems. As a consequence, protesters only have access to local information on people and streets around them. Furthermore, formed protester groups must keep moving to avoid containment by adversary forces and perform actions.

In this scenario, protesters need a distributed and as simple as possible protocol, that uses local information only and ensures the fast formation of significantly large, mobile, and robust groups. We illustrate these objectives in Figure 1. Our goal in this paper is to identify the key building blocks for such protocols.

To do so, we first model the city as a network of streets and intersections, and we model protesters as biased random walkers on this network. We then define a set of basic rules that walkers may use as building blocks to compose *tactics*, as well as metrics that quantify key group features. We perform extensive experiments in order to explore how various tactics behave regarding these metrics. We also explore group robustness when adversary forces break them up while they follow an effective tactic.
stance, namely Paris, to present our work in this paper. This street network has 9 602 nodes, 14 974 links, leading to average degree 3.1. Its diameter is 83 hops and its average distance is 39.4 hops. The average street length is 99 meters, and the average distance is 5 552 meters.

## 2.2 Walkers

Given a network $G = (V, E)$, we consider a set $W$ of walkers numbered from 1 to $|W|$. We denote the location of walker $i$ at time $t$ by $x_i(t) = v$, with $v \in V$. At each time step $t$, walker $i$ moves to node $x_i(t+1) \in N(v)$. Rules we present in Section 3 determine the choice of $x_i(t+1)$.

For any link $(u, v)$ in $E$, we also define the *flux* of walkers from $u$ to $v$ as $J_{u \to v}(t) = |\{i, x_i(t-1) = u, x_i(t) = v\}|$.

We call *group* the set of walkers at a given node $v$ at a given time $t$: $g_v(t) = \{i, x_i(t) = v\}$. We denote by $n_v(t) = |g_v(t)|$ the number of walkers located at node $v$ at time $t$. We denote by $g(t) = |\{g_v(t), v \in V, g_v(t) \neq \emptyset\}|$ the number of non-empty groups at step $t$.

## 2.3 Discretization

The links of a street network generally represent street segments of very heterogeneous lengths [3]. Then, moves from a node to another one may have very different duration. In order to model this, we use a classical discretization procedure [4] that we describe below. It consists in splitting each link of the street network into pieces connected by evenly spaced nodes, see Figure 2.

More formally, given a link $(u, v)$ representing a piece of street of length $L$ in a street network and a discretization step $\delta$, we split each undirected link $(u, v)$ into $k$ new links, with $k = \lfloor \frac{L}{\delta} \rfloor$ as follows. Let us denote a set of new nodes $V(u, v) = \{v_0, v_1, \dots, v_k\}$ with the nodes from the original network being $v_0 = u$ and $v_k = v$. We then define a set of new links $E(u, v) = \{(w_i, w_{i+1}), i = 0, 1, \dots, k\}$. Then we define the set of all nodes $V = \bigcup_{u,v} V(u, v)$ and the set of links $E = \bigcup_{u,v} E(u, v)$. Finally, we model the street network by the graph $G = (V, E)$.

In the obtained graph, each link represents a street slice of length close to $\delta$. Then, the walkers defined in previous section consistently make a move of length approximately $\delta$ at each time step.

In this paper, we use $\delta$ equal to 10 meters, leading to a network of $N = 145000$ nodes and $M = 300736$ links. It gives a sufficient precision in our context, and experiments with other reasonable values of $\delta$ displayed no significant difference.

<figure><img src="image_3.png" /><figcaption>Figure 2: A piece of the discretized street network around Place de la Nation in Paris.</figcaption></figure>

# 3 Walker model

At each time step $t$, each walker $i$ moves from location $x_i(t)$ to location $x_i(t+1)$ in $N(x_i(t))$. This section presents how we choose the new location $x_i(t+1)$.

## 3.1 Available information

We assume that walkers have very limited capabilities: they have no access to the actual location of other walkers, even on neighbor nodes, and they have no long-term memory and no communication protocol. Instead, we assume they only have access to estimates of aggregated observables, such as the number of walkers on neighbor nodes and the flow intensity on surrounding links, and a short-term memory.

More formally, walker $i$ may use the following information:

* its previous location $x_i(t-1)$,

* the number $n_v(t)$ of walkers on node $v$ for all $v$ in $N(x_i(t)) \cup \{x_i(t)\}$,

* the flux of walkers arriving and leaving its current location $v = x_i(t)$, i.e. $J_{u \to v}(t)$ and $J_{v \to u}(t)$ for all $u$ in $N(v)$.

Thanks to the information above, each walker $i$ knows its previous location $u = x_i(t-1)$, its current location $v = x_i(t)$, and it has access to various criteria to decide its next location $w = x_i(t+1)$. Then, it needs a way to derive walking rules from criteria, and a way to combine these walking rules into a tactic.

## 3.2 Criteria

A criterion is a parameter from which we construct walking rules. We consider the following set of criteria $C$.

* *Random.* The walker makes no difference between all possible neighbors: the criterion has value 1 for each of them.

* *Propulsion.* The walker never goes back to its previous location $u$, and otherwise makes random moves: the criterion has value 0 for $u$ and value 1 for other neighbors of $v$.
<figure><img src="image_3.png" /><figcaption>Figure 1: We expect walkers scattered on a street network (left) to quickly gather (center) and then flock (right).</figcaption></figure>

# 2 Framework

This section presents our simulation framework. It models cities as undirected graphs that we call street networks. Then, protesters are biased random walkers on this network. They move from node to node following simple rules that we detail in next section.

## 2.1 Street networks

In order to model real-world cities, we leverage OpenStreetMap data and the OSMnx library [4]. For a given city, we use this library with its default settings to extract the graph $G = (V, E)$ defined as follows: the nodes in $V$ represent street intersections in this city and the links in $E \subseteq V \times V$ represent the pieces of streets that exist between them. The graph $G$ is undirected, meaning there is no distinction between $(u, v)$ and $(v, u)$ in $E$. In addition, we denote by $N(v) = \{u, (u, v) \in E\}$ the set of neighbors of any node $v$ in $V$.

We performed experiments on a wide set of large worldwide cities of diverse sizes and structures. This led to no significant difference on obtained results. We therefore use a typical instance, namely Paris, to present our work in this paper. This street network has 9602 nodes, 14974 links, leading to average degree 3.1. Its diameter is 83 hops and its average distance is 39.4 hops. The average street length is 99 meters, and the average distance is 5552 meters.

## 2.2 Walkers

Given a network $G = (V, E)$, we consider a set $W$ of walkers numbered from 1 to $|W|$. We denote the location of walker $i$ at time $t$ by $x_i(t) = v$, with $v \in V$. At each time step $t$, walker $i$ moves to node $x_i(t+1) \in N(v)$. Rules we present in the following sections determine the choice of $x_i(t+1)$.
* *Attraction.* The walker preferably moves to nodes where there are already many walkers: the criterion is equal to the number of walkers $n_w(t)$.

* *Follow.* The walker preferably follows the most popular moves of other walkers: the criterion has value $J_{v \to w}(t)$.

* *Alignment.* The walker takes into account the net flux in both directions: the criterion is equal to $\Delta J_{v \to w}(t) = J_{v \to w}(t) - J_{w \to v}(t)$.

## 3.3 Walking rules

Let us consider a criterion $C_{u,v,w}(t)$. We define the corresponding walking rule using the classical *logit rule*. It gives the probability $\omega_{u,v,w}^C(t)$ that walker $i$ moves from $v$ to $w$, given the fact that it arrived at $v$ from $u$:

$$ \omega_{u,v,w}^C(t) = \frac{e^{\beta \cdot C_{u,v,w}(t)}}{\sum_{z \in N(v)} e^{\beta \cdot C_{u,v,z}(t)}} \quad (1) $$

Parameter $\beta \ge 0$ is the intensity of choice: it quantifies the influence of the criterion on walker choices. If $\beta = 0$, the criterion has no influence and walkers make purely random choices. If $\beta \to \infty$ walkers necessarily choose a neighbor among the ones that maximize the criterion.

This logit equation is widely used in the literature because it has many convenient features [5]. In particular, it ensures $\omega$ is a positive and monotonic function of the criterion: the greater $C_{u,v,w}(t)$, the greater the chances to move to node $w$ at time $t$. It is also compatible with criteria having both positive and negative values, like the flux-based one below.

We conducted experiments with other functions with similar properties to equation 1. They displayed no significant differences.

## 3.4 Tactics

A *tactic* is a linear combination of walking rules that defines the probability $\pi_{u,v,w}(t)$ to move from $v$ to one of its neighbors $w$ when coming from $u$:

$$ \pi_{u,v,w}(t) = \sum_{C \in \mathcal{C}} \alpha_C \cdot \omega_{u,v,w}^C(t) \quad (2) $$

where $\alpha_C$ is the coefficient of criterion $C$, with $\sum_{C \in \mathcal{C}} \alpha_C = 1$. Therefore, a tactic is defined by a set of criteria and their coefficients.

We call *strict tactic* one that has all its coefficients, except one, set to zero and then always follows the same criterion.

In practice, at each time step, each walker selects a criterion $C$ with probability $\alpha_C$. Then, it computes its probability $\omega_{u,v,w}^C$ to go to each neighbor node $w$ and selects its new location accordingly.

Notice that we may see a tactic as an inhomogeneous Markov chain, where transition probabilities are time-dependent. Still, at any given time, each walker makes a transition from its current state $(u, v)$ giving its previous location $u$ and its current location $v$, to its next state $(v, w)$ giving its current location $v$ and its next location $w$.

As transition probabilities at time $t$ depend on previous non-deterministic moves, formal analysis of such processes is generally out of reach [6]. We will therefore explore possible tactics using simulations.

## 3.5 Baseline

In addition to the tactics above, we consider a reference baseline that easily achieves flocking thanks to collective decisions. This means that, at each time step, all walkers at a given node make the same choice. We then obtain reference results that we expect our walker models to reach or outperform, even though they are unable to make collective decisions.

More formally, for each node $v$ at time $t$, a unique random neighbor $u$ of $v$ is chosen and all walkers $i$ such that $x_i(t) = v$ move to $u = x_i(t + 1)$. This is equivalent to purely random walks of groups until they meet another group.

Since we consider non-bipartite connected graphs, it is well known that all groups will eventually merge. The number of needed steps is called the coalescence time [7]. Even though this number may be prohibitive, this means that the baseline successfully produces large groups. In addition, groups are mobile since, once formed, they perform purely random walks. As a consequence, this baseline makes a relevant reference for the success of flocking walkers.

# 4 Experiments

We seek to design good tactics for our walkers. They must produce flocking faster than the baseline presented in Section 3.5. Moreover, we want to obtain short time convergence, as our walkers model the action of protesters that can not walk forever. In this Section we define metrics to evaluate how well walkers flock. We then run simulations for a reasonable duration and evaluate which tactics have performed the best in this time interval.

## 4.1 Flocking metrics

We characterize *flocking* as a gathering of walkers exploring the network. With notations of Section 2.2, this leads to the two following score definitions for a given run of a given tactic.
For any link $(u, v)$ in $E$, we also define the *flux* of walkers from $u$ to $v$ as $J_{u \to v}(t) = |\{i, x_i(t-1) = u, x_i(t) = v\}|$. We call *group* the set of walkers at a given node $v$ at a given time $t$: $g_v(t) = \{i, x_i(t) = v\}$. We denote by $n_v(t) = |g_v(t)|$ the number of walkers located at node $v$ at time $t$. We denote by $g(t) = |\{g_v(t), v \in V, g_v(t) \neq \emptyset\}|$ the number of non-empty groups at step $t$.

## 2.3 Discretization

The links of a street network generally represent street segments of very heterogeneous lengths [26]. Then, moving from an intersection to another one may have very different durations. In order to model this, we use a classical discretization procedure [28] that we describe below. It consists in splitting each link of the street network into pieces connected by evenly spaced nodes. We illustrate this in Figure 2.

More formally, given a link $(u, v)$ representing a piece of street of length $L$ in a street network and a discretization step $\delta$, we split each undirected link $(u, v)$ into $k$ new links, with $k = \lfloor \frac{L}{\delta} \rfloor$ as follows. We define a set of new nodes $V(u, v) = \{w_0, w_1, \dots, w_k\}$, the nodes from the original network being $w_0 = u$ and $w_k = v$. We also define a set of new links $E(u, v) = \{(w_i, w_{i+1}), i = 0, 1, \dots, k-1\}$. Then we define the set of all nodes $V = \cup_{u,v} V(u, v)$ and the set of links $E = \cup_{u,v} E(u, v)$. Finally, we model the street network by the graph $G = (V, E)$.

<figure><img src="image_4.png" /><figcaption>Figure 2: A piece of the discretized street network around Place de la Nation in Paris.</figcaption></figure>

In the obtained graph, each link represents a street slice of length close to $\delta$. Then, the walkers defined in previous section consistently make a move of length approximately $\delta$ at each time step. In this paper, we use $\delta$ equal to 10 meters, leading to a network of $n = 130\,276$ nodes and $m = 300\,736$ links for
**Definition 4.1** (cluster, gathering score $\rho(t)$). A cluster is a maximal connected sub-graph with walkers on all its nodes. The gathering score $\rho(t)$ is the average number of walkers in clusters.

For example, when every agents are in the same cluster, $\rho(t) = |W|$. If instead all agents are in different ones, it equals 1.

**Definition 4.2** (mobility score $\mu(t)$). The mobility $\mu_i(t)$ of walker $i$ is the number of distinct nodes a walker has already visited at time $t$: $\mu_i(t) = |\{v, \exists t' \le t, x_i(t') = v\}|$. The mobility score $\mu(t)$ is the average walker mobility: $\mu(t) = \frac{1}{|W|} \sum_{i \in W} \mu_i(t)$.

Notice that the mobility score is monotonically non-decreasing with time: $\mu(t+1) \ge \mu(t)$. In addition, if all walkers move to a node they already visited then $\mu(t+1) = \mu(t)$.

We are interested in tactics with high gathering and mobility scores. Indeed, the high gathering score ensures that walkers form significant groups. In addition, the high mobility score implies that walkers continue to move. However, the fact that the gathering score remains high shows that walkers stay grouped. This means that the tactic successfully achieves flocking.

In order to gain more insight on group structure and dynamics, we introduce an additional metric.

**Definition 4.3** (sprawling score $\sigma(t)$). The sprawling score $\sigma(t)$ is the average number of nodes in clusters.

If the sprawling score is 1, all groups are isolated from each other: whenever walkers are at a node, there is no walker on neighbor nodes. If instead the sprawling score is high, walkers form large clusters of neighbor groups. Its largest possible value is the total number of nodes in the network, meaning that there are walkers on each node.

We are interested in tactics with low sprawling score, meaning that they succeed in merging neighbor groups.

## 4.2 Behaviors on a single street

Our networks are essentially composed of streets, modeled as lines of nodes by the discretization presented in Section 2.3 (Figure 2). This plays an important role in walker dynamics, therefore we investigate this special case in this Section.

Figure 3 shows space-time diagrams of three different strict tactics, i.e. the ones using only one rule, for 100 walkers on a line of 100 nodes. These space-time diagrams display the evolution of walker locations over time. The horizontal axis represents the nodes, numbered from 1 to 100. The vertical axis represents time steps,

<figure><img src="image_4.png" /><figcaption>Figure 3: Space-time diagrams of three tactics on a line using only (from left to right) the Random, Attraction, and Alignment rule. The gathering score is expressed relatively to the maximum number of walkers in a given run.</figcaption></figure>

numbered from 1 to 200. Then, the color at coordinates $(x, y)$ represents the number of walkers at node $x$ after $y$ time steps, namely $n_x(y)$. The color is white if this number is 0, and it is the darkest if this number is the maximal value for the considered run. Walkers are initially uniformly distributed on all nodes.

With the Random and with the Attraction strict tactic (Figure 3, left and middle), the largest obtained groups during the run both always contain less than 10 walkers (respectively 6 and 8 on the Figure) which never makes up to 5% of all walkers. However, the two tactics have distinct behaviors: while the Random one leads to walker constantly moving between groups, the Attraction one leads to stable groups. These groups fail to move along the line, though.

With Alignment (Figure 3, right), a more interesting pattern emerges: all walkers gather into a unique cluster that achieves flocking since it moves all along the line.

In conclusion, the Alignment strict tactic is sufficient to obtain flocking on a street. However, the groups we obtain eventually reach the street extremities, which raise the question of their behavior at street intersections.

## 4.3 Extensive exploration of tactics

In this Section, we follow an extensive method to explore the wide set of possible tactics on an entire city network:

* we consider the Paris street network discretized with parameter $\delta = 10$ meters, leading to a network of $N = 145000$ nodes and $M = 300736$ links,

* we consider $N$ walkers initially distributed uniformly at random in the network,

* we perform 1000 time steps, thus considering reasonably short walks of approximately 10 kilometers,

* we set $\beta$ large enough to ensure that each
Paris. It gives a sufficient precision in our context, and experiments with other
reasonable values of $\delta$ displayed no significant difference.

# 3 Tactics

At each time step $t$, each walker $i$ moves from location $x_i(t)$ to location $x_i(t+1)$ in $N(x_i(t))$. This section presents how we choose the new location $x_i(t+1)$.

## 3.1 Available information

We assume that walkers have very limited capabilities: they have no access to the actual location of other walkers, even on neighbor nodes, and they have no long-term memory and no communication protocol. Instead, we assume they only have access to estimates of aggregated observables, such as the number of walkers on neighbor nodes and the flow intensity on surrounding links, and a very short-term memory.

More formally, walker $i$ may use the following information at time $t$:

* its previous location $x_i(t-1)$,

* the number $n_v(t)$ of walkers on node $v$ for all $v$ in $N(x_i(t)) \cup \{x_i(t)\}$,

* the flux of walkers arriving and leaving its current location $v = x_i(t)$, i.e. $J_{u \to v}(t)$ and $J_{v \to u}(t)$ for all $u$ in $N(v)$.

Thanks to the information above, each walker $i$ knows its previous location $u = x_i(t-1)$, its current location $v = x_i(t)$, and it has access to various criteria to decide its next location $w = x_i(t+1)$. Then, it needs a way to derive walking rules from criteria, and a way to combine these walking rules into a tactic.

## 3.2 Criteria

A criterion is a parameter from which we construct walking rules. We consider the following set of criteria $C$.

* *Random.* The walker makes no difference between all possible neighbors: the criterion has value 1 for each of them.

* *Propulsion.* The walker never goes back to its previous location $u$, and otherwise makes random moves: the criterion has value 0 for $u$ and value 1 for other neighbors of $v$.

* *Attraction.* The walker preferably moves to nodes where there are already many walkers: the criterion is equal to the number of walkers $n_w(t)$.

* *Follow.* The walker preferably follows the most popular moves of other walkers: the criterion has value $J_{v \to w}(t)$.

* *Alignment.* The walker takes into account the net flux in both directions: the criterion is equal to $\Delta J_{v \to w}(t) = J_{v \to w}(t) - J_{w \to v}(t)$.
<figure><img src="image_5.png" /><figcaption>Figure 4: Gathering and mobility of all tactics. Each dot corresponds to the average last step value from ten runs of a tactic. The horizontal axis gives the gathering score, the vertical one gives the mobility score. From left to right and from top to bottom: tactics based mostly on the Random, Alignment, Attraction, Propulsion and Follow rule, respectively. On each of these plots, we indicate the strict tactic, that exclusively uses the corresponding rule. The bottom-right plot corresponds to tactics with no prevailing rule.</figcaption></figure>

walking rule strictly follows its criterion,

* we finally consider all tactics obtained as combinations of $\alpha_C$ parameter values from 0 to 1 by steps of 0.1 such that $\sum_{C \in C} \alpha_C = 1$.

With this setup, we obtain 1001 different tactics. We run 10 simulations of each tactic and we plot the average mobility and gathering scores in Figure 4. In these plots, each dot corresponds to a tactic defined by a set of $\alpha_C$ parameter values. We split these tactics into six plots: we display a set of tactics on the same plot if they all have $\alpha_C > 0.5$ for the same criterion C, and we display on the last plot the set of all other tactics.

We also display in each plot of Figure 4 a vertical and an horizontal line that indicate baseline results. Then, the tactics achieving the best flocking performances are the ones in the upper right corner: they obtain groups bigger and are more mobile than the baseline.

<figure><img src="image_6.png" /><figcaption>Figure 5: Plots showing the evolution of gathering and mobility scores for the strict tactics and the best tactic. Gathering score is in log-log scale.</figcaption></figure>

We pay particular attention to strict tactics, which performances are spotted by red dots in Figure 4. We also highlight what we identify as the best tactic regarding our scores. It is the tactic with the highest gathering score among tactics that outperform our baseline. We display the evolution of mobility and gathering scores over time for these tactics in Figure 5.

All strict tactics have very poor scores, except the Alignment one. This is a consequence from our previous Section results, where it was the only to generate large and mobile groups. Other strict tactics failed to achieve those patterns in a street, and therefore fail on an entire city.

Attraction, Follow and Random strict tactic have almost no dynamic as walkers do not explore much the network and do not form large groups. Propulsion however displays an excellent mobility score with an almost linear growth on Figure 5, as walkers never go back to their previous location.

Figure 4 clearly shows that Alignment-based tactics (top center plot) outperform others. All other sets of tactics perform poorly, except a few tactics for which no rule weights up more than 50% (bottom right plot). These tactics actually also use Alignment rule, to a lesser extent. This identifies the Alignment rule as a key building block for flocking tactics.

## 4.4 Best tactics

We now focus on the two main tactics that achieve flocking: the Alignment strict tactic and the best tactic (the one that corresponds to the rightmost dot on Figure 4). Figure 5 displays their scores over time in green and purple colors, respectively.

The plots show that the mobility score of both tactics first rapidly grow, and that this growth significantly decreases over time. Even if these tactics are not as good as the Propulsion strict tactic regarding mobility, they have comparable performances for this metric.

Notice that the Propulsion strict tactic has very low gathering scores (Figure 5, left), which makes it an irrelevant tactic despite its mobil-
### 3.3 Walking rules

Let us consider a criterion $C_{u,v,w}(t)$. We define the corresponding walking rule using the classical *logit rule*. It gives the probability $\omega_{u,v,w}^C(t)$ that walker $i$ moves from $v$ to $w$, given the fact that it arrived at $v$ from $u$:

$$ \omega_{u,v,w}^C(t) = \frac{e^{\beta \cdot C_{u,v,w}(t)}}{\sum_{z \in N(v)} e^{\beta \cdot C_{u,v,z}(t)}} \quad (1) $$

Parameter $\beta \ge 0$ is the intensity of choice: it quantifies the influence of the criterion on walker choices. If $\beta = 0$, the criterion has no influence and walkers make purely random choices. If $\beta \to \infty$, walkers necessarily choose a neighbor among the ones that maximize the criterion.

This logit equation is widely used in the literature because it has many convenient features [6]. In particular, it ensures $\omega$ is a positive and monotonic function of the criterion: the greater $C_{u,v,w}(t)$, the greater the chances to move to node $w$ at time $t$. It is also compatible with criteria having both positive and negative values, like the flux-based one above.

We conducted experiments with other functions with these needed features; they led to no significant differences.

### 3.4 Rule aggregation

A *tactic* is a linear combination of walking rules that defines the probability $\pi_{u,v,w}(t)$ to move from $v$ to one of its neighbors $w$ when coming from $u$:

$$ \pi_{u,v,w}(t) = \sum_{C \in \mathcal{C}} \alpha_C \cdot \omega_{u,v,w}^C(t) \quad (2) $$

where $\alpha_C$ is the coefficient of criterion $C$, with $\sum_{C \in \mathcal{C}} \alpha_C = 1$. Therefore, a tactic is defined by a set of criteria and their coefficients.

We call *strict tactic* one that has all its coefficients, except one, set to zero and then always follows the same criterion.

In practice, at each time step, each walker selects a criterion $C$ with probability $\alpha_C$. Then, it computes its probability $\omega_{u,v,w}^C$ to go to each neighbor node $w$ and selects its new location accordingly.

Notice that we may see a tactic as an inhomogeneous Markov chain, where transition probabilities are time-dependent. Still, at any given time, each walker makes a transition from its current state $(u, v)$ giving its previous location $u$ and its current location $v$, to its next state $(v, w)$ giving its current location $v$ and its next location $w$.

As transition probabilities at time $t$ depend on previous non-deterministic moves, formal analysis of such processes is generally out of reach [7]. We therefore explore possible tactics using simulations.
<figure><img src="image_7.png" /><figcaption>Figure 6: Plot showing the evolution of the sprawling scores for the strict tactics and the best tactic. Legend is the same as in Figure 5.</figcaption></figure>

ity score. Instead, both the Alignment strict tactic and the best static quickly reach excellent gathering scores. The best tactic significantly outperforms the Alignment strict tactic and has a linear gathering score plot in log-log scale. This means that its evolution has a polynomial growth (of exponent below 1), indicating a fast growth, but also that the evolution of group size tends to flatten over time. This is due to groups reaching a state where all clusters of groups are in distant regions of the network. Then, it takes longer for groups to meet other groups, merge, and grow in size.

Finally, Figure 6 displays the sprawling score for all considered tactics. We observe that the best tactic produces a greater sprawling score than Alignment. The sprawling, for those two tactics, is due to groups following each other when they detect another group on a neighbor node, without necessarily merging with it.

With the Alignment strict tactic, the sprawling of groups first very quickly increases, then decreases and stabilizes. This is because this tactic forms groups immediately at the beginning, mostly as lines of walkers following each other. The sprawling reduces as groups reach intersections and split, until the aggregation and splitting dynamics reach an equilibrium.

For the best tactic, groups aggregate into lines for a longer time period, resulting into a much higher sprawling score. It then slowly linearly decreases until the end of the run. This is because the Attraction rule, when chosen in the best tactic, will make the front group wait for the groups behind it, leading to less sprawled clusters.

As explained in Section 4.1, an efficient tactic should have a low sprawling score. The sprawling of the baseline is 1 (up to the third digit), thanks to the collective decision. This is the optimum value.

Our walkers do not have access to collective decision. When a cluster of groups arrives at an intersection, at the end of a street, it can split into multiple groups. In the case of a lone group

<figure><img src="image_8.png" /><figcaption>Figure 7: Schematic configurations that walkers, groups and clusters of groups achieve with the best tactics.</figcaption></figure>

(a cluster with no sprawling) it will split into multiple groups, with equal number of walkers on average. This reduces the gathering score.

However, with a larger sprawling, a cluster keeps most of its groups unchanged after an intersection. Indeed, the first of its groups to reach the intersection node might split into multiple groups, as described above. However, if using an Alignment-based tactic, next walkers will then all follow the biggest of the new groups that came from the split. This shows an effective tactic can benefit from a little bit of sprawling to maintain its clusters size.

## 4.5 Interpretation

Recall that the best tactic corresponds to the rightmost dot among those in the upper right corner of plots in Figure 4. It is defined by the following parameters: {$α_{follow} = 0.1, α_{align} = 0.8, α_{attr} = 0.1$} and a null weight for other rules. This tactic produces groups of 121 walkers on average, and walkers explore on average 540 distinct nodes during their 1000 steps. These scores are more than twice and five times more than what the baseline gets, respectively.

Figure 7 illustrates the behavior of this tactic. First, Alignment imposes walkers to move forward, may they be alone or part of a cluster, as shown in the first configuration of Figure 7. Indeed, a walker *i* alone at location $x_i(t) = u$ and $x_i(t-1) = v$ will measure a negative flux $\Delta J_{u \to v}(t) = -1$ at time *t*, while it will be $\Delta J_{u \to w}(t) = 0$ for all *w* ≠ *v*. This implies the walker never goes back. This effect is left unchanged with multiple walkers in a cluster.

Second, this same rule guarantees that, if two groups cross path, they then merge in a single cluster in which all walkers will follow the same path. Indeed when a group *u* cross path with a smaller group *v*, we have $x_i(t+1) = x_j(t)$ and $x_j(t+1) = x_i(t)$ for all $i \in g_u(t)$ and all $j \in g_v(t)$. The net flux is then $\Delta J_{u \to v}(t) = n_u(t) - n_v(t) > 0$ for all walkers, which drive them all
## 3.5 Baseline

In addition to the tactics above, we consider a reference baseline that easily achieves flocking thanks to collective decisions. This means that, at each time step, all walkers at a given node make the same choice. We then obtain reference results that we expect our walker models to reach or outperform, even though they are unable to make collective decisions.

More formally, for each node $v$ at time $t$, a unique random neighbor $u$ of $v$ is chosen and all walkers $i$ such that $x_i(t) = v$ move to $u = x_i(t + 1)$. This is equivalent to purely random walks of groups until they meet another group.

Since we consider non-bipartite connected graphs, it is well known that all groups will eventually merge. The number of needed steps is called the coalescence time [11]. Even though this number may be prohibitive, this means that the baseline successfully produces large groups. In addition, groups are mobile since, once formed, they perform purely random walks. As a consequence, this baseline makes a relevant reference for the success of flocking walkers.

## 3.6 Flocking metrics

In order to evaluate tactics, we need metrics describing how well walkers flock. We characterize flocking as a gathering of walkers that keep exploring the network.

This leads to the following score definitions for a given run of a given tactic. First, to measure the efficiency of a tactic for exploration, we define the mobility score.

**Definition 3.1.** The mobility $\mu_i(t)$ of walker $i$ is the number of distinct nodes a walker has already visited at time $t$: $\mu_i(t) = |\{v, \exists t' \le t, x_i(t') = v\}|$. The mobility score $\mu(t)$ is the average walker mobility: $\mu(t) = \frac{1}{|W|} \sum_{i \in W} \mu_i(t)$.

Notice that the mobility score is monotonically non-decreasing with time and bounded by the number of nodes: $|V| \ge \mu(t+1) \ge \mu(t)$. In addition, if at time $t$ all walkers move to a node they already visited then $\mu(t+1) = \mu(t)$.

Second, we need a way to evaluate the ability of walkers to gather. The trivial approach consists in observing the average group size, a group being the set of walkers located at a same node. However, this makes no difference between two groups on neighbor nodes and two groups at very distant nodes. We therefore introduce the more advanced notion of clusters.

**Definition 3.2.** We call cluster a maximal connected sub-graph with walkers on all its nodes. The node-size and the walker-size of a cluster is the total number of nodes involved in the cluster, and the total number of walkers on these nodes, respectively.

If all walkers are in the same cluster then the average walker-size of clusters is $\gamma(t) = |W|$. If instead all walkers are in different clusters, then the average walker-size of clusters is $\gamma(t) = 1$. However, if there is a unique walker at each node of the considered graph, then there is a unique cluster and it contains all
in the same direction: the smaller group goes back towards *v* (where it came from) while the trajectory of the largest group is left unchanged.

However, this rule alone is not perfectly ef-
fective at avoiding splitting. The walkers in the
first group in a cluster will not always all choose
the same node at an intersection, as illustrated
in the two bottom pictures of Figure 7, as the
different possible nodes all have a flux equal to 0.

In this context, the Attraction rule allows
walkers that split in the least chosen direction at
an intersection to go backward and avoid loosing
sight of the cluster.

Finally, the Follow rule improves the gathering. Indeed, clusters of groups tend to sprawl when walkers use the Alignment rule. In such chain of groups following each others, the Follow rule allows walkers in the front group to move backwards, merging with the group behind them, while it forces walkers in other groups to move forward to catch up the leading group.

This equilibrium between those three rules
gives an outcome where groups flock very effi-
ciently.

Figure 7 also shows why the baseline is not
good enough: walkers do not move forward at
every step. However we could obtain this with a
collective propulsion (a collective decision with
the Propulsion rule instead of the Random one),
such tactic neither guaranty groups merge when
they cross path. That is the strength of Align-
ment rule: walkers merge not only if they fall on
the same cell, but also if they simply exchange
their position.

4.6 Group robustness

It is crucial for protesters to form groups that re-
sist adversary forces that may break them up. In
order to explore this robustness, we model break
ups as walkers suddenly following the Random
strict tactic for one step. In this way, a group lo-
cated at a given node splits into smaller groups
that move to neighbor nodes, in a way similar
to a group of protesters targeted by adversary
forces.

More formally, we perform the following ex-
periment: we run the Alignment strict tactic for
100 steps, then we run the Random strict tactic
for one step, and we finally run the Alignment
strict tactic again. We perform the same exper-
iment with the best tactic (Section 4.5) instead
of the strict Alignment one.

Figure 8 displays the average observed scores
over ten runs of each experiment, together with
results of the same experiments without the
Random strict tactic step. Since the mobility
score is trivially increased by these experiments,
which brings no useful insight, we do not display
this metric.

<figure><img src="image_9.png" /></figure>

Figure 8: Plots of robustness experiments, sim-
ilar to Figure 5. We display the sprawling and
gathering scores for the Alignment strict tactic
and the best tactic, as well as for the experi-
ments where all walkers perform a random move
at time 100.

The break up simulation clearly appears on
both plots. The gathering score plots show that
large groups reappear shortly after break ups.
The two tactics do not have the same behaviour,
though. The strict Alignment tactic needs some
time to reach gathering scores close to its pre-
break up ones (green curve in Figure 8). Instead,
the best tactic is strikingly efficient in quickly
recovering from break ups. Indeed, large groups
do not only reappear shortly after the break up,
they do so even faster than before. This brings
its gathering score (black curve in Figure 8) to
quickly catch up with the case with no break up
(purple curve).

We also observe that, before going back to
normal, the sprawling score experiences a sharp
increase immediately followed by a sharp de-
crease. The increase is due to the fact that
groups in each cluster first split into several
neighbor groups, thus forming a larger cluster.
Then, the new groups tend to go forward, due
to the Alignment rule, and so they move away
from each other forming separate clusters. Once
again, this metric shows in Figure 8 that the best
tactic recovers faster than the Alignment strict
tactic.

5 Related work

First notice that our work is not concerned with
the modeling of actual pedestrian behaviours
and trajectory planning [8, 9, 10]. Instead, our
goal is to design simple tactics that lead to tar-
geted features, like flocking.

Likewise, our approach is different from usual
protest models based on thresholds [11] or agent-
based [12, 13, 14] approaches. Indeed, these
works focus on how people decide to participate
to a protest; they do not deal with protester mo-
bility.
walkers. Then, the average walker-size of clusters is maximal, despite the fact
that there is actually no significant group and no gathering. This is why we
need to consider both the walker- and node-size of clusters, which lead to the
following definition of gathering and sprawling scores.

**Definition 3.3.** The *gathering score* $\gamma(t)$ is the average cluster walker-size at time $t$. The *sprawling score* $\sigma(t)$ is the average cluster node-size at time $t$.

We are interested in tactics that lead to high gathering and mobility scores,
but low sprawling scores. Indeed, a high gathering score together with a low
sprawling score ensure that walkers form significant clusters: many walkers are
grouped on a small set of close nodes. A high mobility score implies in addition
that walkers continue to move. Therefore, the combination of such scores ensures
that walkers move in groups, which means that the tactic successfully achieves
flocking.

# 4 Exploration of tactics

We seek good tactics for our walkers. In particular, we seek tactics that produce
flocking comparable to the baseline presented in previous section. Moreover, we
want to obtain short time convergence, as our walkers model protesters that
cannot walk forever.

This section presents a wide set of simulations for realistic walk durations
and explores which tactics perform best. We consistently provide interpretations
of observed results and we deepen the study of the most effective tactics.

## 4.1 Behaviors on a single street

Our networks are composed of streets modeled as lines of nodes by the discretization presented above, see Figure 2. This plays an important role in walker dynamics, therefore we first detail this special case in this section.

Figure 3 displays *space-time* diagrams of three different strict tactics, i.e. the ones using only one rule, for 100 walkers on a line of 100 nodes. These space-time diagrams display the evolution of walker locations over time. The horizontal axis represents the nodes, numbered from 1 to 100. The vertical axis represents time steps, numbered from 1 to 200. Then, the color at coordinates $(x, y)$ represents the number of walkers at node $x$ after $y$ time steps, namely $n_x(y)$. The color is white if this number is 0, and it is the darkest if this number is the maximal value for the considered run. Walkers are initially uniformly distributed on all nodes.

With the Random and with the Attraction strict tactics (Figure 3, left and
middle), the largest obtained groups during the run both always contain less
than 10 walkers (respectively 6 and 8 on the Figure) which never makes up to
10% of all walkers. However, the two tactics have distinct behaviors: while the
Random one leads to walker constantly moving between groups, the Attraction
one leads to stable groups. These groups fail to move along the line, though.
<table><caption>Table 1: Important models of collective walks found in literature that provide solutions to problems similar to ours. The ● specifies if they succeed at solving one of the issues we deal with.</caption><thead><tr><th>Models</th><th>Network</th><th>Lattice</th><th>Flocking</th><th>Fast</th></tr></thead><tbody><tr><td>Random walk [15]</td><td>●</td><td>●</td><td></td><td></td></tr><tr><td>UTS/UXS [16, 17]</td><td>●</td><td>●</td><td></td><td></td></tr><tr><td>EAW [18]</td><td>●</td><td>●</td><td></td><td>●</td></tr><tr><td>SIP [19]</td><td></td><td>●</td><td></td><td></td></tr><tr><td>MIPS [20]</td><td></td><td>●</td><td></td><td></td></tr><tr><td>Boids [21]</td><td></td><td></td><td>●</td><td>●</td></tr><tr><td>Cucker-Smale [22]</td><td></td><td>●</td><td>●</td><td>●</td></tr><tr><td>Robot swarm [23, 24]</td><td></td><td></td><td>●</td><td>●</td></tr><tr><td>SVM [25, 26]</td><td></td><td>●</td><td>●</td><td>●</td></tr><tr><td>Our work</td><td>●</td><td>●</td><td>●</td><td>●</td></tr></tbody></table>

## 5.1 Walks on networks

Instead, a number of works deal with flocking behaviors of walkers in a variety of situations. We summarize their relevant features in Table 1. It shows the limits of these works from our perspective. We discuss them in the following.

In distributed systems, computer scientists proposed solutions to gathering problems where walkers follow a common distributed algorithm to meet on any connected graph [27, 28, 29]. In a sense, the main algorithms (UTS and UXS in Table 1) [16, 17] from this community are similar tactics to our baseline, except they are deterministic.

It is important to note that labeling nodes, and letting walkers have the global knowledge to know all labels, are essential in their protocols. Moreover those studies only look for guaranties regarding gathering at long time. Unlike those, we had to ensure our walkers gather sufficiently fast and with no need for hard computations.

## 5.2 Flocking in free space

Flocking is a collective dynamic where groups of walkers move spontaneously in the same direction [22, 30]. Ranging from swarms to pedestrian crowds, numerous articles explored this behavior, in free space, since the Boids model [21]. The work of Vicsek [25] notably settled that alignment and noise were sufficient to produce flocking in the plan (SVM in Table 1). The combination of alignment and attraction is also an effective way to get gathering and flocking [31], as attraction avoids sprawling. Robot swarms also achieve flocking and similar objectives to ours [23]. However, that last example often uses the local communication model that exceeds our walkers capabilities.

In our case, trajectories of walkers are network constrained. As we are not in free space we could not, in a simple manner, define a notion of direction to describe walkers motion in a structure as loose as a graph (except for a lattice where you can define pairs of right/left, top/bottom direction).

That is why we introduced instead the mobility score in Section 4.1.

## 5.3 Flocking and networks

Research on flocks and networks mostly do not study walks on graphs. They study the proximity graph of walkers: the graph of which walkers are in sight of another walker [32]. Researchers then study guaranties regarding the connectivity of this graph to evaluate if walkers achieve flocking.

However, a few articles explore flocking on simple networks. The motivation, in the context of statistical physics, is to use lattices as an approximation of free space to study active particles [20]. For example, in [26] the authors implement rules similar to ours to study the possible outcomes of their combinations on a line. They get results very similar to ours from Section 2.1. We also note that our baseline from Section 3.5 is very similar to the simple inclusion process (SIP in Table 1) [19].

We can also cite algorithms that solve problems very close to ours on a network. There is [33] that studies the reciprocal problem of completely scattering walkers over a graph, while they are all gathered on a single node at the beginning. There is also the edge ant walk (EAW in Table 1) [18], a bio-inspired model, where walkers communicate by leaving a trace of their passage, that can be used to patrol a graph.

Still, to our knowledge, we are the first to experiment rules for flocking that we can apply on any network. Such gap exists in the literature as such dynamic is not meaningful on many complex networks. Those often exhibit small-world and hub properties, making it very easy to gather fast when simply hopping from a high degree node to another at each step. Moreover, as phenomena in free spaces inspire flocking models, existing algorithms are then usually designed for application in free space and not on networks.

# 6 Conclusion

This paper proposes a framework for exploring what basic rules are crucial for walkers to gather and flock in a street network. Our findings indicate that the Alignment strict tactic is sufficient for flocking on a network. Alignment-based tactics are the most effective, and obtained groups are robust to break ups.

This framework is very general and may be extended in several ways. First, the city modelling may be improved with more urban data. For instance, one may use street width information to estimate the number of protesters needed to block each street. One may also use such data,
<figure><img src="image_5.png" /><figcaption>Figure 3: Space-time diagrams of three strict tactics on a line using only (from left to right) the Random, Attraction, and Alignment rule. The fraction of walkers is the relative size of groups with respect to the maximum number of walkers in a group in a given run.</figcaption></figure>

With Alignment (Figure 3, right), a more interesting pattern emerges: all walkers gather into a unique group that achieves flocking since it moves all along the line.

In conclusion, the Alignment strict tactic is sufficient to obtain flocking on a street. However, the groups we obtain eventually reach the street extremities, which raises the question of their behavior at street intersections.

## 4.2 Extensive exploration

In this section, we use an extensive method to explore the wide set of possible tactics on an entire city network:

* we consider the Paris street network discretized with parameter $\delta = 10$ meters, leading to a network of $n = 130276$ nodes and $m = 300736$ links,

* we consider a set $W$ of $|W| = n$ walkers initially distributed uniformly at random in the network,

* we perform 1000 time steps, thus considering reasonably short walks of approximately 10 kilometers at most,

* we consider all tactics obtained as combinations of $\alpha_C$ parameter values from 0 to 1 by steps of 0.1 such that $\sum_{C \in C} \alpha_C = 1$,
as well as point-of-interest (POI) information, such as the presence of restaurants, stores, or theaters around protesters, to design more effective walking rules. Last but not least, this work opens the way to studying how obtained walks impact the underlying street network and traffic taking place on it.

## Code and data.

We provide an implementation of our models in C, and a Python code result analysis: https://github.com/K-avi/protesting_on_graphs. We describe how to use it, including how to generate the obtained dataset, on the companion site: https://k-avi.github.io/protesting_on_graphs.

## Acknowledgements

We warmly thank Ivan Mulot-Radojcic for his help with implementation and documentation. This work is funded in part by the ANR (French National Agency of Research) through the FiT-ANR-19-LCV1-0005 grant and by the CNRS through the MITI interdisciplinary programs.

## References

[1] Steve Coast. Openstreetmap, 2004.

[2] Geoff Boeing. OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. 65:126–139.

[3] Adolfo Paolo Masucci, Duncan Smith, Andrew Crooks, and Michael Batty. Random planar graphs and the london street network. *The European Physical Journal B*, 71:259–271, 2009.

[4] Izaak Neri, Norbert Kern, and Andrea Parmeggiani. Totally asymmetric simple exclusion process on networks. *Physical review letters*, 107(6):068702, 2011.

[5] Jean-Philippe Bouchaud. Crises and collective socio-economic phenomena: simple models and challenges. *Journal of Statistical Physics*, 151:567–606, 2013.

[6] Pierre Brémaud. *Markov chains: Gibbs fields, Monte Carlo simulation, and queues*, volume 31. Springer Science & Business Media, 2001.

[7] Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on connected graphs. *SIAM Journal on Discrete Mathematics*, 27(4):1748–1758, January 2013.

[8] Thibault Bonnemain, Matteo Butano, Théophile Bonnet, Iñaki Echeverría-Huarte, Antoine Seguin, Alexandre Nicolas, Cécile Appert-Rolland, and Denis Ullmo. Pedestrians in static crowds are not grains, but game players. *Physical Review E*, 107(2):024612, 2023.

[9] Raphael Korbmacher, Alexandre Nicolas, Antoine Tordeux, and Claudia Totzeck. Time-continuous microscopic pedestrian models: an overview. *Crowd Dynamics, Volume 4: Analytics and Human Factors in Crowd Modeling*, pages 55–80, 2023.

[10] Serge P Hoogendoorn and Piet HL Bovy. Pedestrian route-choice and activity scheduling theory and models. *Transportation Research Part B: Methodological*, 38(2):169–190, 2004.

[11] Mark Granovetter. Threshold models of collective behavior. *American journal of sociology*, 83(6):1420–1443, 1978.

[12] Joshua M Epstein. Modeling civil violence: An agent-based computational approach. *Proceedings of the National Academy of Sciences*, 99:7243–7250, 2002.

[13] Carlos Lemos, Helder Coelho, Rui J Lopes, et al. Agent-based modeling of social conflict, civil violence and revolution: State-of-the-art-review and further prospects. *EU-MAS*, pages 124–138, 2013.

[14] Michele Agamennone. *Riots and Uprisings: Modelling Conflict between Centralised and Decentralised Systems*. PhD thesis, King's College London, 2021.

[15] Naoki Masuda, Mason A. Porter, and Renaud Lambiotte. Random walks and diffusion on networks. 716–717:1–58.

[16] Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In *20th Annual Symposium on Foundations of Computer Science (sfcs 1979)*. IEEE, October 1979.

[17] Michal Koucký. Universal traversal sequences with backtracking. *Journal of Computer and System Sciences*, 65(4):717–726, December 2002.

[18] Vladimir Yanovski, Israel A Wagner, and Alfred M Bruckstein. A distributed ant algorithm for efficiently patrolling a network. *Algorithmica*, 37:165–186, 2003.
* finally, we set $\beta$ large enough to ensure that each walking rule strictly follows its criterion. Indeed, in the following experiments, lowering this value only worsened gathering scores, as it is equivalent to adding noise to walkers choices.

With this setup, we obtain 1001 different tactics. We run 10 simulations of each tactic and plot the average mobility and gathering scores in Figure 4. In these plots, each dot corresponds to a tactic, defined by a set of $\alpha_C$ parameter values. We split these tactics into six plots: we display a set of tactics on the same plot if they all have $\alpha_C > 0.5$ for the same criterion C, and we display on the last plot the set of all other tactics.

We also display in each plot of Figure 4 vertical and a horizontal lines that indicate baseline results. Then, the tactics achieving the best flocking performances are the ones in the upper right corner: they obtain larger and more mobile groups than the baseline.

We pay particular attention to strict tactics, which performances are spotted by red dots in Figure 4. We also highlight what we identify as the best tactic regarding our scores. It is the tactic with the highest gathering score among tactics that outperform our baseline. For more insight, we display the evolution of mobility, gathering and sprawling scores over time for these tactics in Figure 5.

First notice that all strict tactics have very poor scores, except the Alignment one. This is a consequence of our previous section results, where it was the only one that generates large and mobile groups. Other strict tactics failed to achieve those patterns in a street, and therefore fail on an entire city.

Attraction, Follow and Random strict tactic have almost no dynamic, as walkers do not explore much the network and do not form large groups. Propulsion however displays an excellent mobility score with an almost linear growth on Figure 5, as walkers never go back to their previous location.

Note that tactics in the scatter plot (Figure 4) are not uniformly distributed. Indeed, no tactic has gathering and mobility scores such that its corresponding dot would be in the bottom right corner of the plot. This shows that a high mobility score is a necessary condition to achieve a high gathering score, but it is not sufficient.

Figure 4 clearly shows that Alignment-based tactics (top center plot) outperform others. All other sets of tactics perform poorly, except a few tactics for which no rule weights up more than 50% (bottom right plot). These tactics actually also use Alignment rule, to a lesser extent. This identifies the Alignment rule as a key building block for flocking tactics.

## 4.3 Best tactics

We now focus on the two main tactics that achieve flocking: the Alignment strict tactic and the best tactic (the one that corresponds to the rightmost dot on Figure 4). Figure 5 (left and center) displays their scores over time in green and purple colors, respectively.
[19] Stefan Grosskinsky, Frank Redig, and Kia-mars Vafayi. Condensation in the inclusion process and related models. *Journal of Statistical Physics*, 142:952-974, 2011.

[20] Michael E Cates and Julien Tailleur. Motility-induced phase separation. *Annu. Rev. Condens. Matter Phys.*, 6(1):219-244, 2015.

[21] Craig W Reynolds. Flocks, herds and schools: A distributed behavioral model. In *Proceedings of the 14th annual conference on Computer graphics and interactive techniques*, pages 25-34, 1987.

[22] Felipe Cucker and Steve Smale. Emergent behavior in flocks. *IEEE Transactions on Automatic Control*, 52(5):852-862, May 2007.

[23] Marco Dorigo, Guy Theraulaz, and Vito Trianni. Swarm robotics: Past, present, and future [point of view]. *Proceedings of the IEEE*, 109(7):1152-1165, 2021.

[24] Ahmad Reza Cheraghi, Asma Ben Janete, and Kalman Graffi. Robot swarm flocking on a 2d triangular graph. In *2020 5th Asia-Pacific Conference on Intelligent Robot Systems (ACIRS)*. IEEE, July 2020.

[25] Tamás Vicsek, András Czirók, Eshel Ben-Jacob, Inon Cohen, and Ofer Shochet. Novel type of phase transition in a system of self-driven particles. *Physical review letters*, 75(6):1226, 1995.

[26] JR Raymond and MR Evans. Flocking regimes in a simple lattice model. *Physical Review E*, 73(3):036112, 2006.

[27] Anders Dessmark, Pierre Fraigniaud, Dariusz R Kowalski, and Andrzej Pelc. Deterministic rendezvous in graphs. *Algorithmica*, 46:69-96, 2006.

[28] Andrzej Pelc. Deterministic rendezvous in networks: A comprehensive survey. *Networks*, 59(3):331-347, 2012.

[29] Subhash Bhagat and Andrzej Pelc. How to meet at a node of any connected graph. In *36th International Symposium on Distributed Computing (DISC 2022)*. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.

[30] R. Olfati-Saber. Flocking for multi-agent dynamic systems: Algorithms and theory. *IEEE Transactions on Automatic Control*, 51(3):401-420, March 2006.

[31] Aymeric Hénard, Jérémy Rivière, Etienne Peillard, Sébastien Kubicki, and Gilles Copin. A unifying method-based classification of robot swarm spatial self-organisation behaviours. *Adaptive Behavior*, 2023.

[32] Reza Olfati-Saber, J Alex Fax, and Richard M Murray. Consensus and cooperation in networked multi-agent systems. *Proceedings of the IEEE*, 95(1):215-233, 2007.

[33] Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Pająkowski, and Przemysław Uznański. Fast collaborative graph exploration. *Information and Computation*, 243:37-49, August 2015.
<figure><img src="image_6.png" /><figcaption>Figure 4: *Gathering and mobility scores of all tactics.* Each dot corresponds to the average last step value from ten runs of a tactic. The horizontal axis gives the gathering score, the vertical one gives the mobility score. From left to right and from top to bottom: tactics based mostly on the Random, Alignment, Attraction, Propulsion and Follow rule, respectively. On each of these plots, the red dot is for the strict tactic, that exclusively uses the corresponding rule. The bottom-right plot corresponds to tactics with no prevailing rule.</figcaption></figure>

The plots show that the mobility score of both tactics first rapidly grow, and
<figure><img src="image_7.png" /><figcaption>Figure 5: Plots showing the evolution of gathering, mobility and sprawling scores for the strict tactics and the best tactic. Gathering score is in log-log scale for readability.</figcaption></figure>

that this growth significantly decreases over time. Even if these tactics are not
as good as the Propulsion strict tactic regarding mobility, they have comparable
performances for this metric.

The Propulsion strict tactic has very low gathering scores (Figure 5, left), which makes it an irrelevant tactic despite its mobility score. Instead, both the Alignment strict tactic and the best static quickly reach excellent gathering scores. The best tactic significantly outperforms the Alignment strict tactic and has a linear gathering score plot in log-log scale. This means that its evolution has a polynomial growth (of exponent below 1), indicating a fast growth, but also that the evolution of group size tends to flatten over time. This is due to groups reaching a state where all clusters of groups are in distant regions of the network. Then, it takes longer for groups to meet other groups, merge, and grow in size.

Finally, Figure 5 (right) displays the sprawling score for all considered tac-
tics. We observe that the best tactic produces a greater sprawling score than
Alignment. The sprawling, for those two tactics, is due to groups following each
others when they detect another group on a neighbor node, without necessarily
merging with it.

With the Alignment strict tactic, the sprawling of groups first very quickly increases, then decreases and stabilizes. This is because this tactic forms groups immediately at the beginning, mostly as lines of walkers following each others. The sprawling reduces as groups reach intersections and split, until the aggregation and splitting dynamics reach an equilibrium.

For the best tactic, groups aggregate into lines for a longer time period,
resulting into a much higher sprawling score. It then slowly linearly decreases
until the end of the run. This is because the Attraction rule, when chosen in
the best tactic, will make the front group wait for the groups behind it, leading
to less sprawled clusters.

As explained when defining the metrics, an efficient tactic should have a low sprawling score. The sprawling of the baseline is 1 (up to the third digit), thanks to the collective decision. This is the optimum value.

Our walkers do not have access to collective decision, though. When a cluster of groups arrives at an intersection, at the end of a street, it may split into multiple groups. In the case of a lone group (a cluster with no sprawling) it will split into multiple groups, with equal number of walkers on average. This reduces the gathering score.

However, with a larger sprawling, a cluster keeps most of its groups unchanged after an intersection. Indeed, the first of its groups to reach the intersection node might split into multiple groups, as described above. However, if using an Alignment-based tactic, next walkers will then all follow the largest of the new groups that came from the split. This shows an effective tactic can benefit from a little sprawling to maintain its clusters walker-size.

## 4.4 Interpretation

Recall that the best tactic corresponds to the rightmost dot among those in the upper right corner of plots in Figure 4. It corresponds to the following parameters: {$α_{follow} = 0.1, α_{align} = 0.8, α_{attr} = 0.1$} and a null weight for other rules. This tactic produces groups of 121 walkers on average, and walkers explore on average 540 distinct nodes during their 1000 steps. These scores are more than twice and five times more than what the baseline gets, respectively.

<figure><img src="image_8.png" /><figcaption>Figure 6: Typical behaviors of walkers, groups and clusters of groups with the best tactic.</figcaption></figure>
Figure 6 illustrates the behavior of this tactic. First, Alignment imposes walkers to move forward, may they be alone or part of a cluster, as shown in the first configuration of Figure 6. Indeed, a walker *i* alone at location $x_i(t) = u$ and $x_i(t-1) = v$ will measure a negative flux $\Delta J_{u \to v}(t) = -1$ at time *t*, while it will be $\Delta J_{u \to w}(t) = 0$ for all $w \neq v$. This implies the walker never goes back. This effect is left unchanged with multiple walkers in a cluster.

Second, this same rule guarantees that, if two groups cross path, they then merge in a single cluster in which all walkers will follow the same path. Indeed, when a group *u* cross path with a smaller group *v*, we have $x_i(t+1) = x_j(t)$ and $x_j(t+1) = x_i(t)$ for all $i \in g_u(t)$ and all $j \in g_v(t)$. The net flux is then $\Delta J_{u \to v}(t) = n_u(t) - n_v(t) > 0$ for all walkers, which drive them all in the same direction: the smaller group goes back towards *v* (where it came from) while the trajectory of the largest group is left unchanged.

However, this rule alone is not perfectly effective at avoiding splitting. The walkers in the first group in a cluster will not always all choose the same node at an intersection, as illustrated in the two bottom pictures of Figure 6, as the different possible nodes all have a flux equal to 0.

In this context, the Attraction rule allows walkers that split in the least chosen direction at an intersection to go backward and avoid losing sight of the cluster.

Finally, the Follow rule improves the gathering. Indeed, clusters of groups tend to sprawl when walkers use the Alignment rule. In such chain of groups following each others, the Follow rule allows walkers in the front group to move backwards, merging with the group behind them, while it forces walkers in other groups to move forward to catch up the leading group.

This equilibrium between those three rules gives an outcome where groups flock very efficiently.

Figure 6 also shows why the baseline is not sufficient: it does not imply that walkers move forward at each step. One may try to improve this with a *collective propulsion* (a collective decision with the Propulsion rule instead of the Random one), but such a tactic would not ensure that groups merge when they cross each-other. This is where Alignment rule beats other approaches: walkers merge into a cluster not only if they arrive at the same node, but also if they are neighbors.

## 4.5 Group geography

In order to gain more insight on group formation, we display in Figure 7 the Paris street network for walkers following the Alignment strict tactic. We color nodes according to the group in which a walker that started there ends at the last step of the run. More precisely, we associate a color to each of the ten largest obtained groups. Then, for each walker that ends up in one of these groups, we color its initial location with the group color. The figure presents a typical output observed over many runs.

Figure 7 clearly shows that the walkers of a group come from a specific and limited region of the network. However these regions are rather wide, and a
group does not necessarily gather all walkers that are initially located in the region.

Interestingly, even if two walkers are initially very close, or even neighbors, they often do not end in the same group. As a consequence, the regions defined by groups are entangled, like in the east of Paris (Figure 7). This is a good feature in our context: it is hard for adversary forces to predict which group a protester will join from its initial position.

<figure><img src="image_9.png" /><figcaption>Figure 7: Discretized Paris street network with walkers following the Alignment strict tactic. We color in red the initial position of walkers that end up in the largest group at the end of the run. We do the same, with different colors, for the 10 largest groups at the end of a run.</figcaption></figure>

# 5 Robustness

It is crucial for protesters to form groups that resist adversary forces that may break them up. In order to explore this robustness, we model break ups as walkers suddenly following the Random strict tactic for one step. In this way, a group located at a given node splits into smaller groups that move to neighbor nodes, in a way similar to a group of protesters targeted by adversary forces.

More formally, we perform the following experiment: we run the Alignment strict tactic for 100 steps, then we run the Random strict tactic for one step, and we finally run the Alignment strict tactic again. We perform the same experiment with the best tactic (identified in previous sections) instead of the strict Alignment one.

Figure 8 displays the average observed scores over ten runs of each experiment, together with results of the same experiments without the Random strict tactic step. Since the mobility score is trivially increased by these experiments, which brings no useful insight, we do not display this metric.

The break up simulation clearly appears on both plots. The gathering score plots show that large groups reappear shortly after break ups. The two tactics
<figure><img src="image_10.png" /><figcaption>Figure 8: Plots of robustness experiments, similar to Figure 5. We display the sprawling and gathering scores for the Alignment strict tactic and the best tactic, as well as for the experiments where all walkers perform a random move at time 100.</figcaption></figure>

do not have the same behaviour, though. The strict Alignment tactic needs some time to reach gathering scores close to its pre-break up ones (green curve in Figure 8). Instead, the best tactic is strikingly efficient in quickly recovering from break ups. Indeed, large groups do not only reappear shortly after the break up, they do so even faster than before. This brings its gathering score (black curve in Figure 8) to quickly catch up with the case with no break up (purple curve).

We also observe that, before going back to normal, the sprawling score experiences a sharp increase immediately followed by a sharp decrease. The increase is due to the fact that groups in each cluster first split into several neighbor groups, thus forming a larger cluster. Then, the new groups tend to go forward, due to the Alignment rule, and so they move away from each other, forming distinct clusters. Then, like for the gathering score, the best tactic recovers strikingly well, and faster than the Alignment strict tactic.

# 6 Related work

Our work is not concerned with the modeling of actual pedestrian behaviours and trajectory planning [5, 20, 22]. Instead, our goal is to design simple tactics that lead to targeted features, like flocking.

Likewise, our work differs from protest models based on thresholds [17] or agent-based [1, 16, 21, 25] approaches. Indeed, these works focus on how people decide to participate in a protest; they do not deal with protester mobility.

Works in [8,24] are much closer to ours. Not only their protesters are mobile, but authors also study adversary forces. However, they focus on the strategy these forces should follow to control the crowd, whereas we are more interested
in protesters tactics.

Finally, a number of works deal with flocking behaviors of walkers in a variety of situations. We summarize their main features in Table 1 and show their limits from our perspective. We discuss them in more details below.

<table><caption>Table 1: Important models of collective walks found in literature that provide solutions to problems similar to ours. The • specifies if they succeed at solving one of the issues we deal with.</caption><thead><tr><th>Models</th><th>Network</th><th>Lattice</th><th>Flocking</th><th>Fast</th></tr></thead><tbody><tr><td>Random walk [27]</td><td>•</td><td>•</td><td></td><td></td></tr><tr><td>UTS/UXS [2, 23]</td><td>•</td><td>•</td><td></td><td></td></tr><tr><td>EAW [36]</td><td>•</td><td>•</td><td></td><td>•</td></tr><tr><td>SIP [18]</td><td></td><td>•</td><td></td><td></td></tr><tr><td>MIPS [9]</td><td></td><td>•</td><td></td><td>•</td></tr><tr><td>Boids [33]</td><td></td><td></td><td>•</td><td>•</td></tr><tr><td>Cucker-Smale [12]</td><td></td><td></td><td>•</td><td>•</td></tr><tr><td>Robot swarm [10, 15]</td><td></td><td>•</td><td>•</td><td>•</td></tr><tr><td>SVM [32, 34]</td><td></td><td>•</td><td>•</td><td>•</td></tr><tr><td><strong>Our work</strong></td><td>•</td><td>•</td><td>•</td><td>•</td></tr></tbody></table>

## 6.1 Walks on networks

First notice that our baseline is known as a coalescent random walk [11] and guarantees a non-deterministic gathering. In the field of distributed computing, researchers therefore proposed deterministic solutions for such gathering problems. Walkers then follow a common distributed algorithm to meet on any connected graph [3, 14, 31]. The main algorithms are UTS and UXS in Table 1 [2, 23].

In such works, labeling nodes during walks and knowledge of labels is in general crucial. Moreover the focus is on guarantees regarding long-term gathering. Instead, fast gathering is crucial in our context, as well as very limited memory and computation capacities.

Other works in this line focus on network exploration [35], and conclude that backtracking is to avoid, which we indeed observe with the high mobility score of the Propulsion rule.

## 6.2 Flocking in free space

Many papers explore flocking since the seminal Boids model [33]. These works typically consider bird swarms or pedestrian crowds that move in *free space*, like the continuous two-dimensional plane. Then, flocking means that a group of agents spontaneously move in the same *direction* [12, 29].

The work of Vicsek [34] (SVM in Table 1) notably established that alignment and noise are sufficient to produce flocking in the plan. The combination of
alignment and attraction is also an effective way to gather and flock [19], as attraction avoids sprawling.

Robot swarms often target objectives very similar to ours [15]. However, they generally use the *local communication model* that exceeds our walkers capabilities.

Our work differs from all these works by the fact that walkers move in a network, not in free space. Therefore, they do not have a readily usable notion of direction, except in very specific cases where the network is a lattice, for instance. This makes a big difference, and some of our moving criteria may be seen as extensions of free-space concepts to networks.

## 6.3 Flocking and networks

Papers on flocking and networks rarely study walks in networks. They typically focus on *proximity graphs* of walkers: the graph of which walkers (in free space) are in sight of each other [30]. Then, the connectivity of these graphs allows to evaluate if walkers achieve flocking.

Only a few papers are concerned with flocking in networks, but then the considered networks are in general very specific. The motivation typically is to use lattices to approximate free space and study active particles [9]. For instance, the authors of [32] explore rules similar to ours in order to study their combinations on a line. They get results similar to the ones we presented in the single street case.

Finally, some algorithms solve problems close to ours on a network. For instance, [13] studies the problem of scattering walkers over a graph, when they are initially all gathered at a single node. *Edge ant walk* (EAW in Table 1) [36] is a bio-inspired model where walkers communicate by leaving a trace of their passage, useable by other walkers. Such works require capacities that exceed the ones of our walkers.

# 7 Conclusion

This paper proposes a framework for exploring which basic rules are crucial for walkers to gather and flock in street networks. Our findings indicate that the Alignment strict tactic is sufficient for flocking. Combining Alignment with other tactics is even more effective, and obtained groups are very robust to break ups.

This raises many questions on group formation and dynamics over time, and on the role of street network properties in gathering and flocking. For instance, it is unclear why a group emerges at a specific location and gathers walkers from a specific region. Figure 7 is a first step in answering such questions, and it shows they are non-trivial.

Our framework may also be extended in several ways. For instance, the city modelling may be improved with more urban data, like street width or point-of-interest (POI) data (restaurants, stores, or theaters, e.g.). Such information
may be used by walkers, and they open the way to studies of the impact of
groups on network connectivity.

**Reproducibility.** We publicly provide all code and data used in this paper, our models in C and a Python code to analyse outputs: https://github.com/K-avi/protesting_on_graphs. We describe how to use it, including how to generate the obtained dataset, on the companion site: https://k-avi.github.io/protesting_on_graphs.

## Acknowledgements

We warmly thank Ivan Mulot-Radojcic for his help with implementation and documentation and Nicolas Maudet for his highly valuable feedbacks.

## References

[1] Michele Agamennone. *Riots and Uprisings: Modelling Conflict between Centralised and Decentralised Systems*. PhD thesis, King's College London, 2021.

[2] Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In *20th Annual Symposium on Foundations of Computer Science (sfcs 1979)*. IEEE, October 1979.

[3] Subhash Bhagat and Andrzej Pelc. How to meet at a node of any connected graph. In *36th International Symposium on Distributed Computing (DISC 2022)*. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.

[4] Geoff Boeing. Modeling and analyzing urban networks and amenities with osmnx. 2024.

[5] Thibault Bonnemain, Matteo Butano, Théophile Bonnet, Iñaki Echeverría-Huarte, Antoine Seguin, Alexandre Nicolas, Cécile Appert-Rolland, and Denis Ullmo. Pedestrians in static crowds are not grains, but game players. *Physical Review E*, 107(2):024612, 2023.

[6] Jean-Philippe Bouchaud. Crises and collective socio-economic phenomena: simple models and challenges. *Journal of Statistical Physics*, 151:567-606, 2013.

[7] Pierre Brémaud. *Markov chains: Gibbs fields, Monte Carlo simulation, and queues*, volume 31. Springer Science & Business Media, 2001.

[8] Bing Bu, Lei Wang, Zhenyang Pi, and Weiguo Fang. An extensive evolutionary mental game model for the mandatory evacuation of protesters by police. *IEEE Access*, 9:64468-64486, 2021.
[9] Michael E Cates and Julien Tailleur. Motility-induced phase separation. *Annu. Rev. Condens. Matter Phys.*, 6(1):219–244, 2015.

[10] Ahmad Reza Cheraghi, Asma Ben Janete, and Kalman Graffi. Robot swarm flocking on a 2d triangular graph. In *2020 5th Asia-Pacific Conference on Intelligent Robot Systems (ACIRS)*. IEEE, July 2020.

[11] Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on connected graphs. *SIAM Journal on Discrete Mathematics*, 27(4):1748–1758, January 2013.

[12] Felipe Cucker and Steve Smale. Emergent behavior in flocks. *IEEE Transactions on Automatic Control*, 52(5):852–862, May 2007.

[13] Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Pająk, and Przemysław Uznański. Fast collaborative graph exploration. *Information and Computation*, 243:37–49, August 2015.

[14] Anders Dessmark, Pierre Fraigniaud, Dariusz R Kowalski, and Andrzej Pelc. Deterministic rendezvous in graphs. *Algorithmica*, 46:69–96, 2006.

[15] Marco Dorigo, Guy Theraulaz, and Vito Trianni. Swarm robotics: Past, present, and future [point of view]. *Proceedings of the IEEE*, 109(7):1152–1165, 2021.

[16] Joshua M Epstein. Modeling civil violence: An agent-based computational approach. *Proceedings of the National Academy of Sciences*, 99:7243–7250, 2002.

[17] Mark Granovetter. Threshold models of collective behavior. *American journal of sociology*, 83(6):1420–1443, 1978.

[18] Stefan Grosskinsky, Frank Redig, and Kiamars Vafayi. Condensation in the inclusion process and related models. *Journal of Statistical Physics*, 142:952–974, 2011.

[19] Aymeric Hénard, Jérémy Rivière, Etienne Peillard, Sébastien Kubicki, and Gilles Coppin. A unifying method-based classification of robot swarm spatial self-organisation behaviours. *Adaptive Behavior*, 2023.

[20] Serge P Hoogendoorn and Piet HL Bovy. Pedestrian route-choice and activity scheduling theory and models. *Transportation Research Part B: Methodological*, 38(2):169–190, 2004.

[21] Jae-Woo Kim and Robert Hanneman. A computational model of worker protest. *Journal of Artificial Societies and Social Simulation*, 14(3):1, 2011.

[22] Raphael Korbmacher, Alexandre Nicolas, Antoine Tordeux, and Claudia Totzeck. Time-continuous microscopic pedestrian models: an overview. *Crowd Dynamics, Volume 4: Analytics and Human Factors in Crowd Modeling*, pages 55–80, 2023.
[23] Michal Koucký. Universal traversal sequences with backtracking. *Journal of Computer and System Sciences*, 65(4):717–726, December 2002.

[24] Tamsin E Lee. The thin blue line between protesters and their counter-protesters. *Journal of Artificial Societies and Social Simulation*, 21(2), 2018.

[25] Carlos Lemos, Helder Coelho, Rui J Lopes, et al. Agent-based modeling of social conflict, civil violence and revolution: State-of-the-art-review and further prospects. *EUMAS*, pages 124–138, 2013.

[26] Adolfo Paolo Masucci, Duncan Smith, Andrew Crooks, and Michael Batty. Random planar graphs and the london street network. *The European Physical Journal B*, 71:259–271, 2009.

[27] Naoki Masuda, Mason A. Porter, and Renaud Lambiotte. Random walks and diffusion on networks. 716–717:1–58, 2017.

[28] Izaak Neri, Norbert Kern, and Andrea Parmeggiani. Totally asymmetric simple exclusion process on networks. *Physical review letters*, 107(6):068702, 2011.

[29] R. Olfati-Saber. Flocking for multi-agent dynamic systems: Algorithms and theory. *IEEE Transactions on Automatic Control*, 51(3):401–420, March 2006.

[30] Reza Olfati-Saber, J Alex Fax, and Richard M Murray. Consensus and cooperation in networked multi-agent systems. *Proceedings of the IEEE*, 95(1):215–233, 2007.

[31] Andrzej Pelc. Deterministic rendezvous in networks: A comprehensive survey. *Networks*, 59(3):331–347, 2012.

[32] JR Raymond and MR Evans. Flocking regimes in a simple lattice model. *Physical Review E*, 73(3):036112, 2006.

[33] Craig W Reynolds. Flocks, herds and schools: A distributed behavioral model. In *Proceedings of the 14th annual conference on Computer graphics and interactive techniques*, pages 25–34, 1987.

[34] Tamás Vicsek, András Czirók, Eshel Ben-Jacob, Inon Cohen, and Ofer Shochet. Novel type of phase transition in a system of self-driven particles. *Physical review letters*, 75(6):1226, 1995.

[35] Shi-Jie Yang. Exploring complex networks by walking on them. *Physical Review E—Statistical, Nonlinear, and Soft Matter Physics*, 71(1):016107, 2005.

[36] Vladimir Yanovski, Israel A Wagner, and Alfred M Bruckstein. A distributed ant algorithm for efficiently patrolling a network. *Algorithmica*, 37:165–186, 2003.