# Exploring Human Mobility for Multi-pattern Passenger Prediction: A Graph
Learning Framework

Xiangjie Kong, , Kailai Wang, Mingliang Hou, Feng Xia, ,
Gour Karmakar, , and Jianxin Li This work was supported in part by the
National Natural Science Foundation of China under Grant 62072409, in part by
the Zhejiang Provincial Natural Science Foundation under Grant LR21F020003,
and in part by the Fundamental Research Funds for the Provincial Universities
of Zhejiang under Grant RF-B2020001. _(Corresponding author: Feng Xia.)_ X.
Kong is with the School of Software, Dalian University of Technology, Dalian
116620, China, and also with the College of Computer Science and Technology,
Zhejiang University of Technology, Hangzhou 310023, China (e-mail:
xjkong@ieee.org).K. Wang and M. Hou are with the School of Software, Dalian
University of Technology, Dalian 116620, China (e-mail<EMAIL_ADDRESS>teemohold@outlook.com).F. Xia is with the School of Engineering, IT and
Physical Sciences, Federation University Australia, Ballarat 3353, Australia
(e-mail: f.xia@ieee.org).G. Karmakar is with the School of Engineering, IT and
Physical Sciences, Federation University Australia, Churchill 3842, Australia
(e-mail: gour.karmakar@federation.edu.au).J. Li is with the School of IT,
Deakin University, Melbourne 3125, Australia (e-mail:
jianxin.li@deakin.edu.au).

###### Abstract

Traffic flow prediction is an integral part of an intelligent transportation
system and thus fundamental for various traffic-related applications. Buses
are an indispensable way of moving for urban residents with fixed routes and
schedules, which leads to latent travel regularity. However, human mobility
patterns, specifically the complex relationships between bus passengers, are
deeply hidden in this fixed mobility mode. Although many models exist to
predict traffic flow, human mobility patterns have not been well explored in
this regard. To reduce this research gap and learn human mobility knowledge
from this fixed travel behaviors, we propose a multi-pattern passenger flow
prediction framework, MPGCN, based on Graph Convolutional Network (GCN).
Firstly, we construct a novel sharing-stop network to model relationships
between passengers based on bus record data. Then, we employ GCN to extract
features from the graph by learning useful topology information and introduce
a deep clustering method to recognize mobility patterns hidden in bus
passengers. Furthermore, to fully utilize Spatio-temporal information, we
propose GCN2Flow to predict passenger flow based on various mobility patterns.
To the best of our knowledge, this paper is the first work to adopt a multi-
pattern approach to predict the bus passenger flow from graph learning. We
design a case study for optimizing routes. Extensive experiments upon a real-
world bus dataset demonstrate that MPGCN has potential efficacy in passenger
flow prediction and route optimization.

###### Index Terms:

Spatio-temporal data mining, human mobility pattern, graph convolutional
networks, passenger flow prediction, smart city.

##  I Introduction

Smart cities have been gradually formed by information and communication
technologies, including the Internet of Things (IoT) [1], cloud computing [2],
and edge computing [3]. One important application scenario of the smart city
is the Intelligent Transportation System (ITS) to improve the public services
and gain the solutions to problems in urban transportation such as traffic
jams, traffic accidents, parking chaos, route planning [4], and resource
allocation [5]. The above problems are closely related to traffic flow and its
prediction. Furthermore, the smart city industry also plays an important role
in Big Data and generates various Spatio-temporal data styles [6, 7, 8]
including GPS, sensors, social media, and traffic cards. Driven these urban
Spatio-temporal Big Data, the main challenge a smart city faces can be
summarized in two aspects: (1) how to deal with and analyze large but
redundant Spatio-temporal data, and (2) how to improve human mobility and
optimize travel.

Public transportation accounts for a large proportion of urban transportation.
Taking Beijing as an example, buses produced 1.7 billion vehicle kilometers
traveled and transported 4.9 billion passengers in 2011 alone [9]. The
behavior that people are encouraged to take buses is beneficial to the city’s
sustainable development owning to low-carbon and green mode of buses.
Therefore, the operation management of public transportation directly affects
the traffic circumstance of the city, which the government has always valued.
Many policies have also been adopted to try to improve public transportation,
such as preferential bus fares, bus lanes, additional stops, routes, and bus
running time [10].

However, emerging traffic problems like severe traffic congestion and the
unreasonable allocation of resources have urged researchers to study [11].
Consequently, the new services and requirements are urgent to improve bus
travel and ride experiences, where the passenger flow prediction becomes
critical. As shown in Figure 1, the existing potential problems are solved
through processing and analyzing Spatio-temporal data. One of the most
effective solutions is route optimization, which is a complex and challenging
task, although valuable to the related industry in sustainable transportation
systems. It is not difficult to find that traffic flow prediction is essential
in the whole process of route optimization. If we predict the traffic flow
accurately, we can respond in time to avoid traffic jams and keep roads
smooth.

Due to this demand for flow prediction, plenty of work has contributed to
traffic prediction for a long time. In general, some traffic flow prediction
approaches are built on traditional mathematical statistics [12], such as AR,
ARMA, and ARIMA. On the other hand, as a result of the limitations of
traditional models and the excellent performance of deep learning in
prediction tasks, the deep learning-based methods have been evolved, like DNN
[13], DBN [14], LSTM [15], and GAN [16]. However, the methods mentioned above
only consider the numerical traffic flow based on the statistics of Spatio-
temporal data but neglect the existence of human mobility behavior, which
refers to travel habits and plays a decisive role in the change of traffic
flow. The issue can lead to a lack of definite identification and
differentiation of traffic flow. Therefore, existing works do not identify
mobility behaviors through the relationship between peoples, which results in
a deviation for the final prediction performance of different groups.
Experientially, people in a similar group have similar mobility behaviors. For
example, the actuality that most commuters work from 9 am to 5 pm may mean
that they must travel at least once in the morning and evening and pass
regular bus stops. Therefore, our studies defines a passenger mobility pattern
as a group of people with similar travel routes. Hypothetically, the total
flow consists of two flows: (i) steady flow having from most people with
permanent jobs and residence, and (ii) uncertain flow generated from travel,
entertainment, and so on. However, few studies considered passenger mobility
pattern analysis to predict traffic flow as far as we know.

Figure 1: Application and process of traffic flow prediction.

In recent years, Graph Neural Network (GNN), especially Graph Convolutional
Network (GCN), has effective performance in extracting the features and
relationships of a topological graph. GNN not only represents explicitly the
nodes of the graph in the low-dimensional vector space (also called
embedding), but retains essential attributes [17]. Ordinarily, the embeddings
of nodes can be used in various downstream tasks, including clustering [18],
classification, and prediction [19]. Different from the previous methods
treating Spatio-temporal information of the trajectory data as the main
feature [20], based on the passenger bus record data, we try to define and
construct an interpretable graph structure-based network that can be applied
in GCN based model to explore passenger mobility patterns. Besides, the
adjacent bus stops with a solid Spatio-temporal relationship can improve the
accuracy of traffic flow prediction in the mass transit network. It is
important to note that our studies focus on the prediction, so we do not
consider the fare evasion [21] and certain anomalies [22, 23], which do not
affect the evaluation of the predictive model.

In this paper, we introduce a framework, namely MPGCN, with three stages to
predict passenger flow for the first time. We first obtain related information
of bus stops based on the bus record data, which are used in the analysis of
passenger mobility patterns. Secondly, we construct a sharing-stop network of
passengers, including stop matching and weight assignment of graph edges. The
sharing-stop network is utilized in graph deep clustering with GCN to explore
mobility patterns. Furthermore, to verify their diversity, we execute the
statistical analysis of each mobility pattern by describing heavy-tailed
distributions of the number of bus stops the passengers passed. Then,
considering the spatial correlation of bus route network and temporal
correlation of traffic flow, we propose GCN2Flow combining Spatio-temporal
information to separately predict passenger flow of different patterns, where
the predictive flows for all passenger patterns are fused in the final stage
to obtain the prediction result. Finally, we design a case study for
optimizing routes, where we select optimal routes from candidates of
passengers and set the passenger diversion and experience as the main
optimization objective based on previous prediction results.

The main contributions of this work are summarized as follows:

  * •

We develop a novel prediction framework, namely MPGCN, which integrates the
passenger mobility patterns into passenger flow prediction task to enhance
accuracy. We define a passenger mobility pattern as a group of people with
similar travel times or similar travel routes. Our MPGCN includes three stages
to achieve the prediction: (i) pre-processing the bus record data, (ii)
recognizing passenger mobility patterns, and (iii) predicting passenger flow
by proposed GCN2Flow combined with Spatio-temporal information. Besides, we
design constrained planning as a case study for optimizing routes and thus
improving passenger diversion and experience based on the prediction results.

  * •

We present a sharing-stop network, where the relationship between passengers
is established, and explore the passenger mobility patterns in the sharing-
stop network based on deep clustering with GCN. Through statistical analysis
and data fitness, we suggest the reasonability and interpretability of the
network, as well as the significant laws among different mobility patterns.

  * •

We conduct a series of experiments, including the analysis of passenger
mobility patterns and the comparison with different prediction algorithms with
or without passenger mobility patterns. The predictive evaluation demonstrates
that our framework has better performance and substantially improves passenger
flow prediction. Besides, Prediction is accurate enough to be used for
downstream tasks such as route optimization.

The remainder of this paper is structured as follows. In Section 2, we briefly
review related works. Section 3 mainly illustrates our proposed model and
framework (MPGCN) in detail. Data description and analysis of the experimental
results are given in Section 4. Finally, we present discussions, conclusion
and future work in Section 5 and 6.

##  II Related Work

In this section, we review the existing works closely related to the research
project presented in this paper covering three fields: traffic flow
prediction, human mobility pattern, and graph convolutional network.

###  II-A Traffic Flow Prediction

Traffic flow prediction has many cutting edge applications, such as road
network planning, congestion prevention, and accident detection. Considering
the technical approach applied in prediction, traffic flow prediction models
can be roughly into three categories: (i) traditional mathematical-statistical
parametric, (ii) non-parametric regression, and (iii) artificial neural
network (ANN) models.

The mathematical-statistical parametric models mainly examine the time series
that have a periodic change rule in the urban road traffic, like traffic peak
in the day and night time. These models include autoregressive moving average
(ARMA) [24], and autoregressive integrated moving average (ARIMA) [25].

Kumar et al. [25] utilized the seasonal ARIMA model to design a prediction
scheme using only limited input data. In this model, the issues associated
with huge time-series data like availability, computation, storage, and
maintenance are considered, and the last three days’ flow observations were
used as input for predicting the next day’s flow. Support Vector Regression
(SVR) [26] and Nearest Neighbor Regression [27] are the most popular
nonparametric regression models. With the complexity and diversity increasing
in the road network, there is a demand for more accurate traffic prediction.
Because of the efficacy of ANN for various prediction tasks in complex and
diverse scenarios, it attracts attention to traffic flow prediction. Liu et
al. [13] proposed a novel passenger flow prediction model using a hybrid of
deep network of unsupervised stacked autoencoders (SAE), and supervised deep
neural network (DNN). Besides, Yu et al. [28] introduced Spatio-temporal GCN
(STGCN) model to forecast traffic using graph GNN and Gate CNN for extracting
spatial and temporal features, respectively. More recent works such as T-GCN
[29], and TGC-LSTM [30] further utilized GCN to the extraction of spatial and
temporal correlations to improve prediction. However, all the models presented
in this section only focus on mining the information in the raw data while
ignoring the potential mobility patterns of passengers. For addressing this
research issue, for the first time, this paper aims to discover passenger
mobility behaviors and rules from the bus record data and then utilize them
for traffic flow prediction. Since passenger mobility behaviors and rules are
to be exploited in this paper to predict passenger flow, human mobility
pattern is presented in the next section.

###  II-B Human Mobility Pattern

The fluctuation of traffic flow naturally depends on the human mobility and
travel. Consequently, the analysis of human mobility patterns is of paramount
importance for traffic prediction. The current methods are distinguished
primarily by the type of datasets. For example, two dataset types: (i)
unconscious mobility data (e.g., sensors data, or card records) and (ii)
active sharing mobility data (e.g., traditional diary activity surveys or
social location sharing). Using the former dataset type, Yan et al. [31]
presented a model to capture the underlying driving force accounting for human
mobility patterns based on GPS and mobile phone data. Besides, Qi et al. [32]
designed a multi-step methodology to extract mobility patterns from smart card
data and points of interest data. Nitti et al. [33] presented a Wi-Fi-based
Automatic Bus pAssenger CoUnting System (iABACUS), which did not depends on
passengers card records and can track passengers to analyze urban mobility. In
[34], authors integrated taxi and subway data to compute the human mobility
network, and discover the human mobility patterns in terms of trip
displacement, duration, and interval. On the other hand, people are willing to
share their activities containing location information because of the
convenience and popularity of the social networks, like Weibo and Twitter.
Utilizing the latter, Comito et al. [35] developed a methodology to discover
people, community behavior and travel routes from geo-tagged posts and tweets.
Nevertheless, none of these research works has leveraged human mobility
patterns to predict traffic flow. Therefore, exploring human mobility patterns
from passenger bus data is one of the main aims of the research project
presented in this paper. Since we decide to leverage graph convolutional
network for the traffic flow prediction, the next section presents its
overview.

Figure 2: Framework of the model, MPGCN, where $C_{m}$ and $P_{m}$ represent
cluster and corresponding pattern of passenger mobility.

###  II-C Graph Convolutional Network

With the development of graph learning, there is an extension of CNNs in the
graph (network) as an extensive data structure, like embedding of nodes or
subgraphs into vector spaces. The first convolutional operation on graphs is
presented in [36]. However, it has been evolved over time for its
effectiveness in representing graph [37] and its numerous application domains,
such as node clustering [38], classification [39], prediction [40], and so on.
Besides, to further utilize neighbours’ information, GAT [41] combined multi-
head self-attention mechanism to calculate attention scores of different
neighbours. In this paper, unlike others, a major challenge is to establish an
explainable network from bus record data, which can enable us to discover the
relationship between passengers. Besides, we also need to extract spatial
features of geographical information in the stop network to improve passenger
flow prediction.

##  III Design of Framework

This section provides the details of the theoretical underpinning of our
proposed network and techniques used in our proposed Multi-Pattern GCN based
passenger flow prediction, namely MPGCN framework as shown in Figure 2.

###  III-A Network construction: Sharing-Stop Network

For exploring human mobility patterns, a sharing-stop network is defined as a
weighted undirected graph
$\mathcal{G}_{p}=\left\\{\mathcal{V}_{p},\mathcal{E}_{p},\mathcal{A}_{p}\right\\}$,
where $\mathcal{V}_{p}$ is the set of passenger nodes and $\mathcal{E}_{p}$ is
the set of edges.
$\mathcal{A}_{p}\in\mathbb{R}^{\left|\mathcal{V}_{p}\right|\times\left|\mathcal{V}_{p}\right|}$
is the weighted matrix with each element $a^{p}_{ij}\geq 0$. Specifically, the
edge between passengers $i$ and $j$ denotes their existing relationship of
sharing stops, and weight $a^{p}_{ij}$ indicates the count of the occurrences
of their sharing stops. The pseudocode of the construction of the sharing-stop
network is shown in Algorithm 1. A simple example of this sharing-stop network
is shown in the middle part of Figure 2 based on the empirical assumption that
there are similar records between passengers in the same pattern meaning that
for the same mobility pattern, passengers have a similar number of edges and
the similar value of their weights in the sharing-stop network.

Algorithm 1 The construction of sharing-stop network

0: $P2S$: the list of passengers to stops;

0: $G_{p}$, sharing-stop network;

1: Initialize the graph structure $G_{p}$;

2: for $p_{i},p_{j}$ in $P2S.keys$ do

3: $s_{i},s_{j}\leftarrow P2S[p_{i}],P2S[p_{j}]$; $\backslash\backslash$
obtain stops set of records;

4: $s\\_s\leftarrow s_{i}\cap s_{j}$; $\backslash\backslash$ obtain all
sharing-stops;

5: if $s\\_s$ is empty then

6: continue;

7: end if

8: Initialize $a^{p}_{ij}=0$ in $G_{p}$; $\backslash\backslash$ add an edge;

9: for $s$ in $s\\_s$ do

10: $c_{i},c_{j}\leftarrow s_{i}.count(s),s_{j}.count(s)$;
$\backslash\backslash$ counting;

11: $G_{p}.a^{p}_{ij}+=min(c_{i},c_{j})$; $\backslash\backslash$ update the
weight;

12: end for

13: end for

14: return $G_{p}$;

###  III-B Deep Clustering with GCN

Figure 3: Computational process of deep clustering with GCN.

After constructing the graph, inspired by [38], an unsupervised deep
clustering with GCN is used to mine potential passenger mobility patterns as
shown in Figure 3. First, unsupervised representation method, the basic
autoencoder (AE), is employed to learn the representation of passenger nodes,
that is a mapping function $\Phi:v\in\mathcal{V}_{p}\mapsto\mathbb{R}^{d}$,
where $d\ll\left|\mathcal{V}_{p}\right|$. We assume that there are $L$ layers
in the encoder and decoder parts, which are symmetrical. Therefore, the
representation of the $l$-th layer, $Y^{(l)}$ in the encoder and
$\hat{X}^{(l)}$ in the decoder, can be obtained as follows:

$\left\\{\begin{aligned}
&Y^{(l)}=\phi\left(W_{e}^{(l)}Y^{(l-1)}+b_{e}^{(l)}\right),\\\
&\hat{X}^{(l)}=\phi\left(W_{d}^{(l)}\hat{X}^{(l-1)}+b_{d}^{(l)}\right),\\\
\end{aligned}\right.$ (1)

where $W$ and $b$ are the weight matrix and bias, respectively, and $\phi$ is
the activation function, such as Relu or Sigmoid functions. Besides, the input
of the encoder, $Y^{(0)}$ is X that is initial feature matrix obtained by
previous sharing-stop network, and the output of the decoder is the
reconstruction of $\hat{X}=\hat{X}^{(L)}$. Hence, the loss function of the
entire AE is as follows:

$\mathcal{L}_{1}=\dfrac{1}{2|V|}\left\|X-\hat{X}\right\|^{2},$ (2)

where $||\cdot||$ denotes the Euclidean distance between two representations
matrix.

On the other hand, we integrate these representations into GCN that can learn
them by combining the relationship between passenger nodes. In this part, the
convolutional operation of the $l$-th layer can be defined by:

$H^{(l)}=\phi\left(\tilde{D}^{-\frac{1}{2}}\tilde{A}_{p}\tilde{D}^{-\frac{1}{2}}\tilde{H}^{(l-1)}W^{(l-1)}\right),$
(3)

where $\tilde{A}_{p}=\mathcal{A}_{p}+I$, and $I$ is an identity matrix.
$\tilde{D}_{ii}=\sum_{j}\tilde{a}^{p}_{ij}$ is the degree of node $i$ in
adjacent matrix $A_{p}$, and $W$ is the weight matrix of parameters.
Specially, the input of $l$-th layer in GCN, $\tilde{H}^{(l-1)}$, combines the
representations from the initial GCN and AE:

$\tilde{H}^{(l-1)}=\alpha H^{(l-1)}+(1-\alpha)Y^{(l-1)},$ (4)

Eq. (4) joins GCN with AE. In this case, we uniformly set $\alpha=0.5$. The
final representation of the last layer can be mapped as a multiple
classification probability with softmax function:

$H=softmax\left(\tilde{D}^{-\frac{1}{2}}\tilde{A}_{p}\tilde{D}^{-\frac{1}{2}}H^{(L)}W^{(L)}\right),$
(5)

where $H$ can be regarded as the probability distribution, and $h_{ij}\in H$
denotes the probability of node $i$ in cluster $j$.

For being more suitable for deep clustering, a dual self-supervised method is
employed to combine clustering information with the representation learned
previously. With t-distribution to measure the similarity, the probability of
node $i$ in cluster $j$ is as follows:

$q_{ij}=\dfrac{\left(1+\left\|y_{i}-\mu_{j}\right\|^{2}/n\right)^{-(n+1)/2}}{\sum_{j}\left(1+\left\|y_{i}-\mu_{j}\right\|^{2}/n\right)^{-(n+1)/2}},$
(6)

where $y_{i}$ is from the $Y^{(L)}$, $\mu_{j}$ is the cluster center vector
initialized by the K-means clustering, and $n$ is the degree of freedom of
t-distribution. Therefore, we obtain the clustering probability distribution
$Q=\left\\{q_{ij}\right\\}$. Besides, the target distribution, $P$, can be
computed and normalized as follows:

$p_{ij}=\dfrac{q^{2}_{ij}/\sum_{i}q^{2}_{ij}}{\sum_{k}(q^{2}_{ik}/\sum_{i}q^{2}_{ik})}.$
(7)

Then, we use the KL divergence as part of the loss function, that is
$\mathcal{L}_{2}$ is the KL divergence between $P$ and $Q$ distributions, and
$\mathcal{L}_{3}$ is between $P$ and $H$. In the end, the overall loss
function is defined by:

$\mathcal{L}=\theta_{1}\mathcal{L}_{1}+\theta_{2}\mathcal{L}_{2}+\theta_{3}\mathcal{L}_{3}.$
(8)

where $\theta$ is the hyper-parameters, $\mathcal{L}_{2}=KL(P||Q)$, and
$\mathcal{L}_{3}=KL(P||H)$. The final cluster label of node $i$ is determined
considering the maximum value of $h_{ij}$ from the probability distribution
$H$.

###  III-C Multi-Pattern GCN Based Passenger Flow Prediction

The flow prediction components include identifying passenger patterns,
training neural network model with GCN, and predicting passenger flow. From
the previous results of clustering, passenger nodes under the same cluster
reflect that they have similar mobility rules. Therefore, we divide the
passengers into several mobility pattern groups utilizing the clustering
results, which is also patterns exploration. Besides, we design a statistical
task to discover the potential law by fitting several possible heavy-tailed
distribution [34] shown in Section IV.

Figure 4: The architecture of GCN2Flow, which takes spatial bus route network
($A_{s}$), and time series flows for the passengers in pattern $j$ ($F_{j}$)
as input of TC block and SGC block.

As shown in Figure 4, we develop a prediction architecture, GCN2Flow that
comprises several Temporal Convolutional blocks (TC blocks) and Spatial GCN
blocks (SGC blocks). In this section, the stop network based on routes is
defined as
$\mathcal{G}_{stop}=\left\\{\mathcal{V}_{s},\mathcal{E}_{s},\mathcal{A}_{s}\right\\}$,
where $\mathcal{V}_{s}$ is the set of stop nodes and $\mathcal{E}_{s}$ is the
set of edges. $e^{s}_{ij}\in\mathcal{E}_{s}$ indicates the existence of a
route from the stop $i$ to the next stop $j$. $\mathcal{A}_{s}$ is a weighted
adjacency matrix, whose value of elements denote the geographical distance.

On the one hand, passenger flow prediction leverages historical time series
data i.e., the past $t$ time steps are used to predict the next time step.
Recurrent neural network-based methods are popular in time-series prediction.
However, they have issues, such as time-consuming training and insensitive to
the dynamics of long sequences. Therefore, in our TC block, we define a
temporal gated convolutional operation, which utilizes gated linear units
(GLU) [42] as a non-linearity with the residual connection. We assume that
$C_{in}$, $C_{out}$ are respectively the number of input and output channels,
and $X\in\mathbb{R}^{t\times|\mathcal{V}_{s}|\times C_{in}}$ is the input of
the TC block. The operation is as follows:

$\begin{split}&TC(X)=ReLU((XW_{0}+b_{0})\otimes sigmoid(XW_{1}+b_{1})\\\
&\quad+(XW_{2}+b_{2})),\end{split}$ (9)

where $W\in\mathbb{R}^{k\times C_{in}\times C_{out}}$ (k is the size of
convolutional kernel), $b\in\mathbb{R}^{|\mathcal{V}_{s}|\times C_{out}}$ are
learned parameters, and $\otimes$ is the element-wise product between
matrices.

Note, there are spatial connections between stops of bus routes. For example,
the passenger flow of a stop is related to the flow of its neighboring stops.
Therefore, the spatial graph convolutional operation through Chebyshev
polynomials and first-order approximation [39] can be written as:

$SGC(X)=\phi\left(\tilde{D}^{-\frac{1}{2}}\tilde{A}_{s}\tilde{D}^{-\frac{1}{2}}XW\right),$
(10)

where $\tilde{A}_{s}=\mathcal{A}_{s}+I$, $\tilde{D}$ is degree matrix of the
adjacent matrix $\mathcal{A}_{s}$, and $W$ is the learnable parameter matrix.

Therefore, one TC block and one SGC block are jointly utilized to extract
Spatio-temporal features. The whole computational process of two blocks in
l-th layer is designed as:

$F^{(l)}_{j}=TC(ReLU(SGC(TC(F^{(l-1)}_{j})))),$ (11)

where $F^{(0)}_{j}=F_{j}\in\mathbb{R}^{t\times|\mathcal{V}_{s}|\times
C^{0}_{in}}$ ($C^{0}_{in}=1$ in this case) is the flow matrix of stops with
$t$ time steps in pattern $j$. $ReLU(\cdot)$ is the activation function
(Rectified linear unit). Furthermore, we execute an extra temporal gated
convolutional operation and attach a Fully-Connected (FC) layer as the output
of the whole network. Therefore, $\hat{F}_{j}=FC(TC(F^{(L))})$ is the
prediction flow matrix of next time step. Therefore, the loss function for
passenger flow prediction in pattern $j$ can be defined as:

$\mathcal{L}=\left\|\hat{F}_{j}-F_{j}\right\|^{2}$ (12)

Finally, we train multiple GCN2Flow models, the number of which depends on the
number of passenger mobility patterns. Therefore, each mobility pattern has
its own GCN2Flow model to predict its passenger flow, and then we merge
prediction result of all GCN2Flow models to obtain the total passenger flow
prediction result. Algorithm 2 presents the pseudocode for the training and
predicting process of MPGCN.

Algorithm 2 MPGCN predicts passenger flow

0: $m$: The number of passenger patterns;$F_{j}$: the matrix of stop passenger
flow in the pattern $j$; $A_{s}$: the adjacent matrix of stop network; $T$:
the time-steps of flow sequence;

0: $\hat{F}$: the sequence of total flow prediction results;

1: $normaliztion(A_{s})$;

2: for $j\leftarrow 1$ to $m$ do

3: $normaliztion(F_{j})$;

4: $X,y\leftarrow Samples(F_{j},T)$; $\backslash\backslash$ obtain training
set;

5: building $GCN2Flow_{j}$ network;

6: $GCN2Flow_{j}\leftarrow GCN2Flow_{j}.train(X,y,A_{s})$;

7: $\hat{F}_{j}\leftarrow unnormaliztion(GCN2Flow_{j}.predict)$;

8: $\hat{F}+=\hat{F}_{j}$;

9: end for

10: return $\hat{F}$;

###  III-D Route Optimization

Finally, we use the prediction result of MPGCN to attempt a simple application
case study. Once ensuring the accuracy of passenger flow prediction, we can
assume that the prediction result is the real flow distribution of bus stops
at the next time interval. In our framework, we show an example, route
optimization, which is closely related with flow prediction, and our
optimization task aims at providing a new travel route to avoid crowded bus
stops, thus relieving the pressure of overcrowded bus stops in the public
transportation systems.

Therefore, we mainly focus on passenger diversion and ride experience as the
optimization objective $O$, measured by the standard deviation ($std$) of
traffic flow of all bus stops. More specifically, given the Origin-Destination
($OD$) matrix of passengers (shown in Section IV) and bus route network, how
to select optimal routes from the candidate route set becomes the primary
purpose. Mathematically, the objective function, $O(f)$, is similar with the
standard deviation calculation formula, which means $\nabla^{2}O(f)\geq 0$ and
the domain of variable $f$ is a finite set. Then, the optimal route selection
problem can be abstracted into a convex optimization problem. In other words,
given a stop network $\mathcal{G}_{stop}$ and traffic condition at the next
time interval, the objective is to minimize the $std$ of traffic flow of all
bus stops by changing the travel route of some passengers. Therefore, the
objective function and constraints can be defined as follows:

$\min_{f_{1},f_{2},\ldots,f_{|\mathcal{A}_{s}|}}O(f)=\sqrt{\frac{1}{|\mathcal{A}_{s}|}\sum_{i=1}^{|\mathcal{A}_{s}|}(f_{i}-\bar{f})^{2}},$
(13)

$\begin{split}s.t.,&\left\\{\begin{aligned}
&RS=g_{1}(\mathcal{G}_{stop},OD,\hat{F})\\\ &F^{*}=g_{2}(r),\\\ &f_{i}\in
F^{*},\\\ &t\in T,\\\ &r\in RS,\\\
&len(r)-len(r_{shortest})\leq\epsilon\end{aligned}\right.\end{split}$ (14)

where function $g_{1}()$ can generate candidate routes finite set, $RS$, by
passing in arguments including $\mathcal{G}_{stop}$, $OD$ matrix at time $t$
and the predicted passenger flow at the next time $t+1$, and $g_{2}()$ counts
the passenger flow matrix of all stops based on a candidate route in $RS$.
Besides, in the process of generating candidate routes set, we would set a
threshold $\epsilon$ to ensure minimal additional cost of passenger travel
time, that is, $len(r)-len(r_{shortest})\leq\epsilon$ ($\epsilon=5$ in this
part), $r\in RS$, where $r_{shortest}$ is the shortest travel route based on
$OD$. As a result, we can obtain the optimal routes of passengers, which can
make the passenger flow of bus stops more balanced and relieve the crowded
situation on the bus to a certain extent.

###  III-E Complexity Analysis

In the part of deep clustering, we denote $d_{l}$ as the dimension of the
input of $l-th$ layer in the autoencoder. The time complexity of the
autoencoder is $\mathcal{O}(|\mathcal{V}_{p}||X|d_{1}^{2}\cdots d_{L}^{2})$,
and the time complexity of GCN module is
$\mathcal{O}(|\mathcal{E}_{p}||X|d_{1}\cdots d_{L})$. Besides, we assume that
there are K clusters, and the time complexity of (6) is
$\mathcal{O}(|\mathcal{V}_{p}|K+|\mathcal{V}_{p}|log|\mathcal{V}_{p}|)$.
Therefore, the total time complexity is the sum of the above three, and is
linearly related to the $|\mathcal{V}_{p}|$ and $|\mathcal{E}_{p}|$.
Similarly, the time complexity of flow prediction method is
$\mathcal{O}(|\mathcal{E}_{s}||\mathcal{V}_{s}|d_{1}\cdots d_{L})$.

##  IV Experiments

To demonstrate the efficiency of our proposed MPGCN, we conducted a series of
experiments. In this section, firstly, we describe the experimental dataset in
detail, including preprocessing of data, analysis of data, and sharing-stop
network. Secondly, we show the related parameters setting in experiments.
Next, we present the analysis of mobility patterns and the effectiveness
evaluation of the prediction performance compared with other methods. Finally,
we suggest the application value of our prediction results through a case
study.

###  IV-A Data Description and Analysis

####  IV-A1 Data Description

The real-world bus dataset is employed in our experiments, a typical kind of
Spatio-temporal data, shown in TABLE I and TABLE II that contains bus record
dataset from bus card, credit card, and Qr code, and bus stop arriving-leaving
dataset comprising 12 used fields, which can basically cover the majority of
bus passengers and reflect the overall trend of passenger mobility. Besides,
the information about bus stops includes longitude, latitude, and the sequence
of bus stops in the route. The bus dataset was generated by buses in Jiangsu,
by Panda Bus Company, for 30 days (nine weekend days and 21 weekdays) from
November 1st to 30th, 2019, and 18 hours a day from 05:00 to 23:00. It is
noted that we do not use passengers’ private information, so there is no
privacy issue with our data.

TABLE I: Description of the bus record dataset Field | Annotation | Examples
---|---|---
bus_no | ID of each bus | 11180
card_no | ID of each passenger | 2230000010282075
cardType | Payment card type | 1
riding_time | Record time and date | 2019-11-01 05:29:20
routeId | ID of each route | 106
TABLE II: Bus stop arriving-leaving dataset details Field | Annotation | Examples
---|---|---
bus_no | ID of each bus | 61189
enterTime | Enter stop time and date | 2019-11-01 06:37:59
leaveTime | Leave stop time and date | 2019-11-01 06:38:12
stopId | ID of each stop | 46976
routeId | ID of each route | 157
directId | 0 for upline, 1 for downline | 0
stayTime | Bus waiting time (seconds) | 13
Figure 5: A example of passenger flow trend on November 1st, 2019.

####  IV-A2 Preprocessing and Analysis

From the raw data, we could not directly obtain bus stops where the passengers
get on the bus and scan their card or Qr code. Hence, we first need to match
bus stops. Considering the real-world experience of bus riding in China, the
bus may have already run when passengers scan their card or Qr code. This fact
implies the scanning time may not be between entering and leaving time and
thus has a certain deviation. Consequently, we empirically selected 20 seconds
to increase the time interval to expand the matching time range. Algorithm 3
presents the technique for matching stops. Another difficulty with data
preprocessing is that the drop-off stops of passengers are not given, unlike
subway travel, which means the destination of passengers is not clear.
Usually, travel by bus is symmetrical. For example, passengers’ origin stop
and destination will be switched to return to the origin stop. Based on this
assumption, we will extract all getting-on stops and corresponding bus lines,
and the two stops will be regarded as the origin and destination if these two
stops are on the same line for a certain passenger. Therefore, the symmetrical
$OD$ matrix can be inferred.

Algorithm 3 Matching stops

0: $Ride\\_Records$: The table based on bus record data; $Bus\\_Records$: the
table based on bus stop arriving-leaving data; $\tau$: the time interval;

0: $P2S$: the dictionary of matching stop;

1: Load $Bus\\_Records$; $\backslash\backslash$ convert to specific data
structure for easy retrieve;

2: for $i$ in $Ride\\_Records$ do

3: $temp\leftarrow Bus\\_Records.where(i)$ $\backslash\backslash$ obtain
retrieve information based on bus id and date;

4: for $j$ in $temp$ do

5: if $i.riding\\_time.time\geq j.enterTime-\tau$ and
$i.riding\\_time.time\leq j.leaveTime+\tau$ then

6: $\backslash\backslash$ matching condition;

7: add $j.stopId$ to $P2S[i.card\\_no]$;

8: break;

9: end if

10: end for

11: end for

12: return $P2S$;

Figure 6: The heavy-tailed distribution of the number of passengers, who pass
a certain number of stops (a), and the number of stops that have a certain
number of records (b). Figure 7: The distribution of degrees of all passenger
nodes.

After matching stops and inferring the $OD$ matrix, we expand the $OD$ matrix
into stop trajectories, which enable us to count passenger flow at each stop.
Besides, the number of records per passenger is required to be higher than a
particular value. This higher number of records is required because of our
demand for exploring passenger mobility and its laws. For this, some
passengers and their records are needed to be filtered. For example,
passengers having a few records in a month or starting to generate a card
record end of the month were filtered. Also, we found data anomalies like the
missing value problem among the raw data. For example, bus stop arriving-
leaving data of some buses for several days is missing, influencing model
training. Hence, inspired by [22], we use the linear interpolation method to
reduce errors during the computing of traffic flow. The matching process
screens some records having less impact on passenger mobility laws. Finally,
the data extracted by us contains 857900 bus records of 31353 passengers, 214
routes, and 1114 stops in Huai’an city.

Apart from data preprocessing, cleaning, and filtering, we analyze the
relevance of passenger flow and time. In Figure 5, we list passenger flow for
one day (November 1st, 2019). Figure 5 shows daily flow is similar in shape
i.e., there are 2 or 3 peaks and 1 or 2 troughs. Therefore, this similarity
also means that not only is traffic flow regular, but also that passenger
mobility follows the law. Besides, as shown in Figure 6, we calculate the
number of stops that each passenger passes and the average daily number of
records at each stop in a month and describe their distribution based on a
certain order of magnitude after counting them. Figure 6 exhibits both
distributions conform with the heavy-tailed distribution, which is why our
network embedding part is inspired. The existence of heavy-tailed distribution
is the main reason for the latent effectiveness in the process of natural
language model and network representation.

After preprocessing, the sharing-stop network is constructed with Algorithm 1.
As shown in Figure 7, we count the degrees of all passenger nodes in the
network and draw their distribution, which suggests the analogous
distribution, an expected heavy-tailed distribution, and shows the potential
law of passenger mobility.

(a) time_step=5 min

(b) time_step=15 min

(c) time_step=30 min

Figure 8: The prediction results with different number of clusters, where
$n\\_cluster=1$ denotes prediction without passenger patterns. (a) time_step=5
min. (b) time_step=15 min. (c) time_step=30 min.

###  IV-B Experimental Settings

In the part of deep clustering with GCN, we extracted passenger mobility
patterns based on the sharing-stop network. Since the size of the sharing-stop
network is large, we set the dimension of the neural network of AE to
$\left|\mathcal{V}_{p}\right|$-100-100-500-16, which was the same as the GCN
module. In addition, the result of our method is insensitive to hyper-
parameters, therefore the setting of hyper-parameters is
$(\theta_{1},\theta_{2},\theta_{3})=(1,0.5,0.05)$. The learning rate and epoch
number were 0.001 and 100, respectively. For considering the impact of cluster
number on the passenger flow prediction comprehensively, we set 3, 4, and 5 as
the number of clusters (passenger mobility patterns), and selected the most
suitable number of passenger mobility patterns to analyze their latent laws
based on the prediction results.

For flow prediction, the historical passenger flow data for an hour were used
as the input of our proposed method to predict the flow for the next time
step, and the time step was taken as 5, 15, and 30 minutes, respectively.
There were 5 TC blocks and 2 SGC blocks in our GCN2Flow. The convolution
kernel size of both blocks was 3. The batch size and the learning rate were 64
and 0.001 with epochs 100, respectively. Before training, the flow of all bus
stops was normalized with the Z-score method, and the stop network as Laplace
matrix was also normalized.

Further, similar with previous works [28, 4], we utilized the following three
most common metrics used in the comparison of passenger flow prediction
methods: Mean Absolute Error (MAE), Root Mean Square Error (RMSE), and
Correlation Coefficient (CC).

  * -

Mean Absolute Error (MAE). MAE is the mean of all absolute errors between the
predicted values and their corresponding real values, whose equation is given
as follows:

$MAE=\dfrac{1}{n}\sum_{i=1}^{n}\left|\hat{y_{i}}-y_{i}\right|$ (15)

where $\hat{y_{i}}$ and $y_{i}$ denote the predicted values and real values,
respectively.

  * -

Root Mean Square Error (RMSE). RMSE measures the deviation between predicted
values and their respective real values. RMSE is defined as:

$RMSE=\sqrt{\dfrac{\sum_{i=1}^{n}\left|\hat{y_{i}}-y_{i}\right|^{2}}{n}}$ (16)

  * -

Correlation Coefficient (CC). CC is used to verify the correlation between
variables and has different forms. In this paper, we used Pearson CC to
measure correlation possessing the following formula:

$CC=\dfrac{cov(\hat{y_{i}},y_{i})}{\sqrt{var(\hat{y_{i}})\cdot var(y_{i})}}$
(17)

where $cov(\cdot,\cdot)$ and $var(\cdot)$ represent the covariance and
variance, respectively.

In addition, our model is implemented based on Pytorch framework, and the
experiments is executed with NVIDIA RTX 2080 Ti.

###  IV-C Analysis of Passenger Mobility Patterns

To investigate the impact of extracting passenger mobility patterns on
prediction, we varied the number of clusters used in prediction models. In
Figure8, $n\\_cluster=1$ indicates the GCN2Flow and LSTM [43] models were
directly used to predict passenger flow, while $n\\_cluster$=3, 4, and 5 means
that the MPGCN and Multi-pattern LSTM (MP-LSTM) models were used to predict
flow of passengers for 3, 4, and 5 different mobility patterns, respectively.
Figure 8 shows it is effective to enhance the performance of prediction
combining passenger mobility patterns i.e., MPGCN and Multi-pattern LSTM (MP-
LSTM) are better than GCN2Flow and LSTM, respectively.

As a result, the MPGCN and Multi-pattern LSTM (MP-LSTM) models produced the
best performance for $n\\_cluster=4$. Therefore, we selected $n\\_cluster=4$
as the number of passenger mobility patterns for further analysis. In our
studies, a clustering result is viewed as a mobility pattern. Due to the
basics of the sharing-stop network, we suspect that passenger nodes in the
same pattern tend to have similar travel habits, like taking fixed and
frequent bus stops or routes. In this way, the number of passengers in the
four patterns is 11857, 10537, 3475, and 5484, which add up to 31353.

To further mine special laws hidden in mobility patterns, we show several
heavy-tail distributions to fit the number of stops passengers pass ($n_{s}$),
which are power-law, exponential, log-normal, and Weibull distributions. The
probability density function (pdf) of these distribution are shown in TABLE
IV. From Figure 9, for Patterns 1, 2 and 3, the distributions of $n_{s}$ have
similar law i.e., log-normal and Weibull distributions are better fitting
curves than the remaining two distributions (power-law and exponential).
Before $P(n_{s})$ reaches the highest value, the Weibull distribution has a
better fitting effect, and after that, the log-normal distribution becomes
better. Besides, by comparing key parameters of distributions, $c\simeq
87,91,92$ in pdf of log-normal distribution; $a\simeq 99,102,99$ and $r\simeq
1.8,1.9,1.7$ in pdf of Weibull distribution, the similarity between log-normal
and Weibull distributions can also be further confirmed. For Pattern 4 and
$c\simeq 71$ in pdf of log-normal distribution and $a\simeq 73,r\simeq 1.4$ in
pdf of Weibull distribution, log-normal distribution achieves the best
fitting. More specifically, through quantitative analysis, we note that 80
percent of passengers of Patterns 1, 2, and 3 tend to pass around less than or
equal to 127 stops, while 80 percent of passengers of Pattern 4 only pass less
than or equal to 101 stops.

Furthermore, in order to verify our conjecture that passengers in the same
pattern tend to have similar travel habits, we count the flow contribution of
passengers of four mobility patterns in each bus route and analyze the
distribution proportion of the top 40 bus routes in terms of total passenger
flow. Then, we define the route preference of the pattern, which denotes the
proportion of passengers of this pattern in the route exceeds 50%. As shown in
TABLE III (see Appendix for details), noticeable preference differences of
mobility patterns can be found. For example, passengers of pattern 4
contribute more than 90% on routes 62, 63, 65, and 66. Particularly, for the
routes not shown in TABLE III, we also found that the proportion of pattern 1
and pattern 2 is relatively high and close, both of which are above 30% or
40%, such as routes 2, 4, 16, 26, and 31. This fact indicates that there is a
specific shared similarity between the two mobility patterns in terms of
travel. Therefore, through deep clustering, the effectiveness of our implicit
mobility pattern extraction is verified by these analysis results. In other
words, passengers of the same pattern tend to travel by bus on some fixed
routes and contribute most of the traffic flow in those routes, while
passengers with different patterns often choose different routes to travel.
Besides, based on the latent laws of mobility patterns, it is effective to
combine them with traffic flow prediction task.

TABLE III: Route preference of four mobility patterns Pattern No. | List of Route Preference
---|---
1 | [5, 7, 12, 15, 18, 19, 32, 33, 36, 39, 53, 88, 89, 100]
2 | [1, 6, 11, 14, 22, 23, 28, 38, 116, K1]
3 | [50, 91, 713]
4 | [10, 20, 62, 63, 65, 66, 69]
TABLE IV: Heavy-tailed distributions Distribution | Probability Density Function (pdf)
---|---
Power-law | $ax^{b}$
Exponential | $a\cdot\exp(bx)$
Lognormal | $\frac{A}{xw\sqrt{2\pi}}\exp[-\frac{(\ln(x/c))^{2}}{2w^{2}}]$
Weibull | $\frac{r}{a}(\frac{x-u}{a})^{r-1}\exp[-(\frac{x-u}{a})^{r}]$

(a) Pattern 1

(b) Pattern 2

(c) Pattern 3

(d) Pattern 4

Figure 9: Description about four mobility patterns of passengers with data fitness. TABLE V: Performance comparison of different approaches Methods | LR | SVR | GBDT | ARIMA | LSTM | DCRNN | STGCN | MP-LSTM | GCN2Flow | MPGCN
---|---|---|---|---|---|---|---|---|---|---
t_step=5 min | MAE | 21.56 | 22.62 | 22.85 | 23.90 | 15.30 | 13.93 | 14.01 | 13.98 | 13.81 | 9.16
RMSE(%) | 35.14 | 37.45 | 37.85 | 43.68 | 23.76 | 21.28 | 22.25 | 17.88 | 20.41 | 15.82
CC | 0.823 | 0.942 | 0.968 | 0.955 | 0.975 | 0.983 | 0.978 | 0.980 | 0.986 | 0.992
t_step=15 min | MAE | 70.27 | 67.52 | 68.36 | 70.72 | 51.04 | 50.06 | 48.96 | 49.08 | 50.28 | 45.23
RMSE(%) | 115.26 | 111.74 | 113.28 | 130.41 | 99.82 | 92.33 | 91.45 | 92.56 | 89.39 | 81.33
CC | 0.901 | 0.945 | 0.972 | 0.953 | 0.973 | 0.976 | 0.979 | 0.976 | 0.978 | 0.984
t_step=30 min | MAE | 164.69 | 155.73 | 155.92 | 161.99 | 153.69 | 137.31 | 144.52 | 144.78 | 142.05 | 130.03
RMSE(%) | 283.58 | 270.42 | 294.71 | 321.23 | 279.82 | 255.09 | 267.62 | 268.09 | 260.88 | 240.48
CC | 0.885 | 0.937 | 0.960 | 0.952 | 0.954 | 0.968 | 0.964 | 0.964 | 0.966 | 0.975

###  IV-D Passenger Flow Prediction

####  IV-D1 Prediction Result

Based on the passenger mobility patterns obtained from the previous
experiments, using GCN2Flow (MPGCN model described in Algorithm 2 for
individual patterns), we predicted the passenger flow for each pattern. Figure
10 shows the short-term passenger flow prediction results of our proposal
GCN2Flow and MPGCN with $time\\_step=5$ for a weekday and a weekend day. The
comparison between the predicted flow with the real flow justifies that the
excellent prediction result is achieved. For different trends of weekdays and
weekend days, our models both capture the features of passenger flow trends
i.e., flow peaks and troughs. In terms of spatial features, the SGC block is
capable of fast predicting the dynamic flow changes in the stop network based
on the bus route network. Moreover, by combining passenger flow predictions
using MPGCN, the prediction accuracy can be improved.

(a) Weekday (Nov. 29th, 2019)

(b) Weekend day (Nov. 30th, 2019)

Figure 10: Prediction results of MPGCN and GCN2Flow with time_step=5 min
including a weekend day (a), and a weekday (b). (Zoom in suitable view during
a peak and a trough period)

####  IV-D2 Comparison of prediction approaches

To verify the potential capability of our approach, we predicted passenger
flow using the same dataset by many contemporary and popular relevant models
that include machine learning models, mathematical-statistical model, and
neural networks model: Logistic Regression (LR), Support Vactor Regression
(SVR), Gradient Boosting Decision Tree (GBDT), ARIMA, LSTM [43], DCRNN [44],
STGCN [28], MP-LSTM (LSTM with passenger mobility patterns).

The results of prediction evaluation are presented in TABLE V. Our proposed
MPGCN achieves the best performance in all three evaluation metrics. In
general comparison, because of the complexity of data, the mathematical-
statistical model, ARIMA, is the worst at predicting. Machine learning models
have similar prediction performance, i.e., they can predict well for short-
term flow, while their prediction accuracy is seriously reduced for the long-
term without considering the relationship of spatial geographic information.
Although the prediction performance of the neural networks model, LSTM, is
respectful, which has better prediction results than those for the
mathematical-statistical model and other machine learning models, it is still
inferior to our models. It’s worth mentioning that the results of STGCN and
DCRNN are close to our GCN2Flow. Besides, in terms of passenger mobility
patterns, when applying them in the prediction model (MP-LSTM), its
performance can be further enhanced. In particular, for the $time\\_step=30$
setting, MPGCN achieves 5.3% ($137.31\rightarrow 130.03$) MSE reduction
compared to other baselines. To sum up, the ability of GCN2Flow and the
effectiveness of combining passenger mobility patterns, MPGCN vindicate their
application in the passenger flow prediction.

Figure 11: The route optimization results compared with : the trend of (a)
passenger flow, and (b) standard deviation of normalized flow. (Zoom in
suitable view during a peak and a trough period)

###  IV-E A Case Study of Route Optimization

On the one hand, passenger flow prediction can be supplied to many downstream
tasks. On the other hand, the feedback results of downstream tasks can also
verify the accuracy of prediction. In our case, we define a route optimization
task for allocating passenger flow and improving travel experience on the bus,
which demonstrates the value of our proposed MPGCN in another way.

In the experiment, based on the OD matrix, we utilize prediction results for
recommending an optimal route to each passenger, which meets objective
function and constraint conditions (Eq. 13, 14). We select the data of the
last day in the dataset to carry out the optimization experiment. Then, we
recount the last day’s flow after optimizing passengers’ travel routes and
calculate the standard deviation of the flow of all bus stops as a simple
evaluation metric. From Figure 11, our route optimization has little impact on
passenger flow because of our constraint conditions. On the other hand, it
reduces $std$, which means balancing the flow of all bus stops, reducing the
probability of congestion on the bus, and achieving traffic diversion in bus
travel. Hence, the prediction results of our MPGCN are accurate enough to be
effectively applied in traffic flow-based downstream tasks.

##  V Discussion

Overall, our studies focus on solving the problem of passenger traffic
prediction using a novel concept called passenger mobility pattern. Deep
clustering with GCN, according to the result analysis, can implicitly extract
passenger mobility patterns in the sharing-stop network. In terms of spatial
characteristics, passengers of the same mobility pattern have high
similarities. That is to say, they share similar travel bus stops and routes,
and their contributions to specific routes’ flow are dominant. However, our
established sharing-stop network does not include the relationship of
passenger travel time, so we were unable to uncover any potential temporal-
related laws in the extracted mobility patterns, which merits more
investigation in future. Besides, our studies can also be used in other modes
of transport like the subway. However, it should be highlighted that we are
primarily interested in mobility patterns based on frequent and consistent
travel, which necessitates sufficient co-occurrence relationship for
passengers. Therefore, our method may not be suitable for the traffic flow
prediction task of infrequently used transport mode. For example, if a
passenger only travels by air once or twice a year, it is hard to discover
their mobility patterns.

In addition, the route optimization problem in public transport systems
involves a variety of specific tasks on different scenarios, including route
network design, frequency setting, timetable optimization [45], schedule
optimization [46], and passenger assignment adjustment. Travel time, waiting
time, path length, amount of crowding on the buses, and other objective
functions are all varied due to different sub-problems. [47]. In essence, our
case study of route optimization is about passenger assignment adjustment,
thus we do not operate on route design, bus timetables, or schedules. Unlike
mentioned above, our optimization aims to passenger diversion and lower level
of bus crowding, as stated in Section III-D. It is also understandable that
passengers can be informed of route congestion and recommended an alternate
travel route to alleviate the overcrowded at bus stops. Furthermore, there are
also shortcomings in our route optimization. For example, the new route
selected in the optimization may be longer than the original route, resulting
in longer travel time or more transfers times. Therefore, our case study is
merely a naive application example, which can demonstrate the advantages of
passengers prediction in our MPGCN, but it also provides researchers with
another idea to extend more applications in practical industrial application.

##  VI Conclusion and Future Work

In this paper, we introduced forward a passenger flow prediction framework,
MPGCN, including the sharing-stop network construction, passenger mobility
patterns recognition, and passenger flow prediction. We executed experiments
to analyze extracted mobility patterns, and we discovered that different
mobility patterns can fit heavy-tailed distributions well and have their own
travel laws and route preference. Our framework gave full consideration to the
impact of passenger mobility patterns on prediction. We conducted extensive
experiments to demonstrate that MPGCN can accurately predict bus passenger
flow based on the real bus record data. Finally, we design a simple case
study, which shows the value and application of our accurate prediction in the
downstream tasks, like route optimization. Besides, prediction results of
MPGCN can be applied extensively in other services and strategies of ITS for
sustainable public transportation, such as subsequent bus scheduling, route
planning, and congestion management.

When sufficient multi-source sensors data is available, we will attempt to
provide fine-grained analysis and service based on human mobility patterns.
For further research, considering specific Spatio-temporal information, we
will construct different personal mobility prediction architectures.

[Analysis of Passenger Mobility Patterns]

TABLE VI shows flow contribution proportion of passengers of four mobility
patterns in the top 40 bus routes by total passenger flow, which is used to
analyze the route preferences of mobility patterns and travel rules.

TABLE VI: Distribution proportion of passengers of four mobility patterns Route No. | Pattern No. (%) | Total flow | Route No. | Pattern No. (%) | Total flow
---|---|---|---|---|---
1 | 2 | 3 | 4 | 1 | 2 | 3 | 4
1 | 31.38 | 65.48 | 1.61 | 1.53 | 51736 | 32 | 67.47 | 13.67 | 18.37 | 0.49 | 15335
28 | 28.57 | 62.74 | 7.18 | 1.51 | 31822 | 89 | 95.62 | 2.98 | 1.09 | 0.31 | 15278
16 | 47.9 | 49.08 | 2.13 | 0.89 | 28659 | 33 | 64.29 | 16.68 | 17.83 | 1.2 | 14689
3 | 42.37 | 18.18 | 39.06 | 0.4 | 26413 | 53 | 62.31 | 17.14 | 20.14 | 0.41 | 14543
4 | 44.77 | 30.65 | 18.6 | 5.98 | 24472 | 38 | 20.38 | 70.68 | 6.59 | 2.35 | 14354
10 | 2.95 | 32.7 | 1.63 | 62.72 | 23871 | 50 | 18.98 | 17.23 | 58.64 | 5.16 | 14233
12 | 74.03 | 21.6 | 2.52 | 1.84 | 23593 | 63 | 0.3 | 1.74 | 0.47 | 97.49 | 14167
69 | 22.57 | 12.81 | 10.32 | 54.3 | 22987 | 14 | 4.67 | 85.88 | 2.11 | 7.34 | 12390
11 | 28.1 | 64.2 | 6.32 | 1.38 | 22418 | 88 | 64.2 | 14.78 | 17.6 | 3.43 | 11007
26 | 36.95 | 45.66 | 12.87 | 4.52 | 21992 | 91 | 19.85 | 19.45 | 59.51 | 1.18 | 10900
2 | 37.83 | 45.26 | 16.47 | 0.45 | 21705 | 6 | 24.9 | 72.96 | 0.99 | 1.16 | 10893
23 | 20.23 | 65.06 | 13.94 | 0.77 | 21225 | 65 | 1.64 | 5.62 | 2.32 | 90.43 | 10884
18 | 66.34 | 14.83 | 17.81 | 1.02 | 21199 | 5 | 73.25 | 19.92 | 5.45 | 1.38 | 10689
116 | 44.96 | 52.65 | 1.61 | 0.79 | 21103 | 100 | 81.18 | 14.96 | 2.98 | 0.89 | 10504
31 | 42.51 | 46.65 | 9.57 | 1.26 | 18991 | 39 | 87.42 | 9.75 | 1.33 | 1.51 | 10291
22 | 35.62 | 61.89 | 1.84 | 0.65 | 18792 | 66 | 0.56 | 1.39 | 0.28 | 97.76 | 10192
7 | 68.24 | 27.26 | 4.17 | 0.33 | 17846 | 20 | 1.62 | 15.48 | 0.47 | 82.44 | 9872
62 | 1.52 | 2.1 | 1.13 | 95.24 | 17319 | 713 | 18.21 | 19.56 | 60.81 | 1.42 | 9664
36 | 79.62 | 16.33 | 3.59 | 0.46 | 17060 | K1 | 37.68 | 58.37 | 1.6 | 2.34 | 9660
15 | 76.89 | 17.74 | 4.97 | 0.4 | 16705 | 19 | 94.81 | 3.54 | 0.94 | 0.71 | 9633

## References

  * [1] E. Sisinni, A. Saifullah, S. Han, U. Jennehag, and M. Gidlund, “Industrial internet of things: Challenges, opportunities, and directions,” _IEEE Transactions on Industrial Informatics_ , vol. 14, no. 11, pp. 4724–4734, 2018\.
  * [2] M. R. Rahimi, N. Venkatasubramanian, S. Mehrotra, and A. V. Vasilakos, “On optimal and fair service allocation in mobile cloud computing,” _IEEE Transactions on Cloud Computing_ , vol. 6, no. 3, pp. 815–828, 2018.
  * [3] X. Kong, S. Tong, H. Gao, G. Shen, K. Wang, M. Collotta, I. You, and S. Das, “Mobile edge cooperation optimization for wearable internet of things: A network representation-based framework,” _IEEE Transactions on Industrial Informatics_ , 2020.
  * [4] X. Kong, M. Li, T. Tang, K. Tian, L. Moreira-Matias, and F. Xia, “Shared subway shuttle bus route planning based on transport data analytics,” _IEEE Transactions on Automation Science and Engineering_ , vol. 15, no. 4, pp. 1507–1520, 2018.
  * [5] S. Ruan, J. Bao, Y. Liang, R. Li, T. He, C. Meng, Y. Li, Y. Wu, and Y. Zheng, “Dynamic public resource allocation based on human mobility prediction,” _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ , vol. 4, no. 1, 2020\.
  * [6] G. Atluri, A. Karpatne, and V. Kumar, “Spatio-temporal data mining: A survey of problems and methods,” _ACM Comput. Sur._ , vol. 51, no. 4, 2018.
  * [7] R. Du, P. Santi, M. Xiao, A. V. Vasilakos, and C. Fischione, “The sensable city: A survey on the deployment and management for smart city monitoring,” _IEEE Communications Surveys Tutorials_ , vol. 21, no. 2, pp. 1533–1560, 2019\.
  * [8] S. Wang, J. Cao, and P. Yu, “Deep learning for spatio-temporal data mining: A survey,” _IEEE Transactions on Knowledge and Data Engineering_ , 2020.
  * [9] J. Zhou, E. Murphy, and Y. Long, “Commuting efficiency in the beijing metropolitan area: an exploration combining smartcard and travel survey data,” _Journal of Transport Geography_ , vol. 41, pp. 175–183, 2014.
  * [10] F. Pili, A. Olivo, and B. Barabino, “Evaluating alternative methods to estimate bus running times by archived automatic vehicle location data,” _IET Intelligent Transport Systems_ , vol. 13, no. 3, pp. 523–530, 2019.
  * [11] A. Mourad, J. Puchinger, and C. Chu, “A survey of models and algorithms for optimizing shared mobility,” _Transportation Research Part B: Methodological_ , vol. 123, pp. 323–346, 2019.
  * [12] M. Gan, Y. Cheng, K. Liu, and G. lin Zhang, “Seasonal and trend time series forecasting based on a quasi-linear autoregressive model,” _Applied Soft Computing_ , vol. 24, pp. 13–18, 2014.
  * [13] L. Liu and R.-C. Chen, “A novel passenger flow prediction model using deep learning methods,” _Transportation Research Part C: Emerging Technologies_ , vol. 84, pp. 74–91, 2017.
  * [14] Y. Bai, Z. Sun, B. Zeng, J. Deng, and C. Li, “A multi-pattern deep fusion model for short-term bus passenger flow forecasting,” _Applied Soft Computing_ , vol. 58, pp. 669–680, 2017.
  * [15] B. Du, H. Peng, S. Wang, M. Z. A. Bhuiyan, L. Wang, Q. Gong, L. Liu, and J. Li, “Deep irregular convolutional residual lstm for urban traffic passenger flows prediction,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 3, pp. 972–985, 2020.
  * [16] Y. Zhang, S. Wang, B. Chen, J. Cao, and Z. Huang, “Trafficgan: Network-scale deep traffic prediction with generative adversarial nets,” _IEEE Transactions on Intelligent Transportation Systems_ , pp. 1–12, 2019.
  * [17] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in _International Conference on Learning Representations (ICLR)_ , 2019.
  * [18] G. Shen, Z. Zhao, and X. Kong, “Gcn2cdd: A commercial district discovery framework via embedding space clustering on graph convolution networks,” _IEEE Transactions on Industrial Informatics_ , 2021, doi: 10.1109/TII.2021.3051934.
  * [19] X. Han, G. Shen, X. Yang, and X. Kong, “Congestion recognition for hybrid urban road systems via digraph convolutional network,” _Transportation Research Part C: Emerging Technologies_ , vol. 121, p. 102877, 2020.
  * [20] Z. Pan, Z. Wang, W. Wang, Y. Yu, J. Zhang, and Y. Zheng, “Matrix factorization for spatio-temporal neural networks with applications to urban flow prediction,” in _Proceedings of the 28th ACM International Conference on Information and Knowledge Management_ , ser. CIKM ’19. Association for Computing Machinery, 2019, pp. 2683–2691.
  * [21] B. Barabino, C. Lai, and A. Olivo, “Fare evasion in public transport systems: a review of the literature,” _Public Transport_ , vol. 12, pp. 27–88, 2020, doi: https://doi.org/10.1007/s12469-019-00225-w.
  * [22] F. McLeod, “Estimating bus passenger waiting times from incomplete bus arrivals data,” _Journal of the Operational Research Society_ , vol. 58, no. 11, pp. 1518–1525, 2007, doi: 10.1057/palgrave.jors.2602298.
  * [23] B. Barabino, M. Di Francesco, and S. Mozzoni, “Time reliability measures in bus transport services from the accurate use of automatic vehicle location raw data,” _Quality and Reliability Engineering International_ , vol. 33, no. 5, pp. 969–978, 2017.
  * [24] N. Sadek and A. Khotanzad, “Multi-scale high-speed network traffic prediction using k-factor gegenbauer arma model,” in _2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577)_ , vol. 4, 2004, pp. 2148–2152.
  * [25] S. V. Kumar and L. Vanajakshi, “Short-term traffic flow prediction using seasonal arima model with limited input data,” _European Transport Research Review_ , vol. 7, no. 3, p. 21, 2015.
  * [26] W. Ge, Y. Cao, Z. Ding, and L. Guo, “Forecasting model of traffic flow prediction model based on multi-resolution svr,” in _Proceedings of the 2019 3rd International Conference on Innovation in Artificial Intelligence_ , ser. ICIAI 2019. Association for Computing Machinery, 2019, pp. 1–5.
  * [27] P. Dell’Acqua, F. Bellotti, R. Berta, and A. De Gloria, “Time-aware multivariate nearest neighbor regression methods for traffic flow prediction,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 16, no. 6, pp. 3393–3402, 2015.
  * [28] B. Yu, H. Yin, and Z. Zhu, “Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting,” in _Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI)_ , 2018\.
  * [29] L. Zhao, Y. Song, C. Zhang, Y. Liu, P. Wang, T. Lin, M. Deng, and H. Li, “T-gcn: A temporal graph convolutional network for traffic prediction,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 9, pp. 3848–3858, 2020.
  * [30] Z. Cui, K. Henrickson, R. Ke, and Y. Wang, “Traffic graph convolutional recurrent neural network: A deep learning framework for network-scale traffic learning and forecasting,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 11, pp. 4883–4894, 2020.
  * [31] X. Yan, C. Zhao, Y. Fan, Z. Di, and W. Wang, “Universal predictability of mobility patterns in cities,” _Journal of the Royal Society Interface_ , vol. 11, no. 100, p. 20140834, 2014.
  * [32] G. Qi, A. Huang, W. Guan, and L. Fan, “Analysis and prediction of regional mobility patterns of bus travellers using smart card data and points of interest data,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 4, pp. 1197–1214, 2019.
  * [33] M. Nitti, F. Pinna, L. Pintor, V. Pilloni, and B. Barabino, “iabacus: A wi-fi-based automatic bus passenger counting system,” _Energies_ , vol. 13, no. 6, p. 1446, 2020.
  * [34] F. Xia, J. Wang, X. Kong, Z. Wang, J. Li, and C. Liu, “Exploring human mobility patterns in urban scenarios: A trajectory data perspective,” _IEEE Communications Magazine_ , vol. 56, no. 3, pp. 142–149, 2018.
  * [35] C. Comito, D. Falcone, and D. Talia, “Mining human mobility patterns from social geo-tagged data,” _Pervasive and Mobile Computing_ , vol. 33, pp. 91–107, 2016.
  * [36] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected networks on graphs,” in _International Conference on Learning Representations (ICLR)_ , 2014.
  * [37] T. N. Kipf and M. Welling, “Variational graph auto-encoders,” _NIPS Workshop on Bayesian Deep Learning_ , 2016.
  * [38] D. Bo, X. Wang, C. Shi, M. Zhu, E. Lu, and P. Cui, “Structural deep clustering network,” in _Proceedings of The Web Conference 2020_ , ser. WWW ’20. Association for Computing Machinery, 2020, p. 1400–1410.
  * [39] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _International Conference on Learning Representations (ICLR)_ , 2017.
  * [40] D. Chai, L. Wang, and Q. Yang, “Bike flow prediction with multi-graph convolutional networks,” in _Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems_ , ser. SIGSPATIAL ’18. Association for Computing Machinery, 2018, pp. 397–400.
  * [41] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” _arXiv preprint arXiv:1710.10903_ , 2017.
  * [42] Y. N. Dauphin, A. Fan, M. Auli, and D. Grangier, “Language modeling with gated convolutional networks,” ser. Proceedings of Machine Learning Research, vol. 70. PMLR, 2017, pp. 933–941.
  * [43] I. Sutskever, O. Vinyals, and Q. V. Le, “Sequence to sequence learning with neural networks,” in _Advances in Neural Information Processing Systems 27_. Curran Associates, Inc., 2014, pp. 3104–3112.
  * [44] Y. Li, R. Yu, C. Shahabi, and Y. Liu, “Diffusion convolutional recurrent neural network: Data-driven traffic forecasting,” in _International Conference on Learning Representations (ICLR)_ , 2018.
  * [45] R. Borndörfer, H. Hoppmann, and M. Karbstein, “Passenger routing for periodic timetable optimization,” _Public Transport_ , vol. 9, no. 1, pp. 115–135, 2017.
  * [46] W. Wu, P. Li, R. Liu, W. Jin, B. Yao, Y. Xie, and C. Ma, “Predicting peak load of bus routes with supply optimization and scaled shepard interpolation: A newsvendor model,” _Transportation Research Part E: Logistics and Transportation Review_ , vol. 142, p. 102041, 2020.
  * [47] J. Durán-Micco and P. Vansteenwegen, “A survey on the transit network design and frequency setting problem,” _Public Transport_ , pp. 1–36, 2021\.

|  Xiangjie Kong (M’13–SM’17) received the B.Sc. and Ph.D. degrees from
Zhejiang University, Hangzhou, China. He is currently a Full Professor with
College of Computer Science and Technology, Zhejiang University of Technology.
Previously, he was an Associate Professor with the School of Software, Dalian
University of Technology, China. He has published over 160 scientific papers
in international journals and conferences (with over 130 indexed by ISI SCIE).
His research interests include network science, mobile computing, and
computational social science.
---|---
|  Kailai Wang received the B.Sc. degree in software engineering from the
Dalian University of Technology, China, in 2019, where he is currently
pursuing the master’s degree with the School of Software. His research
interests include analysis of complex networks, network science, and urban
computing.
---|---
|  Mingliang Hou received the B.Sc. degree from Dezhou University and the
M.Sc. degree from Shandong University, Shandong, China. He is currently
pursuing the Ph.D. degree in software engineering with the Dalian University
of Technology, Dalian, China. His research interests include graph learning,
city science and social computing.
---|---
|  Xia Feng (M’07-SM’12) received the BSc and PhD degrees from Zhejiang
University, Hangzhou, China. He is currently an Associate Professor and
Discipline Leader in School of Engineering, IT and Physical Sciences,
Federation University Australia. Dr. Xia has published 2 books and over 300
scientific papers in international journals and conferences. His research
interests include data science, social computing, and systems engineering. He
is a Senior Member of IEEE and ACM.
---|---
|  Gour C. Karmakar (M’01) received a B.Sc. degree in Computer Science
Engineering from CSE, BUET in 1993 and Masters and Ph.D. degrees in
Information Technology from the Faculty of Information Technology, Monash
University, in 1999 and 2003, respectively. He is currently an Associate
Professor at Federation University Australia. He has published over 161 peer-
reviewed research publications including 39 international peer-reviewed
reputed journal papers and was awarded six best papers in reputed
international conferences. He received a prestigious ARC linkage grant in
2011. His research interest includes multimedia signal processing, traffic
signal management, big data analytics, Internet of Things and cybersecurity
including trustworthiness measure.
---|---
|  Jianxin Li received the Ph.D. degree in computer science from Swinburne
University of Technology, Australia, in 2009. He is an Associate Professor of
Data Science in the School of Information Technology, Deakin University. He
has published 90 high quality paper in top-tier venues, including The VLDB
Journal, IEEE TKDE, PVLDB and IEEE ICDE. He has received two competitive
grants from Australian Research Council. His research interests include graph
query processing, social network computing, and information network data
analytics.
---|---


# Repeat Voting:
Two-Vote May Lead More People To Vote††thanks: The idea of repeat voting
evolved following discussions at the Annual Conference of the Federmann Center
for the Study of Rationality in February 2017\. The author thanks the Center’s
members, in particular Maya Bar-Hillel, Orit Kedar, and Motty Perry, for their
suggestions.

Sergiu Hart The Hebrew University of Jerusalem (Federmann Center for the Study
of Rationality, Department of Economics, and Institute of Mathematics). _E-
mail_<EMAIL_ADDRESS>_Web site_ : http://www.ma.huji.ac.il/hart

(October 17, 2017)

###### Abstract

A _repeat voting_ procedure is proposed, whereby voting is carried out in two
identical rounds. Every voter can vote in each round, the results of the first
round are made public before the second round, and the final result is
determined by adding up all the votes in both rounds. It is argued that this
simple modification of election procedures may well increase voter
participation and result in more accurate and representative outcomes.

Suppose that it is two weeks after the Brexit vote, and there is a new vote on
the same issue—what will the result be? Given the way the original vote went,
will people change their minds and vote differently? Will the original results
cause people who had not voted to cast their vote in this second round? Will
the final result be different?111Before the Brexit vote, a petition that
called for a second vote in case of low participation and a narrow winning
margin was launched; it got 22 signatures before the vote, and more than 2
million signatures in the two days after the result was announced.
(Interestingly, the initiator was a “leave” supporter who believed that
“leave” would lose.) See, e.g., http://www.bbc.com/news/uk-politics-eu-
referendum-36629324 (There are no clear answers to any of these questions, but
one can easily provide arguments either way.) Now carry out a similar thought
experiment regarding the latest presidential election in the U.S., or whatever
your latest favorite, or unsettling, election is …

Democratic elections are beset by many problems. One issue is low voter
turnout, which at times is only one-half of the eligible voters or even less.
Another issue is excessive reliance on polls: polls affect voters, despite
repeatedly turning out to being quite far from accurate. This also relates to
the low-turnout issue: “I will not waste my time voting, as my candidate is in
any case sure to win” (or “… sure to lose”). Polls may also lead people not to
cast their vote for their preferred candidate, if, for example, they do not
want him or her to win by too large a majority, or if they want to voice a
certain “protest” through their vote—only to find out that in the end their
candidate did not win at all. Yet another issue concerns unexpected events
that occur extremely close to election time, too late to be able to be
addressed by the candidates, such as a terrorist attack, the publication of
false information, bad weather, and so on. What is common to many of these
situations is that people might want to change their vote, or their non-
participation in the election, once they see the actual results and how these
came about.

To address these and other issues, I propose the use of the following REPEAT
VOTING procedure.

  1. A.

Voting is carried out in two rounds.

  2. B.

Every eligible voter is entitled (and encouraged) to vote in each of the two
rounds.

  3. C.

All the votes of the two rounds are added up, and the final election result is
obtained by applying the current election rules222Be they plurality, special
majority, electoral college, and so on. to these two-round totals.

  4. D.

The results of the first round are officially counted and published; the
second round takes place, say, two weeks after the first round, but no less
than one week after the official publication of the first round’s results.

What are the _advantages_ of repeat voting?

  1. 1.

_Polls._ The first round becomes a de facto giant opinion poll; however,
because the votes of the first round count, it is a much more truthful poll
(in contrast to the usual pre-election polls, where giving untruthful
answers—whether intentionally or not—carries no cost333Someone once quipped
that Israelis tell the truth in polls, but lie when they cast their vote.).
The combination of the large sample size and incentivized truthfulness makes
the results of the first round a significantly more accurate predictor of the
electorate views. It is thus crucial for the votes of the first round to count
no less than the votes of the second round, which explains why we are adding
up the votes of the two rounds, rather than having only the second round
determine the outcome.

  2. 2.

_Participation._ Voters who do have a preference that is not however strong
enough to make them vote in the first round may well be led to vote in the
second round because of the results of the first round. Thus, participation in
at least one round of the election is expected to increase. It is better that
people vote even in one round than not at all.444Voters who have strong or
extreme positions will most probably vote in both rounds; their relative
weight in the final result will decrease when enough people are motivated to
vote in the second round (which may well happen if such extreme positions get
higher shares of the vote in the first round). One indirect advantage is that
people who vote may feel closer to the elected officials, and to the
democratic system in general.

  3. 3.

_Representative results._ The final results may be more representative,
because the second round makes it possible for the voters as well as for the
candidates to “correct” any problems of the first round. This includes the
effects of wrong predictions by the polls, as well as any special
circumstances and events that occurred close to election time (see the second
paragraph of the paper; it is unlikely that such unexpected events will happen
both times). All this, again, can only increase the robustness of the results:
they become more trustworthy and more accepted.

  4. 4.

_New reference point._ The results of the first round become a new reference
point, which may well affect a person’s choice in the second round:
_imagining_ a new situation and _being_ in a new situation are not the same
thing.555Robert J. Aumann, awarded the Nobel Prize in Economics in 2005, tells
the following story (S. Hart, “An Interview with Robert Aumann,”
_Macroeconomic Dynamics_ 9, 2005, page 711; reprinted in: Paul A. Samuelson
and William A. Barnett, editors, _Inside the Economist’s Mind: Conversations
with Eminent Economists_ , Blackwell Publishing 2006). In 1956 he had two
offers: one from Bell Labs in New York, and another from the Hebrew University
of Jerusalem. It took him a long time to make up his mind, and he chose Bell
Labs. He phoned them and told them that he accepted their offer. Once he put
down the phone, he immediately started imagining the next few years at Bell
Labs, and reached the conclusion that he had made the wrong choice. A day
later he phoned Bell Labs and asked them if he could change his mind—which
they graciously agreed to. How come a leading game theorist couldn’t
understand all this before he made his initial decision? Aumann’s answer is
that until he found himself in the new situation of someone going to Bell
Labs, he could not really grasp what it meant!

  5. 5.

_Strategic voting._ People seem to be more strategic in their voting than is
usually believed (again, see the examples in the second paragraph above), but
under current procedures they base their strategic decisions on possibly
inaccurate polls. Repeat voting provides a much more solid basis. In close
elections it is conceivable that the voting of the second round may be less
strategic (and the other way around when there is a large winning margin in
the first round).666An interesting related instance concerns the minimal
threshold for a party to be represented in a parliament. Many potential
entrants try to convince voters that they have support that is higher than the
threshold and so voting for them would not be a “waste” of one’s vote. In many
cases, however, it turns out that these parties do not pass the threshold;
once this is seen in the first round, there will be many fewer such wasted
votes in the second round.

What are the possible _disadvantages_ of repeat voting?

  1. 1.

_Costs._ A second round adds costs (however, in future voting that may be
conducted online, these costs would become much smaller). The additional
electoral campaign between the two rounds also increases the costs (but one
should remember that two rounds are already used in various elections, albeit
not two identical rounds as proposed here). One way to save costs is to carry
out the second round only when the results of the first round are close (for
instance, when the winning margin is below a certain threshold that is
specified in advance).777Suggested by Motty Perry and Steve Brams.

  2. 2.

_Participation._ There may be fewer voters in the first round (“I will have a
chance to vote in the second round”).

  3. 3.

_Bandwagon effect._ Voters with strong or extreme positions, who are much more
likely to vote in the first round, may have a big effect on the results of the
first round, which may then have a bandwagon effect on the whole election.

One can think of other ways to overcome the issues pointed out above. For
example, one can repeat the vote three times, with the winner having to win at
least two rounds (this applies only to two-outcome elections, however, not to
multi-candidate and parliamentary elections, and is inherently more
complicated).888This procedure was also suggested by Shachar Kariv. Another
possibility is to make voting mandatory (as in certain countries); while this
may resolve the participation issue, it does not resolve the significant
“polls issue” discussed in advantage #1 above. Yet another is to have the
votes in the two rounds of repeat voting weighted differently (for instance,
depending on the total number of votes in each round999For example, averaging
the percentages of votes that each candidate received in the two rounds (which
amounts to giving weights to the two rounds that are inversely proportional to
the total number of votes in each) may perhaps increase participation in that
round where there are fewer voters (probably the first round).); at this
point, however, it seems best to leave it as simple and straightforward as
possible.

In summary: REPEAT VOTING is a simple modification of election procedures that
is capable of increasing voter participation and yielding more accurate and
representative results. Everyone deserves a second chance, as the saying goes.
Shouldn’t this include voters and candidates?