# Connecting Arrow’s Theorem, Voting Theory, and the Traveling Salesperson
Problem

Donald G. Saari  IMBS; University of California, Irvine
Irvine, California 92617-5100<EMAIL_ADDRESS>
###### Abstract.

Problems with majority voting over pairs as represented by Arrow’s Theorem and
those of finding the lengths of closed paths as captured by the Traveling
Salesperson Problem (TSP) appear to have nothing in common. In fact, they are
connected. As shown, pairwise voting and a version of the TSP share the same
domain where each system can be simplified by restricting it to complementary
regions to eliminate extraneous terms. Central for doing so is the Borda
Count, where it is shown that its outcome most accurately reflects the voter
preferences.

This paper is a written version of my 4/8/2022 JMM presentation; these results
provide applications of conclusions in [12, 13]. My thanks to George Hazelrigg
for our several discussions of these topics. This work is part of a National
Science Foundation project under NSF Award Number CMMI-1923164.

##  1\. Introduction

Among the many challenges posed by discrete mathematics and the Social
Sciences are aspects of voting theory as characterized by Arrow’s Theorem and
the properties of closed paths on a graph as typified by the Traveling
Salesperson Problem (TSP). Surprisingly, both topics can be analyzed with
essentially the same approach. After introducing the commonality with
examples, it is shown how each situation can be simplified by emphasizing
different regions of the associated geometry.

###  1.1. Voting theory and Arrow’s Theorem

Central to Arrow’s Theorem [1] is his IIA condition, which requires a
profile’s conclusion to be completely determined by the rankings of its
associated paired comparisons.111Even stronger, a decision method satisfies
“Independence of irrelevant alternatives,” IIA, iff it can be expressed in
terms of independent paired comparison methods [10, 11]. This means it is not
a negative feature if a decision method, such as the plurality vote, fails to
satisfy IIA; it only means that the method cannot be so expressed. Conversely,
any method that cannot be expressed in this manner does not satisfy IIA. Thus,
Arrow’s Theorem is a result about the problems that accompany paired
comparisons. A $N=70$ person majority vote example over the $n=3$ alternatives
$\\{A_{j}\\}_{j=1}^{3}$ is where

(1) $25\textrm{ prefer }A_{1}\succ A_{2}\succ A_{3},\,23\textrm{ prefer
}A_{2}\succ A_{3}\succ A_{1},\,22\textrm{ prefer }A_{3}\succ A_{1}\succ
A_{2}.$

This leads to the cyclic pairwise majority vote outcomes of

(2) $A_{1}\succ A_{2}\textrm{ by 47:23, }A_{2}\succ A_{3}\textrm{ by 48:22,
and }A_{3}\succ A_{1}\textrm{ by 45:25},$

which violate Arrow’s objective of obtaining a transitive conclusion. This
difficulty reflects the long-standing objective in voting theory, which is to
replace cyclic outcomes with appropriate transitive rankings, or at least with
outcomes that identify a “best choice.” Prominent approaches were developed by
the mathematicians Dodgson [2] in 1876 and Kemeny [3] in 1959.

A way to compare how an alternative fares in a paired comparison is to compute
how its tally differs from the average score of $\frac{\textrm{number of
voters}}{2}=\frac{N}{2}$. (In what follows, $N$ is the number of voters, $n$
is the number of alternatives.) So

(3) $d_{i,j}=\frac{1}{2}[A_{i}\textrm{'s tally}-A_{j}\textrm{'s
tally}]=A_{i}\textrm{'s tally}-\frac{N}{2}=-d_{j,i}.$

For the Eq. 2 values, where $N=70$ and $n=3,$

(4) $d_{1,2}=47-\frac{70}{2}=12=-d_{2,1},\,d_{2,3}=13=-d_{3,2},\textrm{ and
}d_{1,3}=-10=-d_{3,1}.$

###  1.2. TSP

To introduce the notation for the TSP system discussed here, it takes 30
minutes to walk from home, H, to campus, C, while returning uphill takes 40.
As the average is 35 minutes, returning home requires 5 minutes above the
average denoted by $C\stackrel{{\scriptstyle 5}}{{\longrightarrow}}H$;
traveling in the opposite direction takes 5 fewer minutes or
$H\stackrel{{\scriptstyle-5}}{{\longrightarrow}}C$. More generally, if
$d_{i,j}$ represents the “difference from the average” cost of going from
$A_{i}$ to $A_{j}$, then

(5) $A_{i}\stackrel{{\scriptstyle d_{i,j}}}{{\longrightarrow}}A_{j}\textrm{
and }A_{j}\stackrel{{\scriptstyle-d_{i,j}}}{{\longrightarrow}}A_{i}\textrm{
are equivalent},$

or, as true with Eq. 3,

(6) $d_{i,j}=-d_{j,i}.$

$A_{1}$3322$A_{6}$311$A_{2}$11082$A_{3}$1439$A_{4}$1$A_{5}$8Figure 1.
$\mathcal{G}_{A}^{6}$

Figure 1 is a typical TSP example, where the graph catalogues all “differences
from averages” information about the alternatives $\\{A_{j}\\}_{j=1}^{6}$ and
its ${6\choose 2}=15$ pairs. (Subscripts “$A$” and ‘$S$” refer, respectively,
to whether the graph has an asymmetric or a symmetric structure.) Only
positive cost directions are displayed because (Eqs. 5, 6) traveling counter
to an arrow is a negative, or below average cost. A standard TSP objective is
to discover the longest and shortest Hamiltonian circuits. To appreciate what
will be developed, before reading more, let me ask the reader to find the
longest such path in Fig. 1. Recall, a Hamiltonian circuit is a closed path
that starts and ends at a selected vertex $A_{j}$ and passes through each of
the other vertices once. To illustrate, the Fig. 1 Hamiltonian path

$A_{1}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle
11}}{{\longrightarrow}}A_{4}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}A_{6}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{3}\stackrel{{\scriptstyle-14}}{{\longrightarrow}}A_{5}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{1}$

has length $-2$, and its reversal has length $2.$ In fact, thanks to Eqs. 5,
6, the tasks of finding the longest and shortest Hamiltonian paths coincide;
the reversal of one is the other.

###  1.3. A common space

The voting and TSP questions involve the $n\choose 2$ pairs defined by $n$
alternatives where costs/differences between vertices of a $\\{i,j\\}$ pair
are measured by $d_{i,j}=-d_{j,i}$ values.222 Rather than “difference from
average,” $d_{i,j}$ can be anything; e.g., a natural choice is the difference
between $A_{i}$ and $A_{j}$ values. Thus, both settings share the
$\mathbb{R}_{A}^{n\choose 2}$ domain, where
$\mathbf{d}_{A}^{n}\in\mathbb{R}_{A}^{n\choose 2}$ has the form

(7)
$\mathbf{d}_{A}^{n}=(d_{1,2},d_{1,3},\dots,d_{1,n};d_{2,3},\dots,d_{2,n};d_{3,4}\dots;d_{n-1,n});\,d_{i,j}=-d_{j,i}.$

Semicolons indicate changes in the first subindex. The
$\mathbb{R}_{A}^{n\choose 2}$ structure is developed next.

To start, recall that if a triplet $\\{A_{i},A_{j},A_{k}\\}$ defines a
transitive ranking, it can be expressed with these $d_{s,u}$ values; e.g.,
should $d_{i,j}>0$ and $d_{j,k}>0$, then transitivity requires that
$d_{i,k}>0$. These inequalities are borrowed from the structure of points on a
line where $p_{i}>p_{j}$ and $p_{j}>p_{k}$ require $p_{i}>p_{k}$. But these
points also satisfy the stronger algebraic relationship
$(p_{i}-p_{j})+(p_{j}-p_{k})=(p_{i}-p_{k})$. The following mimics this
equality.

######  Definition 1.

[12] Vector $\mathbf{d}_{A}^{n}\in\mathbb{R}_{A}^{n\choose 2}$ is strongly
transitive iff each triplet $\\{i,j,k\\}$ satisfies

(8) $d_{i,j}+d_{j,k}=d_{i,k}.$

.

This condition was introduced for profiles in [9]; the decision theory version
used here comes from [12]. The subspace of strongly transitive vectors,
$\mathbb{ST}_{A}^{n}$, is described next.

######  Theorem 1.

[12] The set of strongly transitive
$\mathbf{d}_{A,st}^{n}\in\mathbb{R}_{A}^{n\choose 2}$, denoted by
$\mathbb{ST}^{n}$,333In [9, 14], $\mathbb{ST}_{A}^{n}$ is called the
“transitivity plane.” is a $(n-1)$-dimensional linear subspace of
$\mathbb{R}_{A}^{n\choose 2}$.

While details are in [12], proving that $\mathbb{ST}_{A}^{n}$ is a linear
subspace is a standard exercise. The assertion about its dimension follows
from the fact that any $d_{j,k}$ can be expressed as $d_{j,k}=d_{j,1}+d_{1,k}$
(Eq. 8), so all $d_{j,k}$ values for
$\mathbf{d}^{n}_{A,st}\in\mathbb{ST}^{n}_{A}$ can be determined from the
$(n-1)$ terms $\\{d_{1,s}\\}_{s=2}^{n}.$ $\square$

The dimensions of $\mathbb{R}_{A}^{n\choose 2}$ and $\mathbb{ST}_{A}^{n}$
dictate that $\mathbb{C}_{A}^{n}$, the orthogonal complement of
$\mathbb{ST}_{A}^{n}$, has dimension ${n-1}\choose 2$. To motivate the form of
these orthogonal vectors, expressing Eq. 8 as $x+y=z$, or $x+y-z=0$,
identifies $(1,1,-1)$ as a normal vector. Thus the $x=y=-z=1$ values define a
normal vector $d_{i,j}=d_{j,k}=d_{k,i}=1$, which is represented by the cyclic
$A_{i}\succ A_{j},\,A_{j}\succ A_{k},\,A_{k}\succ A_{i}$ where the differences
between values is the same constant.

######  Theorem 2.

[12] The ${n-1}\choose 2$ dimensional linear subspace $\mathbb{C}_{A}^{n}$
consists of cycles where one basis, which consists of three-cycles, is
$\\{\mathbf{d}^{n}_{1,j,k}\\}_{1<j<k\leq n}$. The only non-zero terms of
$\mathbf{d}^{n}_{1,j,k}$ are $d_{1,j}=d_{j,k}=d_{k,1}=1.$

According to these theorems, $\mathbb{R}_{A}^{n\choose 2}$ nicely separates
into linear subspaces of strongly transitive vectors, $\mathbb{ST}_{A}^{n}$,
and cyclic vectors, $\mathbb{C}_{A}^{n}$, where $\mathbb{C}_{A}^{n}$ has a
basis consisting of a special type of three-cycles. This means that
$\mathbf{d}^{n}_{A}\in\mathbb{R}_{A}^{n\choose 2}$ has a unique decomposition

(9) $\mathbf{d}^{n}_{A}=\mathbf{d}^{n}_{A,st}+\mathbf{d}^{n}_{A,cyclic}$

where $\mathbf{d}^{n}_{A,st}$ and $\mathbf{d}^{n}_{A,cyclic}$ are,
respectively, the orthogonal projection of $\mathbf{d}^{n}_{A}$ to
$\mathbb{ST}^{n}$ and $\mathbb{C}^{n}_{A}$.

An immediate consequence of Eq. 9 is that a transitive vector, which is not
strongly transitive, is a hybrid.

######  Corollary 1.

For $n\geq 3$, if $\mathbf{d}_{A}^{n}$ is transitive but not strongly
transitive, then there are unique non-zero vectors
$\mathbf{d}^{n}_{A,st}\in\mathbb{ST}_{A}^{n}$ and
$\mathbf{d}^{n}_{A,cyclic}\in\mathbb{C}_{A}^{n}$ so that
$\mathbf{d}_{A}^{n}=\mathbf{d}^{n}_{A,st}+\mathbf{d}^{n}_{A,cyclic}$.

What limits the use of transitive vectors is that they fail to define a linear
subspace. For instance, $d_{1,2}=d_{2,3}=2$, $d_{1,3}=1$ and
$d^{*}_{1,2}=d^{*}_{2,3}=-1$, $d^{*}_{1,3}=-2$ are transitive triplets, but
their sums (e.g., $d_{i,j}+d^{*}_{i,j}=d^{+}_{i,j})$ define the cyclic
$d^{+}_{1,2}=d^{+}_{2,3}=1$, $d^{+}_{1,3}=-1$. According to Cor. 1, it is
reasonable to treat a transitive vector as a strongly transitive choice that
is lightly contaminated with cyclic terms. The following theorem partly
explains the “lightly contaminated” modifier by showing that rankings of
transitive $\mathbf{d}_{A}^{n}$ and its strongly transitive component
$\mathbf{d}^{n}_{A,st}$ can differ, but not radically. This holds even for a
non-transitive $\mathbf{d}_{A}^{n}$ that has, at least, a Condorcet winner and
loser. (A Condorcet winner is a candidate who beats each of the other
candidates in majority vote comparisons. A Condorcet loser loses all pairwise
majority votes. They can exist even without transitivity; e.g., for $n=5,$
$A_{1}$ could be the Condorcet winner, $A_{5}$ the Condorcet loser, and
$A_{2},A_{3},A_{4}$ define a cycle.)

######  Theorem 3.

If $\mathbf{d}_{A}^{n}$ has a unique Condorcet winner $A_{1}$ and a unique
Condorcet loser $A_{n}$, then $A_{1}$ is strictly ranked above $A_{n}$ in
$\mathbf{d}^{n}_{A,st}$.

The converse is to determine what happens by adding cyclic terms to a
$\mathbf{d}^{n}_{A,st}.$ If the resulting $\mathbf{d}_{A}^{n}$ is wildly
cyclic, not much can be stated. But if $A_{1}$ and $A_{n}$ are, respectively,
the top and bottom ranked candidates of the $\mathbf{d}^{n}_{A,st}$ and if
$\mathbf{d}_{A}^{n}$ remains transitive, the question is whether $A_{1}$ must
be ranked above $A_{n}$ in
$\mathbf{d}_{A}^{n}=\mathbf{d}^{n}_{A,st}+\mathbf{d}^{n}_{A,cyclic}$. Proofs
of this kind of results can be messy. But to illustrate Thm. 2, the basic idea
is developed in Sect. 5 for $n=3,4$. The details of these proofs are similar
to earlier relationships that were developed about the Kemeny and paired
voting rankings relative to the Borda ranking [9, 14].

##  2\.  Voting Theory

As a central objective in voting and decision theory is to obtain transitive
outcomes, the cyclic components of $\mathbf{d}_{A}^{n}$ introduce problems. A
resolution is obvious; drop the troubling $\mathbf{d}^{n}_{A,cyclic}$ cyclic
term and retain only $\mathbf{d}^{n}_{A,st}$. Dodgson’s method partly does so
by replacing $\mathbf{d}_{A}^{n}$ with a vector that may have cyclic terms,
but at least it has a Condorcet winner. ($A_{j}$ is a Condorcet winner iff
$d_{j,k}>0$ for all $k\neq j$. That is, $A_{j}$ is “better than” all other
alternatives in paired comparisons.) Dodgson’s method [2], then, projects
$\mathbf{d}_{A}^{n}\in\mathbb{R}_{A}^{n\choose 2}$ to the nearest
$\mathbb{R}_{A}^{n\choose 2}$ subset where all vectors have a Condorcet
winner. For $n\geq 4$, these regions have cyclic components; e.g., for $n=4$,
the dimension of $\mathbb{ST}_{A}^{4}$ is only three, while the Condorcet
subset has the full ${4\choose 2}=6$ dimension. For instance, $A_{1}$ is the
Condorcet winner in the eight $\mathbb{R}_{A}^{6}$ orthants where
$d_{1,2}>0,d_{1,3}>0,d_{1,4}>0$. Without imposing restrictions on the signs of
$d_{2,3},d_{2,4},d_{3,4}$, cyclic behavior is allowed among
$\\{A_{2},A_{3},A_{4}\\}$.

Kemeny adopted the more ambitious goal [3] of replacing $\mathbf{d}_{A}^{n}$
with a transitive outcome. Similar to Dodgson, he created a projection mapping
that sends $\mathbf{d}_{A}^{n}$ into the nearest $\mathbb{R}_{A}^{n\choose 2}$
subset consisting of transitive outcomes.

Both methods provide electoral relief at a first level, but a deeper
investigation reveals a host of other subtle difficulties that cast doubt on
the reliability of these approaches. Important results in this direction were
found in a series of papers by Ratliff [4, 5, 6]. For instance, the above
“projection” descriptions makes it reasonable to expect that the Dodgson and
Kemeny outcomes are related; perhaps the Dodgson winner always is the top-
ranked Kemeny candidate. But Ratliff proved that, in general, such assertions
are false. A small sample of his findings follows.

######  Theorem 4.

[4, 5, 6] For $n\geq 4$ candidates, select an integer k, where $1\leq k\leq
n.$ There exist paired comparison examples where the Dodgson winner is the
$k^{th}$ ranked Kemeny winner.

Dodgson’s method can be generalized to select a committee of $k\geq 2$
candidates by using Dodgson’s projection method to a subset of
$\mathbb{R}_{A}^{n\choose 2}$ where all vectors have $k$ candidates where each
is ranked above the $(n-k)$ remaining candidates. For integers $k$ and $s$
satisfying $1\leq s<n-k,$ $k\neq s$, there exist examples where with the
Dodgson’s generalized approach, no candidate in the Dodgson committee of $s$
is in the Dodgson committee of $k$ candidates.

As Ratliff proved, rather than being top-ranked, the Dodgson winner can end up
being anywhere in a Kemeny outcome; it can even be bottom-ranked. Moreover,
the Dodgson winner need not be in a Dodgson-Ratliff committee of two or three.
These unexpected conclusions are consequences of the cyclic terms that remain
even after the Dodgson and Kemeny projections. For instance, unless Kemeny’s
outcome is strongly transitive, it contains cyclic components (Cor. 1) that
can create other difficulties.

Stated differently, the Dodgson and Kemeny procedures remove only as many of
the $\mathbf{d}_{A}^{n}$ cyclic components as needed to attain their
objectives. Without a thorough cleansing, it is reasonable to expect other
mysterious properties: this happens. This also holds for Arrow’s Theorem; its
negative conclusion is strictly a consequence of the
$\mathbf{d}_{A,cyclic}^{n}$ component. Completely removing
$\mathbf{d}_{A,cyclic}^{n}$ converts Arrow’s assertion into a positive result
[10, 11]. Indeed, the ultimate goal for decision and voting problems should be
to eliminate all cyclic components of a given $\mathbf{d}_{A}^{n}$. Doing so
is a common mathematical computation.

###  2.1. Orthogonal Projection

The standard way to eliminate the unwanted cyclic terms from a given
$\mathbf{d}_{A}^{n}$ is with the orthogonal projection

(10) $P:\mathbb{R}_{A}^{n\choose 2}\to\mathbb{ST}_{A}^{n}.$

The computations require finding a basis for $\mathbb{ST}_{A}^{n}$ (using Eq.
8) and carrying out the associated vector analysis. The resulting approach
follows; see [12] for details and examples.

######  Definition 2.

For alternative $A_{j}$, the weighted sum is

(11) $\mathcal{S}_{A}(A_{j})=\sum_{k=1}^{n}d_{j,k};\,j=1,\dots,n.$

With Eq. 4 values,

(12) $S_{A}(A_{1})=12-10=2,\,S_{A}(A_{2})=-12+13=1,\,S_{A}(A_{3})=-13+10=-3.$

######  Theorem 5.

[12] For $\mathbf{d}_{A}^{n}\in\mathbb{R}_{A}^{n\choose 2}$, the $d_{i,j}$
value in $\mathbf{d}^{n}_{A,st}$ is

(13) $d_{i,j}=\frac{1}{n}[\mathcal{S}_{A}(A_{i})-\mathcal{S}_{A}(A_{j})].$

Of surprise, this projection is equivalent to the well known Borda Count. This
Borda procedure tallies a $n$-candidate ballot by assigning $n-j$ points to
the $j^{th}$ ranked candidate. A candidate’s Borda tally,
$\mathcal{B}(A_{j})$, is the sum of points assigned to $A_{j}$ over all $N$
ballots. Using the Eq. 1 example,
$\mathcal{B}(A_{1})=25(3-1)+23(3-3)+22(3-2)=72$,
$\mathcal{B}(A_{2})=25(3-2)+23(3-1)+22(3-3)=71$, and
$\mathcal{B}(A_{3})=25(3-3)+23(3-2)+22(3-1)=67.$

######  Theorem 6.

[12] For any $n\geq 3$, the Eq. 10 orthogonal projection of
$\mathbf{d}_{A}^{n}\in\mathbb{R}_{A}^{n\choose 2}$ to $\mathbb{ST}_{A}^{n}$,
which is $\mathbf{d}^{n}_{A,st}$, is equivalent to the Borda Count. More
precisely,

(14) $\mathcal{B}(A_{j})=(n-1)\frac{N}{2}+S_{A}(A_{j}),\,j=1,\dots,n.$

and

(15)
$\mathcal{B}(A_{j})-\mathcal{B}(A_{k})=S_{A}(A_{j})-S_{A}(A_{k})=nd_{j,k}.$

Proof: As known (e.g., [8, 9, 10]), a way to compute $\mathcal{B}(A_{j})$ is
to sum $A_{j}$’s tallies over each of its $(n-1)$ majority vote paired
comparisons. (As an example, using the Eq. 2 tallies, in the
$\\{A_{1},A_{2}\\}$ and $\\{A_{1},A_{3}\\}$ elections, $A_{1}$ receives,
respectively, 47 and 25 votes; this $47+25=72$ value agrees with $A_{1}$’s
above computed $\mathcal{B}(A_{1})=72$.) According to Eq. 3,

(16) $\mathcal{B}(A_{j})=\sum_{k=1,k\neq
j}^{n}[d_{j,k}+\frac{N}{2}]=(n-1)\frac{N}{2}+S_{A}(A_{j}).$

Thus, for voting theory,
$S_{A}(A_{j})-S_{A}(A_{k})=\mathcal{B}(A_{j})-\mathcal{B}(A_{k}).$ $\square$

Theorem 6 has an interesting consequence. To set the stage, consider all of
those voting methods where the outcome is determined by assigning a score to
each candidate; e.g., this includes almost all standard methods such as all
positional methods, cumulative voting, Approval Voting, etc. As these scores
satisfy strong transitivity, the outcome is in $\mathbb{ST}^{n}_{A}$. A
natural objective is to have an outcome that most accurately reflects the
views (i.e., preferences) of the voters. That is, find the
$\mathbb{ST}^{n}_{A}$ outcome that is closest to the data, which is the
orthogonal projection of $\mathbf{d}_{A}^{n}$. This is equivalent to the Borda
Count (Thm. 6).

Combining comments from the above provide new explanations for earlier
results. For instance, the following, which has the spirit of Thm. 3, was
proved by using these tools.

######  Theorem 7.

[9, 14] For $n\geq 3$, Kemeny’s method ranks a Borda winner over the Borda
loser. Conversely, the Borda Count ranks a Kemeny winner over the Kemeny
bottom ranked candidate.

For paired comparison majority votes, the Borda outcome ranks the Condorcet
winner over the Condorcet bottom ranked candidate. Conversely, is the paired
comparisons define a transitive ranking, the Borda winner is ranked over the
Borda bottom ranked candidate.

The Kemeny outcome is a transitive vector, while the strongly transitive Borda
ranking comes from the orthogonal projection of $\mathbf{d}_{A}^{n}$ to
$\mathbb{ST}_{A}^{n}$. As Cor. 1 asserts, a transitive ranking is a strongly
transitive ranking clouded by cyclic terms, which captures the flavor of the
Kemeny outcome.

Theorem 6 provides an explanation why the Borda Count has so many positive
properties; examples with decision methods are in [12]. The following
completes the introductory comments about Arrow’s Theorem.

######  Theorem 8.

[8, 9] If $\mathbf{d}_{A}^{n}\in\mathbb{ST}_{A}^{n}$, then the Borda Count and
majority vote paired comparisons both satisfy Arrow’s Theorem. The Borda Count
is the only positional voting method that satisfies Arrow’s conditions.

The last assertion holds because the Borda Count is the only positional method
where its outcomes are determined by the outcomes of majority votes over
pairs. The outcome for all other positional methods need not be related, in
any manner, to the paired comparison outcomes [7].

##  3\. Turning to the TSP

According to Eq. 9, $\mathbf{d}_{A}^{n}\in\mathbb{R}^{n\choose 2}$ can be
uniquely expressed as
$\mathbf{d}_{A}^{n}=\mathbf{d}^{n}_{A,st}+\mathbf{d}^{n}_{A,cyclic}$, where
$\mathbf{d}^{n}_{A,st}\in\mathbb{ST}_{A}^{n}$ and
$\mathbf{d}^{n}_{A,cyclic}\in\mathbb{C}_{A}^{n}$. As described above, voting
and decision theories seek transitive outcomes, which means that the cyclic
$\mathbf{d}^{n}_{A,cyclic}$ component imposes obstacles. The natural
resolution is to eliminate $\mathbf{d}^{n}_{A,cyclic}$ and retain
$\mathbf{d}^{n}_{A,st}$ by projecting $\mathbf{d}_{A}^{n}$ into
$\mathbb{ST}_{A}^{n}.$

In contrast, TSP and other closed path concerns involve cycles, so the linear
behavior now is what creates barriers. This change in the objective converts
the strongly transitive $\mathbf{d}^{n}_{A,st}$ from being the desired
component into a troublemaker. Thus, to analyze TSP issues, mimic what was
done for voting by orthogonally projecting $\mathbf{d}_{A}^{n}$ into
$\mathbb{C}_{A}^{n}$ to eliminate the $\mathbf{d}^{n}_{A,st}$ term and retain
$\mathbf{d}^{n}_{A,cyclic}$.

What simplifies finding $\mathbf{d}^{n}_{A,cyclic}$ is that
$\mathbf{d}^{n}_{A,cyclic}=\mathbf{d}_{A}^{n}-\mathbf{d}^{n}_{A,st}$, and
$\mathbf{d}^{n}_{A,st}$, which is equivalent to the Borda Count (Thm. 6), is
easily computed (Thm. 5). The decomposition of the Fig. 1 graph is in Fig. 2
where the $\mathcal{G}^{6}_{A,cpi}$ and $\mathcal{G}^{6}_{A,cyclic}$ entries
represent, respectively, $\mathbf{d}^{6}_{A,st}$ and
$\mathbf{d}^{6}_{A,cyclic}.$

The computation of $\mathcal{G}^{6}_{A,cpi}$ follows from Def. 2 and Thm. 5.
For instance, $S_{A}(A_{1})=[-3+3+2-2+3]=3$ while
$S_{A}(A_{2})=[3+8+0+11+11]=33$, so
$d_{1,2}=\frac{1}{6}[S_{A}(A_{1})-S_{A}(A_{2})]=-5$ is the
$\mathbf{d}^{6}_{A,st}$ entry, which is the length of the $A_{1}\to A_{2}$ leg
in $\mathcal{G}^{6}_{cpi}.$ The cpi subscript of $\mathcal{G}^{6}_{A,cpi}$,
which means “closed path independent,” is described next.

$A_{1}$3322$A_{6}$311$A_{2}$11082$A_{3}$1439$A_{4}$1$A_{5}$8a.
$\mathcal{G}_{A}^{6}\approx\mathbf{d}_{A}^{6}$$A_{1}$5645$A_{6}$311$A_{2}$9082$A_{3}$1139$A_{4}$1$A_{5}$8=b.
$\mathcal{G}_{A,cpi}^{6}\approx\mathbf{d}^{6}_{A,st}$$A_{1}$2323$A_{6}$00$A_{2}$2000$A_{3}$300$A_{4}$0$A_{5}$0+c.
$\mathcal{G}_{A,cyclic}^{6}\approx\mathbf{d}^{6}_{A,cyclic}.$Figure 2.
Decomposition of a $\mathcal{G}_{A}^{6}$

Thanks to the linearity of the decomposition, the length of any closed path
(not just Hamiltonian circuits) in $\mathcal{G}^{6}_{A}$ equals the sum of the
path’s lengths in $\mathcal{G}^{6}_{A,cpi}$ and $\mathcal{G}^{6}_{A,cyclic}$.
As an example, the $-4$ length of the $\mathcal{G}_{A}^{6}$ closed path
$A_{1}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle
8}}{{\longrightarrow}}A_{6}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{3}\stackrel{{\scriptstyle-14}}{{\longrightarrow}}A_{5}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{1}$ equals the sum of its path’s lengths of
$A_{1}\stackrel{{\scriptstyle-5}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle
8}}{{\longrightarrow}}A_{6}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{3}\stackrel{{\scriptstyle-11}}{{\longrightarrow}}A_{5}\stackrel{{\scriptstyle
5}}{{\longrightarrow}}A_{1}$ in $\mathcal{G}^{6}_{A,cpi}$ and
$A_{1}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}A_{6}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}A_{3}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}A_{5}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}A_{1}$
in $\mathcal{G}^{6}_{A,cyclic}$. As this path’s length in
$\mathcal{G}^{6}_{A,cpi}$ is zero, its $-4$ length in
$\mathcal{G}^{6}_{A,cyclic}$ equals the $\mathcal{G}^{6}_{A}$ path length.
That this closed path in $\mathcal{G}^{6}_{A,cpi}$ has length zero is not a
lucky coincidence. Instead, all closed paths in $\mathcal{G}^{n}_{A,cpi}$ have
length zero, so these paths are “closed path independent” when computing
$\mathcal{G}^{6}_{A}$ path lengths.

######  Theorem 9.

For $n\geq 3$, a closed path in $\mathcal{G}^{n}_{A,cpi}$ has length zero. The
length of a closed path in $\mathcal{G}_{A}^{n}$ equals its length in
$\mathcal{G}^{n}_{A,cyclic}$.

The length of any $\mathcal{G}_{A}^{n}$ path starting at $V_{i}$ and ending at
$V_{j}$ equals its length in $\mathcal{G}^{n}_{A,cyclic}$ plus the $V_{i}\to
V_{j}$ length in $\mathcal{G}^{n}_{A,cpi}$.

The proof of the first assertion follows immediately from the strong
transitivity of the $\mathcal{G}^{n}_{A,cpi}$ components. To check that
$\mathcal{G}^{6}_{A,cpi}$ has this property, select any triplet from Fig.
2b—perhaps $\\{A_{1},A_{5},A_{3}\\}$; the goal is to show that
$d_{1,5}+d_{5,3}=d_{1,3}$. Fom $\mathcal{G}^{6}_{A,cpi}$, this requires
$d_{1,5}+d_{5,3}=-5+11$ to equal $d_{1,3}=6$, which it does.

Next, a standard induction exercise shows that if $\mathbf{d}_{A,st}^{n}$ is
strongly transitive, then any path from $A_{j}$ to $A_{k}$ has the same length
as the direct $A_{j}\to A_{k}$ path. Reversing this last arc creates a closed
path with length zero. The rest of the theorem follows immediately.

The last assertion of Thm. 9 requires the “-1” length of $\mathcal{G}^{6}_{A}$
path,

$A_{1}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle
11}}{{\longrightarrow}}A_{4}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{3}\stackrel{{\scriptstyle-11}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}A_{5},$

which skips $A_{6}$ but visits $A_{2}$ twice, to equal this path’s length in
$\mathcal{G}^{6}_{A,cyclic}$ plus $-5$. The $-5$ comes from the
$A_{1}\stackrel{{\scriptstyle-5}}{{\longrightarrow}}A_{5}$ arc in
$\mathcal{G}^{6}_{A,cpi}$ (Fig. 2b). This path’s length in
$\mathcal{G}^{6}_{A,cyclic}$ is

$A_{1}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{4}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}A_{3}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}A_{5}$

or 4, and, as Thm. 9 promises, $-1=4-5$.

###  3.1. Finding the longest and shortest Hamiltonian circuits

According to Thm. 9, the longest/shortest Hamiltonian path in
$\mathcal{G}^{6}_{A}$ (Fig. 2a) can be found by ignoring $\mathcal{G}^{6}_{A}$
and, instead, analyzing the reduced $\mathcal{G}^{6}_{A,cyclic}$ with its two
three-cycles (Fig. 3) $A_{1}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{5}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{3}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{1}$ and $A_{1}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{4}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{1}$. The obvious strategy is to use these cycles as
fully as possible. To avoid premature closure by returning to a previously
visited vertex, use at most two arcs of each three-cycle.

$A_{1}$3322$A_{6}$311$A_{2}$11082$A_{3}$1439$A_{4}$1$A_{5}$8$A_{1}$2$||$323$||$$A_{6}$00$A_{2}$2000$A_{3}$300$A_{4}$0$A_{5}$0$\to$Figure
3. Finding $\mathcal{G}_{A}^{6}$’s longest Hamiltonian circuit via
$\mathcal{G}^{6}_{A,cyclic}$.

Consequently, starting at $A_{1}$, use only the edges
$A_{1}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{5}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{3}$ from the first three-cycle; this is why
$A_{3}\stackrel{{\scriptstyle 3}}{{\longrightarrow}}A_{1}$ arc is crossed out
in Fig. 3. As only one arc can leave $A_{1}$, this eliminates the crossed-out
$A_{1}\stackrel{{\scriptstyle 2}}{{\longrightarrow}}A_{2}$ arc. Thus, the
Hamiltonian circuit depends upon the four bold $\mathcal{G}^{6}_{A,cyclic}$
arcs in Fig. 3. Finding the longest Hamiltonian circuit now is immediate—use
zero-length arcs to ensure all vertices are visited and to connect the two
basic ones. An answer is the Hamiltonian path

$(A_{1}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{5}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{3})\stackrel{{\scriptstyle
0}}{{\longrightarrow}}A_{6}\stackrel{{\scriptstyle
0}}{{\longrightarrow}}(A_{2}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{4}\stackrel{{\scriptstyle
2}}{{\longrightarrow}}A_{1})$

of length 10. The reversal of this closed path has length $-10$. It is clear
from the graph’s structure that these are the longest and shortest
$\mathcal{G}^{6}_{A,cyclic}$ Hamiltonian circuits, so (Thm. 3) they define the
longest and shortest $\mathcal{G}^{6}_{A}$ Hamiltonian circuits with the same
lengths.

To appreciate what is going on, notice that what complicates computing the
Fig. 2a path length $A_{5}\stackrel{{\scriptstyle
14}}{{\longrightarrow}}A_{3}\stackrel{{\scriptstyle-3}}{{\longrightarrow}}A_{1}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}A_{5}$
of $14-3-2=9$ are the subtractions/cancelations. To see what they are, let
$u$, $v$, and $w$ be the canceled terms, respectively, for arcs
$\widehat{A_{5}A_{3}},\widehat{A_{3}A_{1}}$, and $\widehat{A_{1}A_{5}}$. That
is, after cancellations, the path length computation would be
$(14-u)+(-3-v)+(-2-w)=9$ where $u+v+w=0$, which satisfies cpi from Eq. 8. That
is, the cancelations in computing closed path lengths are linear expressions
that define a $\mathbb{ST}_{A}^{n}$ graph. The optimal choice of cancelations
for a $\mathcal{G}^{n}_{A}$ is the $\mathbb{ST}_{A}^{n}$ graph that most
closely approximates $\mathcal{G}^{n}_{A}$, which is its orthogonal projection
into $\mathbb{ST}_{A}^{n}$, or $\mathcal{G}^{n}_{A,cpi}$. Indeed, with Fig.
2b, the optimal cancelation is from $\mathcal{G}^{6}_{A,cpi}$ where
$u+v+w=11-6-5=0.$ Removing these cancelations leaves
$\mathcal{G}^{6}_{A,cyclic}$ with the path length
$A_{5}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{3}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{1}\stackrel{{\scriptstyle
3}}{{\longrightarrow}}A_{5}$ of length $9$ where no modifications are needed
in the computations.

###  3.2. The symmetric case

For the standard symmetric TSP, the distance between vertices is the same in
each direction. Thus the $d_{i,j}=-d_{j,i}$ asymmetric condition is replaced
with the $d_{i,j}=d_{j,i}$ requirement. This requires a different
decomposition of the new $\mathbb{R}_{S}^{n\choose 2}$ where, with the
orthogonal projection, leads to a different type of inherent symmetries.
Otherwise, everything remains much the same. Of importance, the decomposition
provides a best possible simplification for closed paths. Details for the
general symmetric and asymmetric cases are given elsewhere [13], but a flavor
of what happens is described next.

A $n=6$ example is given in Fig. 4; recall, the S subscript in
$\mathcal{G}^{6}_{S}$ refers to “symmetric.” While a typical goal is to find
the shortest Hamiltonian circuit, everything extends to the analysis of any
path, whether closed or not.

$A_{1}$1534$A_{6}$17$A_{2}$7342$A_{3}$351$A_{4}$7$A_{5}$7Figure 4. A symmetric
$\mathcal{G}_{S}^{6}\in\mathbb{G}^{6}_{S}$

Central to the discussion is the average Hamiltonian path length in
$\mathcal{G}^{n}_{S}$ denoted by $T(\mathcal{G}^{n}_{S})$.

######  Definition 3.

For a graph $\mathcal{G}^{n}_{S}$, let $S_{S}(A_{j})$ be the sum of arc
lengths attached to vertex $A_{j}$, $j=1,\dots,n.$ Let
$T(\mathcal{G}^{n}_{S})=\frac{1}{n-1}\sum_{j=1}^{n}S_{S}(A_{j})$.

So $S_{S}(A_{j})$ (Def. 3) and $S_{A}(A_{j})$ (Eq. 2) are the same. That
$T(\mathcal{G}^{n}_{S})$ is the average Hamiltonian path length follows from
the fact that $\frac{1}{n-1}S_{S}(A_{j})$ is the average length of the $(n-1)$
arcs attached to $A_{j}$. Illustrating with Fig. 4,
$S_{S}(A_{1})=1+5+3+4+1=14,S_{S}(A_{2})=22,S_{S}(A_{3})=22,S_{S}(A_{4})=20,S_{S}(A_{5})=18,S_{S}(A_{6})=24$,
so $T(\mathcal{G}^{6}_{S})=\frac{1}{5}(120)=24.$ When considering non-
Hamiltonian closed paths, restrict the $S_{S}(A_{j})$ values and the summation
defining $T$ to the relevant arcs and vertices.

$A_{1}$1534$A_{6}$17$A_{2}$7342$A_{3}$351$A_{4}$7$A_{5}$7$\to$$A_{1}$-220.52$A_{6}$-2.52$A_{2}$2.5-1-1.5-2.5$A_{3}$-1-0.5-2.5$A_{4}$2$A_{5}$2.5+$T(\mathcal{G}^{6}_{S})$$\mathcal{G}_{S,cyclic}^{6}\in\mathbb{C}^{6}_{S}$$\mathcal{G}^{6}_{S,cyclic}$Figure
5. Decomposition of a $\mathcal{G}_{S}^{6}\in\mathbb{G}^{6}_{S}$

The scheme replaces entries of $\mathcal{G}^{n}_{S}$ with values that, after
removing irrelevant terms (which are similar to $\mathcal{G}^{n}_{A,cpi}$),
can be viewed as differences from the average arc length, as in Fig. 5. Thus
negative values represent “smaller than average” costs. The theorem is that
the length of a Hamiltonian circuit in $\mathcal{G}^{n}_{S}$ is the length of
its path in $\mathcal{G}^{n}_{S,cycle}$ plus $T(\mathcal{G}^{n}_{S})$.
Standard modifications handle paths that are not closed and/or incomplete
graphs.

Each $\mathcal{G}^{6}_{S,cyclic}$ vertex has an arc with negative (i.e., below
average) length; this assertion holds more generally for any
$\mathcal{G}^{n}_{S,cyclic}$. By observation and using arcs with negative
values as often as possible, an Hamiltonian path in
$\mathcal{G}^{6}_{S,cyclic}$ with shortest length of -11 is

(17)
$A_{1}\stackrel{{\scriptstyle-2.5}}{{\longrightarrow}}A_{6}\stackrel{{\scriptstyle-0.5}}{{\longrightarrow}}A_{3}\stackrel{{\scriptstyle-2.5}}{{\longrightarrow}}A_{4}\stackrel{{\scriptstyle-2.5}}{{\longrightarrow}}A_{5}\stackrel{{\scriptstyle-1}}{{\longrightarrow}}A_{2}\stackrel{{\scriptstyle-2}}{{\longrightarrow}}A_{1}.$

This defines the shortest Hamiltonian path in $\mathcal{G}^{6}_{S}$ with
length $24-11=13.$

In general, the shortest $\mathcal{G}^{n}_{S}$ Hamiltonian path is bounded
below by $T(\mathcal{G}^{n}_{S})$ plus the sum of the $n$ smallest
$\mathcal{G}^{n}_{S,cyclic}$ arc lengths. With $\mathcal{G}^{6}_{S}$, this is
$24+(-2.5-2.5-2.5-2-1.5-1)=12.$ This shortest Hamiltonian path length is
larger than, but close to, its lower bound.

Although the $\mathcal{G}^{6}_{S}$ entries can be random numbers, the
advantage of the $\mathcal{G}^{6}_{S,cyclic}$ entries is that each entry has a
meaning with respect to a path’s length. Thus, a way to find the shortest
Hamiltonian path is to rank the arcs according to length, where “smaller is
better.” Start with the first n arcs to determine whether they form a path. If
not, then iteratively add arcs to see whether it creates a Hamiltonian path.
To illustrate, the $\mathcal{G}^{6}_{S,cyclic}$ arcs with negative values are

(18)
$\begin{array}[]{c|ccc|c|cc}\textbf{Length}&\textbf{Arc}&\textbf{Arc}&\textbf{Arc}&\textbf{Length}&\textbf{Arc}&\textbf{Arc}\\\
\hline\cr-2.5&\widehat{A_{1}A_{6}},&\widehat{A_{3}A_{4}},&\widehat{A_{4}A_{5}}&-2&\widehat{A_{1}A_{2}}\\\
-1.5&\widehat{A_{2}A_{6}}&&&-1&\widehat{A_{3}A_{5}},&\widehat{A_{2}A_{5}}\\\
-0.5&\widehat{A_{3}A_{6}}\par\par\end{array}$

This array emphasizes using
$\widehat{A_{1}A_{6}},\,\widehat{A_{3}A_{4}},\widehat{A_{4}A_{5}},$ where
$\widehat{A_{3}A_{6}}$ forms a transition between the first and the second
arc, and $\widehat{A_{5}A_{2}}$ includes the missing $A_{2}$, while
$\widehat{A_{2}A_{1}}$ completes the journey. This is the Eq. 17 tour.

$\mathbb{ST}^{n}_{A}$; Voting$\mathbb{C}^{n}_{A}$: TSP and
graphs$\bullet$$\mathbf{d}_{A}^{n}\in\mathbb{R}_{A}^{n\choose 2}$Borda
outcome$\mathcal{G}^{n}_{A,cyclic}$Figure 6. Resolutions via projections

##  4\. Conclusion

Figure 6 summarizes much of what was discussed. Namely, both the voting
problem and TSP can be described in terms of a point
$\mathbf{d}_{A}^{n}\in\mathbb{R}^{n\choose 2}_{A}$. This space has an
orthogonal decomposition into the strongly transitive linear subspace
$\mathbb{ST}^{n}_{A}$ and the linear subspace $\mathbb{C}^{n}_{A}$ consisting
of three-cycles. The $\mathbf{d}_{A,st}^{n}$ component of $\mathbf{d}_{A}^{n}$
in the $\mathbb{ST}^{n}_{A}$ direction resolves several concerns from voting
theory, but frustrates the analysis of paths in TSP. Conversely,
$\mathbf{d}_{A}^{n}$’s component in the $\mathbb{C}^{n}_{A}$ direction,
$\mathbf{d}_{A,cyclic}^{n}$, determines all closed path properties for the
TSP, but erects barriers and paradoxes for voting theory. A resolution is to
project $\mathbf{d}_{A}^{n}$ into the appropriate subspace that has positive
properties for the problem being considered.

To introduce the rest of the material in this concluding section, let me brag
about my two granddaughters. Heili has a deep interest in neurobiology and
gymnastics, while Tatjana is heavily involved in the social sciences and
ballet. Who is older? It is impossible to tell from this information;
comparing ages requires having relevant inputs. More generally, to realize any
specified objective, for the data to be useful; they must, in some manner, be
directed toward the stated purpose. This truism extends to voting theory and
the TSP.

To see this with Arrow’s result, return to the introductory voting example
where the alternatives are three cities. Suppose the 25 voters with the
$A_{1}\succ A_{2}\succ A_{3}$ ranking judge cities according the ease of
finding parking, the 23 who prefer $A_{2}\succ A_{3}\succ A_{1}$ evaluate
cities according to the popularity of local professional basketball teams, and
the 22 preferring $A_{3}\succ A_{1}\succ A_{2}$ assess them according to
available types of craft beer. Thus the $A_{1}\succ A_{2}$ outcome by 47:23 is
a conglomeration of attitudes about parking, basketball, and beer. Of
importance, nothing is directed toward Arrow’s explicitly stated objective of
having a transitive ranking. This means (with these apple and orange
comparisons) that rather than a surprise, non-transitive outcomes should be
anticipated. Indeed, expect a transitive outcome only if the inputs contribute
toward this transitivity target. This comment leads to the decomposition (Fig.
6); the $\mathbf{d}^{n}_{A,cyclic}$ component of $\mathbf{d}_{A}^{n}$ that
runs counter to the stated objective is identified and dismissed. This leads
to the approach described in the first paragraph of the proof of Thm. 5, which
is called the “summation method” in [8].

Another way to handle this problem is to express the inputs, the preferences
of voters, in terms of the transitivity objective. To do so, describe the
$A_{1}\succ A_{2}\succ A_{3}$ ranking as $(A_{1}\succ A_{2},1),(A_{1}\succ
A_{3},2)$ and $(A_{2}\succ A_{3},1)$, which restates this ranking in terms of
pairs that now are in a strongly transitive format. Here $d_{1,2}=1$ captures
that $A_{1}$ is ranked one spot above $A_{2}$, while $d_{1,3}=2$ means that
$A_{1}$ is ranked two spots above $A_{3}$. Choosing the triplet
($A_{1},A_{2},A_{3}$) requires checking whether $d_{1,2}+d_{2,3}=1+1$ equals
$d_{1,3}=2,$ which it does. By using this strongly transitive approach, which
is called “Intensity of IIA” or IIIA (introduced in [8]), the profile
information for $\\{A_{1},A_{3}\\}$ has 25 voters with $(A_{1}\succ A_{3},2)$,
23 with $(A_{1}\succ A_{3},-1)$ and 22 with $(A_{1}\succ A_{3},-1)$, The IIIA
tally for $\\{A_{1},A_{3}\\}$ sums the products of the number of voters with
each ranking times its intensity. Here the tally is $25(2)+23(-1)+22(-1)=5$
leading to $A_{1}\succ A_{3}$, rather than the above $A_{3}\succ A_{1}$ (Eq.
2) that forced a cycle. Even stronger, the IIIA tallies over the three pairs
not only are transitive, they are strongly transitive.

With any number of alternatives, the IIIA outcome for the majority vote always
is strongly transitive. It must be because $\mathbb{ST}_{A}^{n}$ is a linear
subspace, and the outcome is a summation of strongly transitive profiles. This
IIIA method is equivalent to the Borda Count [8]; a conclusion that should be
anticipated (particularly with Thm. 6). As shown in [8], by replacing IIA with
IIIA, Arrow’s Theorem now has a positive conclusion. That is, by using data
that is consistent with the objective of transitivity, the problems of Arrow’s
Theorem disappear.

Similarly with TSP, each difference from the average cost between two
vertices, as catalogued with $\mathcal{G}^{6}_{A}$ (Fig. 1), could be based on
different attributes; e.g., the $d_{1,2}$ difference between $A_{1}$ and
$A_{2}$ might reflect the topography while $d_{2,3}$ between $A_{2}$ and
$A_{3}$ could be caused by traffic restrictions. As the objective concerns
path lengths of closed curves, the goal must be to use inputs that contribute
to the specified goal. Here the strongly transitive component
$\mathbf{d}_{A,cpi}^{n}$ pushes the outcome in a linear fashion that conflicts
with the goal of having circular paths. Dismissing this
$\mathbf{d}_{A,cpi}^{n}$ term (as indicated in Fig. 6) leaves
$\mathbf{d}^{n}_{A,cyclic}$ data, which are consistent with the global
objective of finding closed path properties.

##  5\. Proofs

Beyond proving Thm. 3, an intent of this section is to demonstrate the above
tools.

Proof of Thm. 3. Assume that the paired rankings defined by $\mathbf{d}^{n}$
have $A_{1}$ and $A_{n}$, respectively, the unique Condorcet winner and loser.
As $A_{1}$ is the unique Condorcet winner, the associated $\mathbf{d}_{A}^{n}$
must have $d_{1,k}>0$ for $k=2,\dots,n$. Similarly, as $A_{n}$ is the unique
Condorcet loser, it must be that $d_{n,k}<0$ for all $k=1,\dots,n-1.$ From Eq.
2, this means that $S_{A}(A_{1})>0$ and $S_{A}(A_{n})<0$. According to Eq. 15,
$A_{1}$ is Borda ranked above $A_{n}$. As the Borda ranking is the
$\mathbf{d}^{n}_{A,st},$ ranking, this proves the theorem. Notice, the
Condorcet uniqueness conditions are unnecessary conveniences. $\square$

It remains to show for $n=3,4$ that if $A_{1}$ and $A_{n}$ are, respectively,
the top and bottom ranked alternative for $\mathbf{d}^{n}_{A,st}$, and if
$\mathbf{d}_{A}^{n}=\mathbf{d}^{n}_{A,st}+\mathbf{d}^{n}_{A,cyclic}$ is
transitive, then $A_{1}\succ A_{n}$. The approach uses the fact, which follows
from strong transitivity, that $d_{1,n}$ for $\mathbf{d}^{n}_{A,st}$ is an
upper bound for all other $d_{s,u}$ values. This size of $d_{1,n}$ requires
the cyclic perturbations to affect and reverse smaller $d_{u,s}$ values, which
violates transitivity before they can impact on the $d_{1,n}$ term to reverse
$A_{1}\succ A_{n}$. Assume the $\mathbf{d}^{n}_{A,st}$ ranking is $A_{1}\succ
A_{2}\succ\dots\succ A_{n-1}\succ A_{n}$.

The proof is immediate for $n=3$. All cyclic $n=3$ vectors are $\alpha$
multiples of $(1,-1;1)$, so
$\mathbf{d}_{A}^{3}=\mathbf{d}^{3}_{A,st}+\mathbf{d}^{3}_{A,cyclic}=(d_{1,2}+\alpha,d_{1,3}-\alpha;d_{2,3}+\alpha).$
If $\alpha\geq 0$, then the $A_{1}\succ A_{2}$ and $A_{2}\succ A_{3}$ rankings
remain unchanged. The $A_{1}>A_{3}$ ranking persists as long as
$d_{1,3}-\alpha>0$. As soon as $\alpha>d_{1,3}$, the $A_{1}\succ A_{3}$
ranking reverses to become $A_{3}\succ A_{1}$, which converts the set of
pairwise rankings from transitive to cyclic.

For all $\alpha<0$ values, $A_{1}\succ A_{3}$. But the system becomes cyclic
as soon as $-\alpha$ equals the second largest of $\\{d_{1,2},d_{2,3}\\}.$ For
instance, suppose $d_{1,2}<d_{2,3}.$ For $\alpha=-d_{1,2}$, the rankings are
$A_{1}\succ A_{3},A_{2}\succ A_{3},$ and $A_{2}\sim A_{1}$ defining the
transitive $A_{1}\sim A_{2}\succ A_{3}$. But once $\alpha=-d_{2,3}$, the
rankings are the non-transitive $A_{1}\succ A_{3},A_{3}\sim A_{2},A_{2}\succ
A_{1}$. Stated differently, if $\mathbf{d}_{A}^{3}$ has a transitive ranking,
then $A_{1}\succ A_{3}$, which proves the assertion.

The theme of the proof for $n\geq 4$ is that, because of strong transitivity,
$d_{1,n}$ from $\mathbf{d}^{n}_{A,st}$ is so large that before the cyclic
components can reverse the $A_{1}\succ A_{n}$ ranking, they change enough
rankings of other pairs to define a cyclic outcome that violates the
transitivity of $\mathbf{d}_{A}^{n}$. One approach follows:

  1. (1)

Assume that the cyclic terms force $A_{n}\succ A_{1}$. It must be shown that
the pairs do not define a transitive outcome.

  2. (2)

The size of the perturbations of cyclic terms that accompany the $A_{n}\succ
A_{1}$ assumption requires some other alternative, say $A_{k}$, to satisfy
$A_{k}\succ A_{n}$. If $\mathbf{d}_{A}^{n}$ is transitive, as assumed, then
$A_{k}\succ A_{n}\succ A_{1},$ and $A_{k}\succ A_{1}.$

  3. (3)

The size of the cyclic perturbations that cause $A_{k}\succ A_{1}$ forces some
other alternative, $A_{j}$, to satisfy $A_{j}\succ A_{k}$. This requires
$A_{j}\succ A_{k}\succ A_{n}\succ A_{1}$, or $A_{j}\succ A_{1}$.

  4. (4)

The next step is to show that this $A_{j}\succ A_{1}$ ranking drives the size
of certain cyclic terms to be large enough so that $A_{n}\succ A_{j}$

  5. (5)

Step 4 is the sought contradiction. The $A_{j}\succ A_{n}$ ranking follows
from the assumption of the transitivity of $\mathbf{d}_{A}^{n}$, and the
conflicting $A_{n}\succ A_{j}$ is a direct result of computations based on the
impacts of the cyclic terms. Thus the assumption that $\mathbf{d}_{A}^{n}$ is
transitive is false, which proves the conclusion.

To illustrate this program with $n=4$, all of the following $d_{i,j}$ values
come from $\mathbf{d}^{4}_{A,st}$. Assume that $\mathbf{d}_{A}^{4}$ is
transitive. Using the Thm. 2 basis for $\mathbb{C}_{A}^{4}$, where
$\alpha_{j,k}$ is the coefficient for $\mathbf{d}^{4}_{1,j,k}$, a
representation for
$\mathbf{d}_{A}^{4}=\mathbf{d}^{4}_{A,st}+\mathbf{d}^{4}_{A,cyclic}$ is

(19)
$\mathbf{d}_{A}^{4}=({d_{1,2}+\alpha_{2,3}+\alpha_{2,4},d_{1,3}-\alpha_{2,3}+\alpha_{3,4},d_{1,4}-\alpha_{24}-\alpha_{3,4};d_{2,3}+\alpha_{2,3},d_{2,4}+\alpha_{2,4},d_{3,4}+\alpha_{3,4}}).$

According to Eq. 19, if $A_{4}\succ A_{1}$, then
$d_{1,4}-\alpha_{2,4}-\alpha_{3,4}<0$, or
$0<d_{1,4}<\alpha_{2,4}+\alpha_{3,4}$. This forces one or both of
$\alpha_{3,4}$, $\alpha_{2,4}$ to be positive.

Step 2. Start with the assumption that $\alpha_{3,4}>0$, which requires from
Eq. 19 that $A_{3}>A_{4}$. From the transitivity of $\mathbf{d}_{A}^{4}$, this
requires $A_{3}>A_{1}$, or $d_{1,3}-\alpha_{2,3}+\alpha_{3,4}<0,$ which leads
to the inequality

(20) $0<d_{1,3}+\alpha_{3,4}<\alpha_{2,3}.$

Step 3. Combining $\alpha_{2,3}>0$ (Eq. 20) with $\mathbf{d}_{A}^{4}$’s
transitivity (and Eq. 19), requires $A_{2}>A_{3}>A_{4}>A_{1}$. The
$A_{2}>A_{1}$ ranking forces (Eq. 19) $\alpha_{2,3}+\alpha_{2,4}<-d_{1,2}<0,$
which, with Eq. 20, becomes

(21) $\alpha_{2.4}<-d_{1,2}-\alpha_{2,3}<-d_{1,2}-d_{1,3}-\alpha_{3,4}<0.$

Step 4. As $\alpha_{2,4}<0$ (Step 3), it follows from $A_{4}>A_{1}$ and
$d_{1,4}-\alpha_{2,4}-\alpha_{3,4}<0$ that

(22) $\alpha_{3,4}>d_{1,4}\geq d_{j,k}.$

The last inequality follows because $d_{1,4}$ is the largest $d_{j,k}$ value
(strong transitivity).

Step 5. By using Eq. 21, the computation for the $\\{A_{2},A_{4}\\}$ ranking
depends on the sign of
$d_{2,4}+\alpha_{2,4}<-d_{1,2}-d_{1,3}+[-\alpha_{3,4}+d_{2,4}]$. Because
$-\alpha_{3,4}+d_{2,4}<0$ (Eq. 22), it follows that $d_{2,4}+\alpha_{2,4}<0$,
which is $A_{4}\succ A_{2}$ and the desired contradiction.

The remaining case of $\alpha_{2,4}>0,\alpha_{3,4}\leq 0$ is simpler because
from $A_{4}\succ A_{1}$ (Eq. 19)

(23) $\alpha_{2,4}>d_{1,4}\geq d_{j,k}.$

Step 2. According to Eq. 19, the $\alpha_{2,4}>0$ inequality and the
transitivity of $\mathbf{d}^{4}$ mandates $A_{2}>A_{4}>A_{1}$, or from
$A_{2}\succ A_{1}$ that $d_{1,2}+\alpha_{2,3}+\alpha_{2,4}<0.$ or that
$\alpha_{2,3}<-d_{1,2}-\alpha_{2,4}<0.$

Step 3. Using this inequality and Eq. 23, the $\\{A_{2},A_{3}\\}$ ranking
equation is determined by
$d_{2,3}+\alpha_{2,3}<-d_{1,2}+[d_{2,3}-\alpha_{2,4}]<0$, or
$A_{3}>A_{2}>A_{4}>A_{1}$.

Step 4. According to the $A_{3}>A_{1}$ ranking,
$d_{1,3}-\alpha_{2,3}+\alpha_{3,4}<0$ or (Step 2)
$d_{1,3}+\alpha_{3,4}<\alpha_{2,3}<-d_{1,2}-\alpha_{2,4}<0.$ What follows uses
the inequality $\alpha_{3,4}<-d_{1,3}-d_{1,2}-\alpha_{2,4}.$

Step 5. The $\\{A_{3},A_{4}\\}$ ranking depends on the sign of
$d_{3,4}+\alpha_{3,4}<-d_{1,2}-d_{1,3}+[-\alpha_{2,4}+d_{3,4}]<0$. As the term
in the brackets is negative, the value is negative, leading to the
$A_{4}>A_{3}$ contradiction. This completes the proof for $n=4$.

## References

  * [1] Arrow, K. J., Social Choice and Individual Values, Wiley, New York, 1951 (2nd ed, 1963).
  * [2] C. L. Dodgson and F. F. Abeles, The pamphlets of Lewis Carroll, vol. 3, The Political Pamphlets and Letters of Charles Lutwidge Dodgson and Related Pieces: a Mathematical Approach, Lewis Carroll Society of North America, New York, 2001.
  * [3] Kemeny J., Mathematics without numbers. Daedalus 88 (1959): 571-591.
  * [4] Ratliff, T., A comparison of Dodgson’s method and Kemeny’s rule, Social Choice and Welfare, 18, (2001), 79-89.
  * [5] Ratliff, T., A comparison of Dodgson’s method and the Borda count, Economic Theory, 20, (2002), 357-372.
  * [6] Ratliff, T., Some startling inconsistencies when electing committees, Social Choice and Welfare, 21 (2003), 433–454.
  * [7] Saari, D. G., A dictionary for voting paradoxes, Jour. Econ. Theory. 48 (1989), 443-475.
  * [8] Saari, D. G., Basic Geometry of Voting, Springer, New York, 1995.
  * [9] Saari, D. G., Mathematical structure of voting paradoxes 1; pairwise vote,” Econ. Theory, 15 (2000), 1-53.
  * [10] Saari, D. G., Mathematics Motivated by the Social and Behavioral Sciences, SIAM, Philadelphia, 2018.
  * [11] Saari, D. G., Arrow, and unexpected consequences of his theorem, Public Choice, 179 (2019), 133-144.
  * [12] Saari, D. G., Seeking consistency with paired comparisons: A systems approach, Theory and Decision 90 (2021), 1-26
  * [13] Saari, D. G., Inherent symmetries of graphs, paths, and Traveling Salesperson Problems, UCI preprint. Jan. 2022.
  * [14] Saari, D. G. and V. Merlin, A geometric examination of Kemeny’s rule, Social Choice & Welfare, 17 (2000), 403-438.


# The NetMob23 Dataset: A High-resolution Multi-region Service-level Mobile
Data Traffic Cartography

Orlando E. Martínez-Durive⋆†∗, Sachit Mishra⋆†∗, Cezary Ziemlicki‡,
Stefania Rubrichi‡, Zbigniew Smoreda‡, and Marco Fiore⋆ ⋆IMDEA Networks
Institute Spain; †Universidad Carlos III de Madrid Spain; ‡Orange Innovation
France.  orlando.martinez, sachit.mishra<EMAIL_ADDRESS>cezary.ziemlicki, stefania.rubrichi<EMAIL_ADDRESS>
###### Abstract.

Digital sources have been enabling unprecedented data-driven and large-scale
investigations across a wide range of domains, including demography,
sociology, geography, urbanism, criminology, and engineering. A major barrier
to innovation is represented by the limited availability of dependable digital
datasets, especially in the context of data gathered by mobile network
operators or service providers, due to concerns about user privacy and
industrial competition. The resulting lack of reference datasets curbs the
production of new research methods and results, and prevents verifiability and
reproducibility of research outcomes. The NetMob23 dataset offers a rare
opportunity to the multidisciplinary research community to access rich data
about the spatio-temporal consumption of mobile applications in a developed
country. The generation process of the dataset sets a new quality standard,
leading to information about the demands generated by $68$ popular mobile
services, geo-referenced at a high resolution of $100\times 100$ m2 over $20$
metropolitan areas in France, and monitored during $77$ consecutive days in
$2019$.

$\ast$ Equal contributors.

††copyright: none††conference: ; ††journalyear: ;††price:

##  1\. Introduction

The surge in the usage of mobile devices and Internet services is generating
an enormous amount of data, which has a high and largely untapped potential to
support the discovery of new knowledge about human behaviors. The data that
can be collected in production mobile networks is already proving an
invaluable proxy to analyze the habits of large populations at large scales of
cities or countries, complementing and in some cases replacing traditional
sources such as surveys or censuses that are expensive and time-consuming to
run. Examples of the substantial utility of mobile network data for research
abound, and span a plethora of domains: the data can unlock analyses of
mobility patterns (gonzalez2008understanding, ; song2010limits, ;
csaji2013exploring, ; kung2014exploring, ; louail2015uncovering, ) and social
interactions (miritello2013limited, ), explorations of transportation systems
(seppecher21zonal, ) estimates of static and dynamic population density
(deville2014dynamic, ; lenormand2015comparing, ; khodabandelou2018estimation,
; batista2020uncovering, ), predictions of poverty (steele17poverty, ;
pnas_17_combining_data_sources, ), socioeconomic inequality (moro21atlas, ;
ucar21news, ) or digital divides (mishra2022second, ), and mappings of land
usage (toole12landuse, ; lenormand15landuse, ; grauwin15cities, ;
furno17spatiotemporal, ) or urban transformation
(www_16_italian_cities_daniel_quercia, ) or pollution (chen21pollution, ); in
addition, mobile network data have proven instrumental to assess the impacts
of natural disasters (yabe22disasters, ) or infectious disease transmission
(www_19_carlos_serraute, ; oliver20covid, ; zanella2022impact, ), and the
effectiveness of the associated containment policies (heroy21covidpolicy, ;
pullano2020evaluating, ). These data can also enable studies aimed at
understanding how the mobile network infrastructure is used, improving its
management and extend its functionalities: for instance, they can be leveraged
for the localization and tracking of devices (www_16_linking_users, ;
IMWUT_19_cellsense, ), the characterization of network loads (paul2011infocom,
; www_20_cellrep, ) and application usages (marquez17conext, ), the prediction
of traffic fluctuations (zhang18mobihoc, ), the planning (su22planning, ) and
dynamic reconfiguration (sharma22vran, ) of Radio Access Networks (RAN)
infrastructures, or the data-driven management of network resources in sliced
environments (zhang20mobicom, ). The list above only covers a small sample of
the literature and does not pretend to be comprehensive by any means; surveys
are available that provide a more thorough review of the relevant body of
works (blondel2015survey, ; naboulsi15survey, ).

(a)

(b)

Figure 1. Population density map of France, highlighting the $\bm{20}$
metropolitan areas covered by our dataset. Zoomed-in maps show the
heterogeneity of population density in six representative cities, as indicated
by the arrows.

Despite their prospective impact on a wide range of domains, mobile network
data are hard to come by. The sensitivity of the information they provide, the
concerns for the privacy of the data subjects, and the questions on the
advantage that they could provide to market competitors are all reasons why
mobile network operators and service providers typically regard the data as
confidential, and are not prone to share them with the research community. It
limits access to mobile network data, curbing innovation as well as preventing
verifiability and reproducibility of the research results whenever permission
to use some data is granted under restrictive Non-Disclosure Agreements
(NDAs).

In this paper, we present a novel dataset of mobile data traffic that is open
to the research community within the context of a challenge organized jointly
with the NetMob 2023 conference111NetMob is the primary conference on the
analysis of mobile network data to investigate social, urban, societal and
industrial problems. Details can be found at https://netmob.org/.. By doing
so, we revive a recent tradition of challenges based on mobile phone data that
have sparked substantial interest and a flurry of original research outcomes a
few years ago. The Data for Development (D4D) challenges organized by Orange
in collaboration with NetMob in 2013 and 2014 (d4d_ivory, ; d4d_senegal, ),
the International Telecommunication Union (ITU) challenge to investigate the
Ebola epidemic in West African countries in 2015 (ITU_Project, ), the Telecom
Italia Big Data Challenge launched in 2014 and 2015 (barlacchi2015multi, ),
the Data for Refugees (D4R) challenge conducted by Turk Telekom in 2018
(salah18d4r, ) or the Future Cities Challenge supported by Foursquare during
the NetMob 2019 conference (foursquare18, ) are prominent examples of such
past initiatives.

Our dataset, referred to as NetMob23 hereinafter, sets a new standard for
mobile network data made available to the research community, from multiple
perspectives as follows.

  * •

While previous datasets have largely focused on Call Detail Records (CDRs)
that only capture network events associated with voice calls and text messages
that are sparse and irregular over time, NetMob23 contains information about
the data traffic generated by the mobile devices attached to a modern 4G
cellular network, which has been for the past ten years the vastly predominant
way of accessing wireless network services.

  * •

The NetMob23 dataset captures traffic in a developed country like France,
which offers a different perspective than earlier datasets focusing on
developing countries; also, the data spans $20$ metropolitan areas in France,
offering the possibility of generalizing analyses and juxtaposing results
across heterogeneous urbanization levels and population densities.

  * •

Unlike any dataset previously available to the research community within the
framework of open challenges, NetMob23 offers rich information about the usage
of $68$ popular mobile services, which opens significant opportunities to
understand the consumption of applications and its implications across
research domains.

  * •

The original generation process behind the NetMob23 dataset makes a major step
beyond the legacy approach of using Voronoi tessellations as a proxy for
antenna coverage, and results in a dataset of unprecedented spatial accuracy
where the mobile data traffic information is mapped to more than $870,000$
high-resolution regular grids whose individual elements span $100\times 100$
m2 each, for a total of over $440$ billion data points.

Overall, the NetMob23 dataset has the potential to support many novel
explorations of mobile network traffic and enable the development of new
applications on top of those findings. We look forward to seeing creative and
constructive uses of the data by the research community worldwide.

##  2\. Data sources

The generation process underpinning NetMob23 hinges upon open-source
geospatial data and extensive measurements from Orange, a major mobile network
operator in France. We note that Orange roughly has a $30$% market penetration
in the country that is relatively uniform across the French territory. This
provides a solid statistical basis for downstream analyses that generalize to
the entirety of the local population. We next present the different data
sources, and discuss the ethical standards of the data collection and
processing.

Figure 2. Mobile services in the NetMob23 dataset, ranked by the fraction of
total demand they generate.

###  2.1. Metropolitan areas

We use geographical shapefiles outlining the $20$ major metropolitan regions
in France, a zoning employed by national and local administrations to carry
out joint planning of the educational, cultural, economic, and social
initiatives over the country territory. Each metropolitan region encompasses a
set of neighboring communes, which are French local administrative zones
analogous to a civil township in the United States, and thus covers both dense
urban, suburban, and more rural areas that constitute the conurbation of a
specific city. Figure 1 shows the location and contour of all metropolitan
areas covered by the NetMob23 dataset, overlapped to a country-wide map of
population density. The areas of a few sample cities are magnified to
appreciate the diversity of population density captured by each of them.

Overall, our dataset includes the foremost industrial, commercial, and
financial centers of France, which are home to more than one third of the
total population in the country.

###  2.2. Mobile network traffic

We employ mobile data traffic collected over the $20$ target metropolitan
areas for $77$ consecutive days, i.e., roughly two and a half months, from
March $16$, $2019$, to May $31$, $2019$.

####  2.2.1. Service-level traffic volumes.

The traffic measurements were performed by Orange using passive measurement
probes tapping at the Gi, SGi and Gn interfaces connecting the Gateway GPRS
Support Nodes (GGSNs) and the Packet Data Network Gateways (PGWs) of the of
Long Term Evolution (LTE) Evolved Packet Core (EPC) network to external public
data networks (PDNs). This monitoring strategy allows capturing all 4G traffic
traversing the mobile network serving the whole country. The probes run
dedicated proprietary classifiers that allow associating individual traffic
flows to their corresponding mobile applications to enable network monitoring,
traffic engineering and research activities.

Ultimately, the EPC probes gather information about the uplink (UL) and
downlink (DL) volume of the demand generated by each of $68$ mobile services,
which are together responsible for about $70$% of the total mobile data
traffic observed by Orange in France. Figure 2 offers a look into the
applications included in the dataset, and a ranking of the same based on the
fraction of total traffic they generate. We observe that the services
responsible for the largest demands are responsible for around $10$% of the
overall mobile network usage. The logarithmic scale of the ordinate highlights
the power law that characterizes the relative consumption across applications,
and the consequent diversity of per-service traffic, which spans three orders
of magnitude when juxtaposing the top and bottom applications in the dataset.

####  2.2.2. Traffic flow to eNodeB association.

We associate traffic volumes to specific base stations using network
signalling data (NSD) captured by probes monitoring the LTE S1 interface
connecting eNodeBs, i.e., 4G base stations, to the Mobility Management Entity
(MME). The NSD allow tracking the eNodeB serving a mobile device across all
control-plane events, which include ($i$) voice and texting communications
such as call establishments and SMS transmissions, ($ii$) handovers, i.e.,
device cell changes during communication, ($iii$) Tracking Area (TA) updates,
i.e., cell changes that cross boundaries among larger regions that trigger
control messages also from idle devices), ($iv$) active paging, i.e., periodic
requests to update the location of the device started from the network side,
($v$) network attaches and detaches generated by devices joining or leaving
the network as they are turned on/off, or ($vi$) data connections, i.e.,
requests to assign resources for traffic generated by mobile applications
running on the device. Such high-frequency NSD events allow associating each
traffic flow to the exact sequence of eNodeBs that serviced it, and thus to
accurately link (portions of) the traffic volume of the flow to each base
station.

####  2.2.3. Service-level traffic time series at eNodeBs

We aggregate the traffic volume generated by all uplink or downlink flows
pertaining to a given mobile service and served by a same eNodeB. We also
aggregate the resulting traffic volumes over $15$-minute time intervals, i.e.,
a temporal granularity that allows observing a wide range of time-dependent
phenomena, while keeping the dataset at a reasonable size.

Figure 3. Summary of the dataset generation methodology. (A) Coverage matrix
for eNodeB $\bm{i}$. (B) Traffic time series aggregated over all users for
application $\bm{a}$, i.e., Spotify, at eNodeB $\bm{i}$. (C) Spatial mapping
of the Spotify traffic at eNodeB $\bm{i}$ during time step $\bm{t}$. (D)
Overall spatial distribution of Spotify traffic in $\bm{t}$, as the sum of all
eNodeB maps.

Overall, the mobile network traffic data we employ is in the form of time
series of the uplink and downlink load generated by $68$ mobile applications
at every eNodeB, with $15$-minute time steps. In order not to disclose the
sensitive information of the actual volume of traffic served by the mobile
network operator, we normalize all traffic by a same random value. Therefore,
traffic is not provided with a specific unit (e.g., bytes) but it is still
fully comparable across space and time.

###  2.3. Coverage dataset

Having associated the correct service-level traffic to each eNodeB over time,
we employ coverage information for each eNodeB to perform a spatial mapping of
the traffic information to the geographical space. This allows producing data
with a much higher spatial resolution than using legacy approaches such as
Voronoi tessellations.

Specifically, we start from coverage data computed using a commercial radio-
frequency signal propagation tool. For every eNodeB, coverage is encoded as
probabilities of association over a regular grid tessellation with tiles of
$100\times 100$ m2 each. A bi-dimensional matrix of $600\times 600$ tiles is
produced for a single eNodeB, hence providing complete coverage information
over an area of $60$ km2 surrounding the base station. The matrix tiles
contain probabilities $p(i\mid\ell)$ that explain the likelihood of a User
Equipment (UE) to connect to eNodeB $i$ while at tile $\ell$. By inverting
this probability information via Bayes’ theorem, under the assumption of a
uniform density of population within the area covered by the eNodeB, we derive
$p(\ell\mid i)$, i.e., the probability that a device associated with a base
station $i$ is located at tile $\ell$. We use $p(\ell\mid i)$ to distribute
over the high-resolution grid of $100\times 100$-m2 tiles the service-level
traffic observed by each eNodeB in a probabilistic fashion, as detailed in
Section 3.

##  3\. Generation methodology

The different data presented above are combined to generate the final NetMob23
dataset, following a process that is visually summarized in Figure 3.
Formally, let us denote by $\mathcal{T}_{\textit{a}}^{i}(t)$ the mobile
traffic generated by application $a$ at eNodeB $i\in I$ during time slot $t\in
T$, where $I$ is the set of all base stations and $T$ denotes the whole system
observation period. Also, recall that $\mathcal{P}(\ell\mid i)$ is the
probability of a user to be at a location $\ell$ while being connected to
eNodeB $i$.

As portrayed in Figure 3, we first multiply traffic observed at each eNodeB
(denoted by B in the figure) by the UE positioning probability of the same
eNodeB (A in the figure), so as to distribute over space the traffic volume
observed at the base station. This operation is repeated for each time slot
$t$ of the time series of every mobile service (e.g., Spotify in the figure).
The result is a traffic map $\mathcal{M}_{\textit{a}}^{i}(t)$, which
represents how the traffic generated by a given service $a$ (again, Spotify in
the figure example) at the target eNodeB $i$ is probabilistically distributed
over the geographical space at time $t$.

Region |  Bordeaux |  Clermont-Ferrand |  Dijon |  Grenoble |  Lille |  Lyon |  Mans |  Marseille |  Metz |  Montpellier |  Nancy |  Nantes |  Nice |  Orleans |  Paris |  Rennes |  Saint-Etienne |  Strasbourg |  Toulouse |  Tours |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Rows | 334 | 208 | 195 | 409 | 330 | 426 | 228 | 211 | 226 | 334 | 151 | 277 | 150 | 282 | 409 | 423 | 305 | 296 | 280 | 251 |
Columns | 342 | 268 | 234 | 251 | 342 | 287 | 246 | 210 | 269 | 327 | 165 | 425 | 214 | 256 | 346 | 370 | 501 | 258 | 347 | 270 |
Table 1. Dimensions of the matrices of regular grid tiles in each of the
$\bm{20}$ target urban regions.

Since the same regular grid tessellation is used for probabilities
$\mathcal{P}(\ell\mid i)$ across all base stations $i\in I$, it is possible to
repeat the process above for all eNodeBs, and generate consistent maps of the
spatial traffic of a same application $a$ over the whole mobile network. This
is attained by simply adding the different traffic maps as
$\mathcal{M}_{\text{a}}(t)=\sum_{i=1}^{I}\mathcal{M}_{\text{a}}^{i}(t)$ (shown
in Figure 3 as C). The final $\mathcal{M}_{\text{a}}(t)$ is the overall
traffic map of service $a$ at time $t$, defined over locations $\ell$ (D in
the figure).

We repeat the above steps for all $t\in T$ and for all applications to
ultimately obtain a complete spatiotemporal representation of the service-
level traffic in the $20$ target metropolitan areas introduced in Section 2.1
over a high-resolution grid of locations $\ell$.

###  3.1. Ethics considerations

The mobile network traffic dataset we use to generate the dataset was
collected, processed and aggregated as described in Section 2.2 in full
compliance with Article 89 of the General Data Protection Regulation (GDPR)
(gdpr, ), under the supervision of the Data Protection Officer (DPO) at
Orange. In particular, all data management was performed on a secure platform
at the operator’s premises and the raw data was deleted immediately afterward.

The resulting service-level time series represent traffic aggregated over all
UEs both in space, at eNodeB level, and time, over $15$-minute intervals.
Moreover, the traffic associated to different base stations is further
aggregated via the spatial mapping described earlier. The final representation
does not allow re-identifying or tracking individual users.

###  3.2. Final dataset format

To facilitate access to the data, the NetMob23 dataset is divided into spatial
representations and traffic information, which are detailed next. As part of
the material provided with the dataset, we also make available Jupyter
notebooks in Python with examples of manipulations of the dataset and
calculations of high-level statistical indicators and
plots222https://github.com/nds-group/netmob2023challenge..

####  3.2.1. Spatial representation

We publish a GeoJson file for each metropolitan region with the WGS84
coordinate system. Each of these files contains the tile identifier of each
regular grid tile in the target urban area, and the corresponding polygon that
bounds the $100\times 100$-m2 geographical surface of the tile. We also
provide an alternative matrix representation of the space, in the form of a
text file containing the number of rows and columns in the matrix, whose
values are also shown in Table 1.

Figure 4. Hierarchical organization of traffic files.

####  3.2.2. Traffic information

The traffic dataset folder is organized according to a tree structure, as
shown in Fig 4. The root is the target urban region, followed by the
application name and then the day, with two leaves, i.e., text files, for the
UL and DL directions, respectively. In each text file, one line represents the
(normalized) traffic in a given tile of the city, for the corresponding
application and date, from midnight to 23:45 at 15-minute time steps, as shown
in Table 2.

More precisely, each line contains the following fields:

  * •

tile is the tile identifier used in the GeoJson spatial representation file
for the same urban area. In the case of the matrix representation of tiles,
the position inside the matrix can be retrieved by an integer division and a
modulo operation.

  * •

thh:mm is a vector of $96$ values, corresponding to the traffic observed in UL
or DL at location tile for the target city, service and day, during all
15-minute time slots, starting from midnight to $23$:$45$.

tile | t00:00 | t00:15 | … | t23:45
---|---|---|---|---
… |  |  |  |
1966 | $\mathcal{T}_{0}$ | $\mathcal{T}_{1}$ | … | $\mathcal{T}_{95}$
1967 | $\mathcal{T}_{0}$ | $\mathcal{T}_{1}$ | … | $\mathcal{T}_{95}$
1968 | $\mathcal{T}_{0}$ | $\mathcal{T}_{1}$ | … | $\mathcal{T}_{95}$
… |  |  |  |
Table 2. Example of the format of a traffic file.

##  4\. Qualitative analysis

In this section, we provide a preliminary exploration of some characteristics
of the NetMob23 dataset. The analysis aims at discussing basic properties of
the spatial and temporal evolution of the service-level mobile traffic, and
highlight anomalies inherent to the dataset that may bias downstream usages of
the same.

###  4.1. Anomaly analysis

(a)

(b)

(c)

Figure 5. Traffic time series highlighting different anomalies in various
cities of the NetMob23 dataset.

The NetMob23 dataset is based on traffic information measured in a production
network. As such, it is characterized by anomalous events of technical nature,
caused, e.g., by exceptional surges in demands, radio access network
malfunctioning, network configuration errors, energy supply problems, or
issues in the traffic monitoring system.

Period | Affected regions | Services
---|---|---
April 9, 2019 | Bordeaux | All
April 12, 2019 | Bordeaux, Toulouse | All
April 14, 2019 (fb_outage_14_4, ) | Nationwide | Meta Inc.
May 12, 2019 (china_telcom_wordwide_may_13, ) | Nationwide | All
May 22-25, 2019 | Bordeaux, Toulouse | All
Table 3. Major anomalies detected in the dataset.

We report examples of anomalous events that can be observed in the NetMob23
dataset in Figure 5, for different combinations of cities and services. The
plots show the overall traffic in UL and DL, with anomalies evidenced by light
red areas. The three plots show for instance the effects of a nationwide
network outage on May 12, 2019, which caused both UL and DL traffic to drop
substantially in the whole Orange network. A similar, but shorter issue also
occurred on April 15. The top and bottom plots also highlight a an event
affecting only the South-East of France but for a longer period spanning from
May 22 through May 25: the problem caused a reduction of traffic in Bordeaux
and Toulouse, but not in Paris, due to the geographical locations of the
cities. More rarely, outages concern specific applications, such as for the
services of Meta on April 14, as seen, e.g., in the top plot for Facebook Live
traffic. The full list of major anomalies we detected in the data is provided
in Table 3.

###  4.2. Temporal Analysis

(a)

(b)

(c)

(d)

Figure 6. Traffic time series of four different applications in Paris, as
observed during a same week.

(a)

(b)

(c)

(d)

Figure 7. Traffic time series of the Netflix service in four different cities
during a same week.

(a)

(b)

(c)

(d)

(e)

(a)

(b)

(c)

(d)

Figure 8. Spatial traffic generated by four applications in Paris, on Mondays
(top) and Sundays (bottom).

People tend to follow fairly regular patterns in their daily lives, and mobile
network data have been repeatedly shown to be affected by such periodicity
(gonzalez2008understanding, ; paul2011infocom, ; furno17spatiotemporal, ).
This is true at the level of the total mobile traffic, but even more so when
considering individual applications, since users employ those at specific
times of their weekly routine.

Figure 6 shows the time series of four major mobile applications with very
diverse usage patterns in Paris. LinkedIn is a business and employment-
oriented social media application that is used to connect with other
professionals to share their resumes, work, or professional events; Netflix is
an application that people use for entertainment; Apple iCloud is a platform
that is used to store and sync data on various Apple devices for applications
like Apple Mail, Apple Calendar, Apple Photos, Apple Notes, contacts,
settings, and backup files; and, Uber is used for long and short rides. Each
of these applications shows different patterns in their time series, i.e.,
LinkedIn shows a high traffic peak in the early morning hours until the
afternoon and then the traffic values for both UL and UD start to decrease.
Conversely, Netflix shows a high traffic peak in the late evening because
people are usually free during these hours, while Apple iCloud does not follow
either the day or night pattern. Finally, Uber generates a clear pattern where
weekend traffic is almost the same during the day and night, implying that the
service is used more on weekends when people travel and take rides to return
late at night. As another notable difference across applications, the UL/DL
ratio is very heterogeneous, which could be noted already in Figure 2.

These behaviors are not a specific feature of a large metropolis like Paris. A
same application tends in fact to be mostly used in the same way in different
geographic locations, as shown in Figure 7. There, we consider the example of
Netflix, and display its usage in four cities, namely Bordeaux, Lyon,
Toulouse, and Marseille. The patterns are very much comparable in all plots,
although minor changes occur that would deserve a deeper investigation.

###  4.3. Spatial Analysis

The NetMob23 dataset allows investigating spatial properties of the mobile
service usage as well. Figure 8 shows the average traffic maps on Mondays (top
row) and Sundays (bottom row) for the same four applications considered
before, i.e., Netflix, LinkedIn, Apple iCloud, and Uber. Each of the plots
shows the whole Paris urban area and a zoom on the city center delimited by
the local inner beltway.

The figure allows comparing the applications along two dimensions. On the one
hand, looking at plots from left to right shows that the different
applications have very diverse geographical distributions of their generated
traffic. Netflix, for example, is pervasively distributed across the region,
which is even more evident in the zoomed map, whereas LinkedIn and Apple
iCloud have a high concentration in the part of the city where there are many
large offices and workplaces. In the case of iCloud, notable traffic is also
recorded at touristic spots, amusement parks, or entertainment facilities: we
speculate that these may be locations where people usually upload photos or
videos to their personal cloud. In the case of Uber, there is a clear
distribution of traffic on city streets, highways, train stations, and
airports.

On the other dimension, a comparison of the demands for a same application in
working and weekend days, i.e., from top to bottom of Figure 8, also reveals
interesting phenomena. For instance, Netflix is used in a fairly constant way
during the week, whereas Uber is more actively used on weekends than on
weekdays. On the contrary, LinkedIn and Apple iCloud largely drops in
weekends, although Apple iCloud usage persists in the more touristic areas of
the city.

##  5\. Additional resources

The NetMob23 dataset can be enriched via combination with other sources of
information. We list a number of sources of sociodemographic and
telecommunication indicators that cover the French territory at around the
same time of the mobile traffic data collection.

Administrative boundaries. These resources are available on the Open platform
for French public data and the National Institute of Geographic and Forest
Information (IGN).

  * •

Regions are the apex level territorial division of France, which is presently
divided into 22 such zones (adm_regions, ).

  * •

Departments are administrative units of France governed by an elected body,
i.e., the departmental council. There are currently $96$ departments in
France.

  * •

Arrondissements are the next level of subdivision of the departments and
organize the local police, fire department, and occasionally elections. There
are currently $332$ arrondissements in France.

  * •

Communes are the smallest and the oldest French administrative unit (insee-
commune, ), administered by the municipal council and headed by a mayor.
Currently, there are about $36,000$ communes in mainland France.

  * •

Urban Units are formed on the basis of contiguous built-up areas (insee-urban-
unit, ), and typically merge neighboring communes denotes by urban continuity.

  * •

IRIS is a fine-grained territorial subdivision of France, such that the number
of inhabitants in each IRIS zone is around $2,000$. This definition is
employed by the French National Institute of Statistics and Economic Studies
(INSEE) for statistical analyses (insee-iris, ; adm_iris, ).

Social-Economic indicators. INSEE collects data on population, education,
income and other socio-economic statistics on a quinquennial basis across the
whole France. The institute has an open-data website that includes, among
others, the information below.

  * •

Population contains data for different age groups for both men and women from
different years at Commune (soc_pop_income_educ_commune, ), and IRIS
(soc_pop_iris, ) levels.

  * •

Average income encompasses median and quantiles of consumption units per
household at commune (soc_pop_income_educ_commune, ) and IRIS levels for
various years. In addition, the data also include Gini indexes that provide
information on income inequality between individuals and households in a given
region.

  * •

Educational level information includes the number of people attending school
or university, in communes (soc_pop_income_educ_commune, ) and IRIS zones
(soc_educ_iris, ), for different age groups.

Telecommunications. The National Agency for Radio Frequencies (ANFR) and the
Authority for the Regulation of Electronic Communications (Arcep) are French
regulatory bodies in the telecommunication area, and gather data such as
coverage and antenna location for electronic communications. Some potentially
relevant datasets are made available by the agencies, as listed below.

  * •

Operator coverage is a cartographic platform that assembles all geographic
data related to different mobile networks (2G, 3G, 4G, 5G) for all operators
(tel_cov_sites, ).

  * •

Radio and antennas location data is handled by ANFR, which updates its mobile
network deployment observatory monthly and lists all radio sites authorized on
French territory via a cartographic platform (tel_radio_antennas, ).

##  6\. Concluding remarks

This paper presents a dataset of mobile traffic made available to the research
community within the context of a challenge, which features for the first time
service-level demands, as well as unprecedented spatial resolution and
geographical coverage in a developed country. We believe that the NetMob23
dataset will inspire researchers to design and implement a number of
innovative analyses, and discover new knowledge about how and why people
consume mobile applications.

## Acknowledgements

The mobile network traffic and coverage data presented in Section 2.2 and
Section 2.3 were collected during the research project CANCAN (Content and
Context based Adaptation in Mobile Networks), grant no. ANR-18-CE25-0011,
funded by the French National Research Agency (ANR). The NetMob 2023 Data
Challenge is organized with the support of the research project NetSense,
grant no. 2019-T1/TIC-16037 funded by Comunidad de Madrid, and of the research
project CoCo5G (Traffic Collection, Contextual Analysis, Data-driven
Optimization for 5G), grant no. ANR-22-CE25-0016, funded by the French
National Research Agency (ANR).

## References

  * (1) M. C. Gonzalez, C. A. Hidalgo, and A.-L. Barabasi, “Understanding individual human mobility patterns,” _nature_ , vol. 453, no. 7196, pp. 779–782, 2008\.
  * (2) C. Song, Z. Qu, N. Blumm, and A.-L. Barabási, “Limits of predictability in human mobility,” _Science_ , vol. 327, no. 5968, pp. 1018–1021, 2010.
  * (3) B. C. Csáji, A. Browet, V. A. Traag, J.-C. Delvenne, E. Huens, P. Van Dooren, Z. Smoreda, and V. D. Blondel, “Exploring the mobility of mobile phone users,” _Physica A: statistical mechanics and its applications_ , vol. 392, no. 6, pp. 1459–1473, 2013.
  * (4) K. S. Kung, K. Greco, S. Sobolevsky, and C. Ratti, “Exploring universal patterns in human home-work commuting from mobile phone data,” _PloS one_ , vol. 9, no. 6, p. e96180, 2014.
  * (5) T. Louail, M. Lenormand, M. Picornell, O. Garcia Cantu, R. Herranz, E. Frias-Martinez, J. J. Ramasco, and M. Barthelemy, “Uncovering the spatial structure of mobility networks,” _Nature communications_ , vol. 6, no. 1, pp. 1–8, 2015.
  * (6) G. Miritello, R. Lara, M. Cebrian, and E. Moro, “Limited communication capacity unveils strategies for human interaction,” _Scientific reports_ , vol. 3, no. 1, pp. 1–7, 2013.
  * (7) M. Seppecher, L. Leclercq, A. Furno, D. Lejri, and T. Vieira da Rocha, “Estimation of urban zonal speed dynamics from user-activity-dependent positioning data and regional paths,” _Transportation Research Part C: Emerging Technologies_ , vol. 129, p. 103183, 2021. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0968090X21001996
  * (8) P. Deville, C. Linard, S. Martin, M. Gilbert, F. R. Stevens, A. E. Gaughan, V. D. Blondel, and A. J. Tatem, “Dynamic population mapping using mobile phone data,” _Proceedings of the National Academy of Sciences_ , vol. 111, no. 45, pp. 15 888–15 893, 2014.
  * (9) M. Lenormand, M. Picornell, O. G. Cantú-Ros, T. Louail, R. Herranz, M. Barthelemy, E. Frías-Martínez, M. San Miguel, and J. J. Ramasco, “Comparing and modelling land use organization in cities,” _Royal Society open science_ , vol. 2, no. 12, p. 150449, 2015.
  * (10) G. Khodabandelou, V. Gauthier, M. Fiore, and M. A. El-Yacoubi, “Estimation of static and dynamic urban populations with mobile network metadata,” _IEEE Transactions on Mobile Computing_ , vol. 18, no. 9, pp. 2034–2047, 2018\.
  * (11) F. Batista e Silva, S. Freire, M. Schiavina, K. Rosina, M. A. Marín-Herrera, L. Ziemba, M. Craglia, E. Koomen, and C. Lavalle, “Uncovering temporal changes in europe’s population density patterns using a data fusion approach,” _Nature communications_ , vol. 11, no. 1, 2020.
  * (12) J. E. Steele, P. R. Sundsøy, C. Pezzulo, V. A. Alegana, T. J. Bird, J. Blumenstock, J. Bjelland, K. Engø-Monsen, Y.-A. de Montjoye, A. M. Iqbal, K. N. Hadiuzzaman, X. Lu, E. Wetter, A. J. Tatem, and L. Bengtsson, “Mapping poverty using mobile phone and satellite data,” _Journal of The Royal Society Interface_ , vol. 14, no. 127, p. 20160690, 2017. [Online]. Available: https://royalsocietypublishing.org/doi/abs/10.1098/rsif.2016.0690
  * (13) N. Pokhriyal and D. C. Jacques, “Combining disparate data sources for improved poverty prediction and mapping,” _Proceedings of the National Academy of Sciences_ , vol. 114, no. 46, pp. E9783–E9792, 2017. [Online]. Available: https://www.pnas.org/doi/abs/10.1073/pnas.1700319114
  * (14) E. Moro, D. Calacci, X. Dong, and A. Pentland, “Mobility patterns are associated with experienced income segregation in large us cities,” _Nat Commun_ , vol. 12, no. 4633, 2021.
  * (15) I. Ucar, M. Gramaglia, M. Fiore, Z. Smoreda, and E. Moro, “News or social media? socio-economic divide of mobile service consumption,” _Journal of The Royal Society Interface_ , vol. 18, no. 185, p. 20210350, 2021. [Online]. Available: https://royalsocietypublishing.org/doi/abs/10.1098/rsif.2021.0350
  * (16) S. Mishra, Z. Smoreda, and M. Fiore, “Second-level digital divide: A longitudinal study of mobile traffic consumption imbalance in france,” in _Proceedings of the ACM Web Conference 2022_ , 2022, pp. 2532–2540.
  * (17) J. L. Toole, M. Ulm, M. C. González, and D. Bauer, “Inferring land use from mobile phone activity,” in _Proceedings of the ACM SIGKDD International Workshop on Urban Computing_ , ser. UrbComp ’12. New York, NY, USA: Association for Computing Machinery, 2012, p. 1–8. [Online]. Available: https://doi.org/10.1145/2346496.2346498
  * (18) M. Lenormand, M. Picornell, O. G. Cantú-Ros, T. Louail, R. Herranz, M. Barthelemy, E. Frías-Martínez, M. San Miguel, and J. J. Ramasco, “Comparing and modelling land use organization in cities,” _Royal Society Open Science_ , vol. 2, no. 12, p. 150449, 2015. [Online]. Available: https://royalsocietypublishing.org/doi/abs/10.1098/rsos.150449
  * (19) S. Grauwin, S. Sobolevsky, S. Moritz, I. Gódor, and C. Ratti, _Towards a Comparative Science of Cities: Using Mobile Traffic Records in New York, London, and Hong Kong_. Cham: Springer International Publishing, 2015, pp. 363–387. [Online]. Available: https://doi.org/10.1007/978-3-319-11469-9_15
  * (20) A. Furno, M. Fiore, and R. Stanica, “Joint spatial and temporal classification of mobile traffic demands,” in _IEEE INFOCOM 2017 - IEEE Conference on Computer Communications_ , 2017, pp. 1–9.
  * (21) M. De Nadai, J. Staiano, R. Larcher, N. Sebe, D. Quercia, and B. Lepri, “The death and life of great italian cities: a mobile phone data perspective,” in _Proceedings of the 25th International Conference on World Wide Web_ , 2016, pp. 413–423.
  * (22) W. Chen, Y. He, and S. Pan, “Impact of air pollution on human activities: Evidence from nine million mobile phone users,” _PLoS ONE_ , vol. 16, p. e0251288, 2021. [Online]. Available: https://doi.org/10.1371/journal.pone.0251288
  * (23) T. Yabe, N. K. Jones, P. S. C. Rao, M. C. Gonzalez, and S. V. Ukkusuri, “Mobile phone location data for disasters: A review from natural hazards and epidemics,” _Computers, Environment and Urban Systems_ , vol. 94, p. 101777, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0198971522000217
  * (24) A. Vazquez Brust, T. Olego, G. Rosati, C. Lang, G. Bozzoli, D. Weinberg, R. Chuit, M. Minnoni, and C. Sarraute, “Detecting areas of potential high prevalence of chagas in argentina,” in _Companion Proceedings of The 2019 World Wide Web Conference_ , ser. WWW ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 262–271. [Online]. Available: https://doi.org/10.1145/3308560.3316485
  * (25) N. Oliver, B. Lepri, H. Sterly, R. Lambiotte, S. Deletaille, M. D. Nadai, E. Letouzé, A. A. Salah, R. Benjamins, C. Cattuto, V. Colizza, N. de Cordes, S. P. Fraiberger, T. Koebe, S. Lehmann, J. Murillo, A. Pentland, P. N. Pham, F. Pivetta, J. Saramäki, S. V. Scarpino, M. Tizzoni, S. Verhulst, and P. Vinck, “Mobile phone data for informing public health actions across the covid-19 pandemic life cycle,” _Science Advances_ , vol. 6, no. 23, p. eabc0764, 2020. [Online]. Available: https://www.science.org/doi/abs/10.1126/sciadv.abc0764
  * (26) A. F. Zanella, O. E. Martínez-Durive, S. Mishra, Z. Smoreda, and M. Fiore, “Impact of later-stages covid-19 response measures on spatiotemporal mobile service usage,” in _IEEE INFOCOM 2022-IEEE Conference on Computer Communications_. IEEE, 2022, pp. 970–979.
  * (27) S. Heroy, I. Loaiza, A. Pentland, and N. O’Clery, “Covid-19 policy analysis: labour structure dictates lockdown mobility behaviour,” _Journal of The Royal Society Interface_ , vol. 18, no. 176, p. 20201035, 2021. [Online]. Available: https://royalsocietypublishing.org/doi/abs/10.1098/rsif.2020.1035
  * (28) G. Pullano, E. Valdano, N. Scarpa, S. Rubrichi, and V. Colizza, “Evaluating the effect of demographic factors, socioeconomic factors, and risk aversion on mobility during the covid-19 epidemic in france under lockdown: a population-based study,” _The Lancet Digital Health_ , vol. 2, no. 12, pp. e638–e649, 2020.
  * (29) C. Riederer, Y. Kim, A. Chaintreau, N. Korula, and S. Lattanzi, “Linking users across domains with location data: Theory and validation,” in _Proceedings of the 25th International Conference on World Wide Web_ , ser. WWW ’16. Republic and Canton of Geneva, CHE: International World Wide Web Conferences Steering Committee, 2016, p. 707–719. [Online]. Available: https://doi.org/10.1145/2872427.2883002
  * (30) Z. Fang, Y. Yang, G. Yang, Y. Xian, F. Zhang, and D. Zhang, “Cellsense: Human mobility recovery via cellular network data enhancement,” _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ , vol. 5, no. 3, sep 2021. [Online]. Available: https://doi.org/10.1145/3478087
  * (31) U. Paul, A. P. Subramanian, M. M. Buddhikot, and S. R. Das, “Understanding traffic dynamics in cellular data networks,” in _2011 Proceedings IEEE INFOCOM_. IEEE, 2011, pp. 882–890.
  * (32) Z. Fang, G. Wang, S. Wang, C. Zuo, F. Zhang, and D. Zhang, “Cellrep: Usage representativeness modeling and correction based on multiple city-scale cellular networks,” in _Proceedings of The Web Conference 2020_ , ser. WWW ’20. New York, NY, USA: Association for Computing Machinery, 2020, p. 584–595. [Online]. Available: https://doi.org/10.1145/3366423.3380141
  * (33) C. Marquez, M. Gramaglia, M. Fiore, A. Banchs, C. Ziemlicki, and Z. Smoreda, “Not all apps are created equal: Analysis of spatiotemporal heterogeneity in nationwide mobile service usage,” in _Proceedings of the 13th International Conference on emerging Networking EXperiments and Technologies_ , 2017, pp. 180–186.
  * (34) C. Zhang and P. Patras, “Long-term mobile traffic forecasting using deep spatio-temporal neural networks,” in _Proceedings of the Eighteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing_ , ser. Mobihoc ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 231–240. [Online]. Available: https://doi.org/10.1145/3209582.3209606
  * (35) J. Su, M. Beshley, K. Przystupa, O. Kochan, B. Rusyn, R. Stanisławski, O. Yaremko, M. Majka, H. Beshley, I. Demydov, J. Pyrih, and I. Kahalo, “5g multi-tier radio access network planning based on voronoi diagram,” _Measurement_ , vol. 192, p. 110814, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0263224122001117
  * (36) M. Sharma, U. Pawar, A. Antony Franklin, and B. R. Tamma, “Proactive clustering of base stations in 5gc-ran using cellular traffic prediction,” in _2022 IEEE 8th International Conference on Network Softwarization (NetSoft)_ , 2022, pp. 339–347.
  * (37) C. Zhang, M. Fiore, C. Ziemlicki, and P. Patras, “Microscope: Mobile service traffic decomposition for network slicing as a service,” in _Proceedings of the 26th Annual International Conference on Mobile Computing and Networking_ , ser. MobiCom ’20. New York, NY, USA: Association for Computing Machinery, 2020. [Online]. Available: https://doi.org/10.1145/3372224.3419195
  * (38) V. D. Blondel, A. Decuyper, and G. Krings, “A survey of results on mobile phone datasets analysis,” _EPJ data science_ , vol. 4, no. 1, p. 10, 2015\.
  * (39) D. Naboulsi, M. Fiore, S. Ribot, and R. Stanica, “Large-scale mobile traffic analysis: a survey,” _IEEE Communications Surveys & Tutorials_, vol. 18, no. 1, pp. 124–161, 2015.
  * (40) V. D. Blondel, M. Esch, C. Chan, F. Clérot, P. Deville, E. Huens, F. Morlot, Z. Smoreda, and C. Ziemlicki, “Data for development: the d4d challenge on mobile phone data,” _arXiv preprint arXiv:1210.0137_ , 2012\.
  * (41) Y.-A. de Montjoye, Z. Smoreda, R. Trinquart, C. Ziemlicki, and V. D. Blondel, “D4d-senegal: the second mobile phone data for development challenge,” _arXiv preprint arXiv:1407.4885_ , 2014.
  * (42) International Telecommunication Union, “Big data for development: preventing the spread of epidemics,” https://www.itu.int/en/ITU-D/Emergency-Telecommunications/Pages/BigData/default.aspx, accessed: 2023-01-09.
  * (43) G. Barlacchi, M. De Nadai, R. Larcher, A. Casella, C. Chitic, G. Torrisi, F. Antonelli, A. Vespignani, A. Pentland, and B. Lepri, “A multi-source dataset of urban life in the city of milan and the province of trentino,” _Scientific data_ , vol. 2, no. 1, pp. 1–15, 2015.
  * (44) A. A. Salah, A. Pentland, B. Lepri, E. Letouze, P. Vinck, Y.-A. de Montjoye, X. Dong, and O. Dagdelen, “Data for refugees: The d4r challenge on mobility of syrian refugees in turkey,” 2018. [Online]. Available: https://arxiv.org/abs/1807.00523
  * (45) Foursquare, “Future cities challenge,” https://location.foursquare.com/resources/blog/leadership/how-location-technology-can-drive-urban-innovation/, 2018, accessed: 2023-03-14.
  * (46) European Union. (2016) Eu general data protection regulation (gdpr): Regulation (eu) 2016/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing directive 95/46/ec (general data protection regulation). [Online]. Available: https://gdpr-info.eu/
  * (47) Bloomberg, “Facebook suffers third major global outage this year,” https://www.bloomberg.com/news/articles/2019-04-14/facebook-suffers-third-major-global-outage-this-year, accessed: 2023-01-09.
  * (48) ThousandEyes, “Internet outage reveals reach of china’s connectivity,” https://www.thousandeyes.com/blog/internet-outage-reveals-reach-of-chinas-connectivity, accessed: 2023-01-09.
  * (49) Open platform for French public data, “Geographical contours of the new regions (metropolis),” https://www.data.gouv.fr/fr/datasets/contours-geographiques-des-nouvelles-regions-metropole/, accessed: 2023-01-09.
  * (50) The National Institute of Statistics and Economic Studies. (2021, Oct.) Definition: Commune. [Online]. Available: https://www.insee.fr/fr/metadonnees/definition/c1468
  * (51) The National Institute of Statistics and Economic Studies , “Definition: Urban unit,” https://www.insee.fr/en/metadonnees/definition/c1501, accessed: 2023-01-20.
  * (52) The National Institute of Statistics and Economic Studies. (2021, Oct.) Definition: Iris. [Online]. Available: https://www.insee.fr/en/metadonnees/definition/c1523
  * (53) National Institute of Geographic and Forest Information (IGN), “The reference database for the infra-municipal dissemination of the results of the population census by iris, of decametric precision,” https://geoservices.ign.fr/contoursiris, accessed: 2023-01-09.
  * (54) The National Institute of Statistics and Economic Studies , “Base du dossier complet,” https://www.insee.fr/fr/statistiques/5359146, accessed: 2023-01-09.
  * (55) The National Institute of Statistics and Economic Studies, “Population en 2019,” https://www.insee.fr/fr/statistiques/6543200/, accessed: 2023-01-09.
  * (56) The National Institute of Statistics and Economic Studies , “Diplômes - formation en 2019 (iris),” https://www.insee.fr/fr/statistiques/6543298, accessed: 2023-01-09.
  * (57) Open platform for French public data, “Mon réseau mobile,” https://www.data.gouv.fr/fr/datasets/mon-reseau-mobile/, accessed: 2023-01-09.
  * (58) The National Frequency Agency, “Cartoradio: The map of radio sites and wave measurements,” https://cartoradio.fr, accessed: 2023-01-09.