BeWater: Effective Protesters Navigate Watersheds in Street Networks

1 Introduction

• BeWater addresses gathering without communication, mutual recognition, or a city map by leveraging features protesters observe nearby.The paper notes that carrying phones or recognizing fellow protesters could expose them to law enforcement, and streets may be closed.Source: §1 · p. 1
• Combining the right observables gathers protesters into groups large enough to perform significant actions.BeWater models sets of starting locations that lead walkers to the same group as watersheds.Source: §1 · p. 1

2 Data

• The study uses OpenStreetMap data and focuses on street length, name, lane count, speed limit, direction, and points of interest.The selected features are available for large-city streets, while features such as street width are often missing.Source: §2 · pp. 1–2

3 Street Networks and Observables

• Each link receives values for its street features, plus POI density and street area; walkers need only estimate which incident segments have maximal values.POI density is POI count divided by length, and street area is length multiplied by lane count.Source: §3 · p. 2
• Street direction is defined by whether building numbers increase or decrease along a link.This direction is used to distinguish ascending from descending movement.Source: §3 · p. 2
• Street links are split into slices of roughly equal length, with the original link’s observables copied to each slice.The experiments use δ = 10 meters; other reasonable values showed no significant difference.Source: §3 · pp. 2–3

4 Guiding example

• Large labeled nodes are crossings, smaller nodes are added by discretization, arrows show street direction, and colored numbers encode two observable weights.Green and red denote the first and second observables, respectively.Source: §4 · p. 3, Figure 2 · p. 3
• Discretization adds more street nodes to longer links, as illustrated by two nodes on D–E and five on A–C.The example's link lengths therefore affect how many slices appear between crossings.Source: §4 · p. 3
• The A–B street has green weight 3 and red weight 4, and those weights are retained across its four slices.The building-number arrow points from A toward B, with three added street nodes.Source: §4 · p. 3

5 Watershed Protocol

• BeWater walkers independently apply the same deterministic protocol using their current and previous locations, local observables, and street direction.The protocol is distributed, memoryless, and requires no synchronization.Source: §5 · pp. 3, 5
• At crossings, walkers follow a unique maximal-weight link, stop when several links tie for maximum, and may U-turn under the protocol’s direction rule.At street nodes, they continue forward; a walker starting on a street node first moves in the ascending direction.Source: §5 · pp. 3–4
• A walker running BeWater always stops after a finite number of steps.The proof rules out infinite repetition: a repeated crossing either triggers a stopping rule or would require a unique maximum to be exceeded.Source: §5 · p. 4
• Walkers on the same crossing node stay together in subsequent steps.The protocol is coalescent because walkers at a crossing have a unique possible next move.Source: §5 · p. 5

• The edge set E′ covers all possible walker moves, including maximum-link choices at crossings and allowed street-node transitions.Source: §6 · p. 5
• Each watershed-forest tree contains one unique sink, and its nodes form that sink’s watershed.Source: §6 · p. 5
• A cycle would require successive unique maxima to increase observable weight around the loop, contradicting the starting node’s unique maximum.Source: §6 · p. 5
• Forest components give the final group count, while their sizes give the group-size distribution, without running simulations.Source: §6 · pp. 5–6
• In the Paris example, the area observable produces 108 watersheds, and each of the 10 largest spans up to a dozen adjacent streets.Source: §6 · p. 6

• 3–4 times: area performs better than spe in watershed counts, and observable performance on one network tracks performance on the others.Source: §7 · p. 6, Table 1 · p. 6
• Length and area produce almost no Paris groups smaller than 10 walkers and several larger than hundreds, while most observables yield many groups under 50.Source: §7 · p. 6, Figure 4 · p. 6
• Up to 700 walkers: the largest watersheds reach that size, but poi’s largest group is followed by much smaller second and later groups than for other observables.Source: §7 · p. 7, Figure 5 · p. 7
• Lane, spe, and name mostly generate small watersheds; their narrow integer-valued weights create many tied maxima that rapidly stop walkers.Source: §7 · p. 7
• Len, area, poi, and den have more heterogeneous values, which are associated with much larger watersheds.Source: §7 · p. 7

8 Comparison to Baselines

• Artificial weights can form one group, while real-observable performance is closer to that of random observables.The artificial construction sends walkers along shortest paths to a central node; real-observable results are described as not far from random-observable performance.Source: §8 · pp. 7–8
• Across 100,000 random weight distributions, watershed counts cluster tightly around their mean, indicating stable performance across assignments.The expected count corresponds to the empirical mean, and the distribution has low variance.Source: §8 · p. 8, Figure 6 · p. 8
• Expected watershed counts from theory closely match experiments, and the regular-graph approximation is close to the exact expected value.Table 2 presents experimental results, theoretical predictions, and regular-graph approximations.Source: §8 · p. 8, Table 2 · p. 8
• Using only one real observable does not gather walkers effectively on street networks.The paper proposes combining observables to improve these results.Source: §8 · p. 8

9 BeWater

• Each walker runs the watershed protocol with observables in sequence, switching to the next observable when it reaches a sink.A procedure using a sequence of k observables is called a k-tactic.Source: §9 · p. 8
• In the guiding example, the sequence red–green–red yields one group, whereas green alone yields three and red alone yields two.The reverse ordering, green–red–green, yields two groups rather than one.Source: §9 · pp. 8–9
• Observable order matters: in the example, green–red–green produces two groups while red–green–red produces one.Single-observable tactics in the same example produce three groups with green and two with red.Source: §9 · pp. 8–9
• Adding an observable cannot increase the number of groups: each step may merge groups formed at earlier sinks but does not create new groups.The number of watersheds for a sequence is no greater than for its first observable alone.Source: §9 · p. 9

10 BeWater Baseline

• The baseline models each weight function in the sequence as a randomly generated observable.After the first i observables, the model treats the resulting groups as sinks for the next step.Source: §10 · p. 9
• The expected number of groups after each random observable is estimated by a recurrence based on the chance that its watersheds contain existing sinks.The estimate assumes the sinks are uniformly distributed and the next observable’s watersheds behave like uniformly sampled sets.Source: §10 · p. 9
• The random baseline eventually reaches a single group as the number of groups decreases and it ultimately samples the ideal baseline..Source: §10 · p. 9

11 Extensive Exploration

• The exploration searches combinations of observables to find tactics that perform well on a given street network.Different combinations can produce very different results.Source: §11 · p. 9
• A watershed forest for each observable is encoded in arrays and a sink list and computed in O(n+m) time and space.For a sequence, the method composes the observable mappings in O(k·n) time and space.Source: §11 · p. 9
• The method typically handles 100,000 combinations per minute and all 391,909 possible 7-tactics for considered cities in under 10 minutes.The paper considers these durations sufficient for its application area because longer sequences are difficult to remember and walk in practice.Source: §11 · pp. 9–10
• For a sequence of length k, the number of possible sequences is n·(2·n−1)^(k−1), where n is the number of observables.The next observable cannot be identical to the immediately preceding one.Source: §11 · p. 10

12 BeWater Performances

• In Paris, the best 7-tactic yields 37 groups, with groups three times larger than before.The sequence is S = {poi, lane, area, den, name, len, den}; Figure 7 depicts its watershed forest for the 11th arrondissement.Source: §12 · p. 10, Figure 7 · p. 10
• Best 7-tactics share similar observables across cities, but their order differs, so the best tactic is not universal.The reported comparison also finds poi absent and name present, despite name performing poorly as a 1-tactic.Source: §12 · p. 10
• The best k-tactic is generally not the best k−1 tactic with one added observable, reflecting complex watershed interactions.The optimal combination for a given k depends on interactions between watersheds.Source: §12 · p. 10
• Among the 1000 best 7-tactics per city, len is abundant and name often appears despite performing poorly alone.The frequency analysis also notes that len was only slightly better than other observables individually.Source: §12 · p. 10
• The random baseline performs better than BeWater, although BeWater improves as k increases.Figure 8 compares the number of groups, normalized by network size.Source: §12 · p. 10, Figure 8 · p. 11
• With their respective best 7-tactics, Paris forms almost twice fewer groups than Seattle relative to network size.The number of groups relative to network size varies greatly across cities.Source: §12 · pp. 10–11

13 Related Work

• Some graph-gathering protocols assume high computing capacity or graph marks, capabilities the authors regard as unrealistic for pedestrians.The cited approach is suitable for robots.Source: §13 · p. 11
• A street-network flocking approach relies on walkers recognizing one another, unlike the unrecognized, locally informed walkers considered here.The authors note protesters may not want to be recognized or may be unable to recognize others.Source: §13 · p. 11
• Pedestrian trajectory planning and protest participation models do not address the mobility of protesters as framed here.The paper states that it does not model actual pedestrian behavior or trajectory planning.Source: §13 · p. 11
• Related watershed-like structures appear in image processing, distributed minimum spanning tree computation, and geography, but those works do not study gathering mobile agents on them.Source: §13 · p. 11

14 Conclusion

• The paper formalizes a high-social-impact situation as a graph problem and proposes BeWater, a simple distributed gathering protocol for street networks.Walkers use local observables such as street area or point-of-interest density, which are accessible to pedestrians.Source: §14 · p. 11
• Experiments cover cities with different shapes and sizes.Source: §14 · p. 12
• BeWater’s efficiency depends on the chosen observable and its sequence order; future work could consider street width or node elevation.These features are not accessible in the OpenStreetMap dataset used here; the authors note elevation reflects geographical constraints.Source: §14 · p. 12
• The authors provide code and report that results are reproducible using open-access OpenStreetMap data and OSMnx.Source: §14 · p. 12