# Characterizing Regional Importance in Cities with Human Mobility Motifs in
Metro Networks

Shuyang Shi111Email<EMAIL_ADDRESS>Ding Lyu, Lin Wang, Xiaofan Wang, and
Guanrong Chen

###### Abstract

Uncovering higher-order spatiotemporal dependencies within human mobility
networks offers valuable insights into the analysis of urban structures. In
most existing studies, human mobility networks are typically constructed by
aggregating all trips without distinguishing who takes which specific trip.
Instead, we claim individual mobility motifs, higher-order structures
generated by daily trips of people, as fundamental units of human mobility
networks. In this paper, we propose two network construction frameworks at the
level of mobility motifs in characterizing regional importance in cities.
Firstly, we enhance the structural dependencies within mobility motifs and
proceed to construct mobility networks based on the enhanced mobility motifs.
Secondly, taking inspiration from PageRank, we speculate that people would
allocate values of importance to destinations according to their trip
intentions. A motif-wise network construction framework is proposed based on
the established mechanism. Leveraging large-scale metro data across cities, we
construct three types of human mobility networks and characterize the regional
importance by node importance indicators. Our comparison results suggest that
the motif-based mobility network outperforms the classic mobility network,
thus highlighting the efficacy of the introduced human mobility motifs.
Finally, we demonstrate that the performance in characterizing the regional
importance is significantly improved by our motif-wise framework.

Keywords: Human mobility motif, human mobility network, regional importance,
higher-order structure, city structure

##  1 Introduction

A city encompasses regions with diverse economic development orientation, and
the fluxes of people between regions further reflect the complexity of the
city. It holds great significance to scientifically understand the complexity
of cities by studying the microscopic individual movement and the macroscopic
flow of people, as well as their interactions with various urban regions. A
deeper comprehension of human mobility within cities is a critical step in
developing well-founded urban management strategies and transportation
planning. Network science provides a method for abstracting the complex
connections within a city in the form of networks[1, 2, 3, 4, 5, 6]. The
regional importance, as reflected in human mobility network, serves as a vital
tool for the study of city structure, which enables us to deeply understand
the city structure[7, 8], explore development and transformation process of
city[9], capture the city’s circadian rhythm and assess the urban jobs-housing
balance[10].

With the rapid development and proliferation of information technology, an
increasing amount of social signal data related to human mobility is being
collected, which paves the way for computing and studying the characteristics
of both human mobility behavior and city structures[11, 12, 13, 14]. In the
scenario of smart cities, research on human mobility data, such as smart
transportation card data, vehicle GPS data, and phone call logs, have been
garnering more and more attention. Metro networks serve as indispensable
infrastructure for daily lives, work, and communications of urban residents.
It indicates that the regional importance around metro stations can be
characterized through the recognition and analysis of the diverse mobility
patterns of passengers in metro networks.

Previous studies typically define a human mobility network in metro systems as
a directed weighted network, where nodes are metro stations and the weight of
an edge denotes the magnitude of passenger flow between stations. In this
conventional approach, the human mobility network is constructed by
aggregating all trips without distinguishing who takes which path. For
example, the aggregation by $A\rightarrow B$ of person 1 and $B\rightarrow C$
of person 2 is not distinguished from another by $A\rightarrow B\rightarrow C$
of one person. It has been pointed out that this kind of memoryless first-
order Markov approach fails to capture the complete structure and dynamics of
networks[15, 16], motivating the present exploration of higher-order
dependencies in human mobility networks.

Existed studies on the higher-order organization of complex networks usually
pre-define a variety of network motifs to explain structural mechanisms. This
approach focuses on extracting or counting network motifs from a large-scale
network to capture higher-order structural dependencies. However, in real
networks, higher-order organizational features may not be solely governed by a
single motif but rather emerge from the collective influence of multiple
higher-order structures. In the context of human mobility networks, pre-
defined network motifs may not comprehensively capture all mobility patterns.
In [17], the human mobility motif is defined as a sequence of visited places
and the trips among them, which can characterize various mobility patterns of
passengers for the exploration of complex human behaviors. In this setting, an
individual mobility motif can be presented as a mesoscopic network, in which
nodes are the visited places and edges are the trips between visited places of
a person in one day.

In recent years, a large number of achievements have been made in each of
these areas individually. Relatively speaking, the exploration of the
interrelationship of these fields remains a challenging topic. It is
foreseeable that the complete trajectory of an individual’s trip in a day can
reflect more structure information of the human mobility network in the city
compared to multiple independent single trips. Building upon the above
inspirations, our study of human mobility networks shifts from the aggregation
of individuals’ single trips to the aggregation of mobility motifs. Similarly
to the approach in [18], every single trip is considered as a first-order
relation. A mobility motif consisting of all trips of a person between several
stations in one day reflects higher-order network structures. Here, mobility
motifs, also known as higher-order structures, are regarded as the fundamental
units of a human mobility network. In this paper, we propose two novel network
construction frameworks at the level of mobility motifs, and compare their
effectiveness with the classic network construction method in characterizing
regional importance through node importance indicators.

Firstly, we identify a variety of mobility motifs of people and then aggregate
them to construct human mobility networks. To enhance the higher-order
structural dependency, we reorganize mobility motifs with a strategy similar
to those in [19, 18, 20]. Then, we additively aggregate all reorganized
mobility motifs to form a human mobility network, which is referred to as the
motif-based mobility network. Secondly, we propose a new weight allocation
method based on individual mobility motifs and trip intentions. With the
inspiration of PageRank, we reorganize mobility motifs by directly connecting
the initial station and all destinations at different times and construct
motif-wise network by aggregating these reorganized motifs.

Specifically, the main contributions of this work are summarized as follows.

  * •

This work presents the first formulation and application of human mobility
motifs to explore human mobility networks within cities and evaluate regional
importance. We claim individual mobility motifs are the fundamental units of
human mobility networks. It is a significant ideological transformation for
the aggregation from first-order individuals’ single trips to the higher-order
mobility motifs in a human mobility network.

  * •

We enhance the indirect effects to propose a motif-based aggregation framework
for modeling human mobility networks. Instead of enumerating network motifs or
subgraphs, this higher-order network construction framework uses mobility
motifs as the fundamental units. The motif-based mobility network demonstrates
superior performance when compared to the classic mobility network.

  * •

We emphasize trip intentions by allocating station importance to destinations
at different time periods in one day. Following the idea of PageRank, we
propose a novel motif-wise framework, which can significantly improve the
characterization of regional importance, as well as the model performance and
explanation.

  * •

We utilize transportation card data from three big cities in China to assess
and compare the capabilities of the motif-based mobility network, motif-wise
network, and classic mobility network in characterizing regional importance.
House prices are used to evaluate the effectiveness of station rankings
produced by our framework. Comparatively, we show that our motif-wise
framework obtains the best performance.

##  2 Related work

###  2.1 Higher-order organization of complex networks

“Network motif” was first defined by [21] to characterize structural patterns
of interconnections occurring in complex networks. Hidden mechanisms of
higher-order structural dependencies in complex networks can be understood and
explained by specific network motifs. In [19], a variety of network motifs and
the corresponding motif adjacency matrices are defined. A generic framework
based on a selected motif adjacency matrix is developed to extract clusters
organized with dense structural motifs. This motif-based framework has been
extended and continuously improved to explore higher-order clustering
structure[22, 23], community structure[24, 25], core-periphery structure[26].
These findings help enhance the understanding of complex structural patterns
and significantly broadens the application of complex network analysis[27,
28].

Some classic work introduces node centrality indicators to assess the node
importance by incorporating network motifs. In [18] and [20], induced networks
from motif adjacency matrices are proposed and the PageRank or betweenness
centrality is calculated for node importance ranking, with the proposed
methods applied to construct motif-based cooperation networks for ranking
scientists. Taking real h-indexes of scientists as the criterion, these models
can improve the performance of ranking under specific motifs. However, little
is known about how to select suitable motifs in different types of networks.
Existing studies need to enumerate plenty of network motifs or simple
subgraphs in order to obtain better higher-order expression. In addition, the
higher-order connections of real-world networks may include multiple higher-
order structures, rather than just one.

###  2.2 Human mobility motifs

Human mobility motifs were first proposed in [17] to characterize diverse
mobility patterns of people, which facilitated the exploration of human
behaviors. The focus is on various mobility patterns hidden in the daily trips
of people, revealing that most daily trips can be described by a few common
mobility motifs. The daily mobility motifs are classified with four rules and
a perturbation-based model is built to reproduce the generating of individual
mobility motifs. Considering both location-based and activity-based motifs, in
[29], the scaling properties of travel distance are investigated, revealing
the relationship between the scaling parameters and the node number of motifs.
The findings indicate that people prefer a mobility motif with the lowest
consumption that satisfies their demand, which is summarized as the least
effort principle. In [30, 31], well-labeled human mobility motif data are used
to present the differences between people in different working and living
conditions in terms of the dimensions of motif complexity, travel time, travel
purpose, etc. In [32, 33], the major motif of each region in a city is
analyzed, clarifying the relationship between the functions of these regions
and the corresponding major motifs. A motif-preserving individual travel
preference learning method is presented in [34], and the accuracy and
robustness of mobility prediction model is improved. Some classic research
conclusions on individual movement patterns have also been extended at the
level of location activity motifs, such as classical exploration and
preferential return model[35]. Current research on human mobility motifs is
devoted to exploring the variety of individual mobility patterns, but co-
analyses with the global mobility network are rare.

###  2.3 Human mobility patterns in metro networks and city structures

Motivations for studying human mobility patterns in metro networks can be
mainly divided into two categories: understanding human behaviors and
analyzing network properties. Recognition and analysis of human mobility
patterns provide a deep insight into complex human behaviors. Metro is a
fundamental infrastructure associated with city structures, helping explore
the latter specifically and precisely.

Several studies focus on passenger flow prediction and anomaly detection in
metro systems. In [36], three machine learning methods are developed to detect
anomalous passenger flows in metro networks. In [37], an algorithm is proposed
for predicting short-term irregular passenger flows during some special
events, such as concerts or football matches. Taking both regional features
and trip intentions into account, a human mobility prediction model is
developed in [38] with higher accuracy. When the function of a region changes,
the model can predict fluxes in the new scene in accordance with the change.
In [39], the effects of two travel strategies are compared, respectively with
the shortest path and minimum cost on the congestion in a metro network, where
an intervention model is built, which shows that the congestion would obtain
great mitigation as long as a small number of people switch travel strategies
from the shortest path to the minimum cost.

Complex networks provide a powerful tool for analyzing city structures
obtained from mobility data in metro networks. Network indicators and
community structures have been widely used to describe the characteristics of
human mobility and city structures[40, 41]. In [9], the smart card data of
Singapore in three years, from 2010 to 2012, are used to introduce structural
indicators that can evaluate node centrality or detect communities for
capturing changes in city structures. It was found that the distributions of
the node centrality are becoming more and more flat, indicating that the urban
development is becoming more and more balanced. In [3], a linear combination
of node centrality, clustering coefficient, and closeness centrality is
embedded into a basic PageRank framework for ranking the station importance.
In [10], directed weighted human mobility networks are built based on the
three motif patterns identified through non-negative tensor decomposition.
These networks, each constituted by one of the three motif patterns, exhibit
distinct characteristics, shedding light on how different city regions serve
diverse populations.

##  3 Data description and processing

We employ public transportation smart card data from Shanghai, Beijing, and
Hangzhou metro in this study. Shanghai and Beijing are the largest cities with
highly developed metro networks in China. The magnitude of daily metro
passenger flows in Beijing and Shanghai was about 5 million during the studied
period. To improve the robustness of our findings in this study, we also use
Hangzhou metro data on a smaller network scale to verify possible variations.
Topological structures of the metro networks in these three cities are
visualized in Fig. 1, and the basic information of Metro data is listed in
Table 1. Previous studies have pointed out that people’s travel patterns may
different on weekdays from weekends[42, 35]. Therefore, we separate the raw
data of Shanghai and Hangzhou by weekdays and weekends for study.

Figure 1: Topological structures and surrounding house prices of (a) Shanghai,
(b) Beijing, and (c) Hangzhou Metro networks. Each node represents a metro
station. The node color reflects the weighted average house price around a
metro station, and the color bar shows the corresponding price in RMB. Newly
built stations that haven’t been color-filled are beyond the scope of this
study. Few areas around metro stations (such as airports and industrial parks)
do not have residential transaction records, which will be considered in the
calculations of node importance but excluded in final ranking comparisons.

Study City | Stations | Lines | Study Date | Motifs
---|---|---|---|---
Shanghai (weekdays) | 289 | 14 | 5-9 Sep 2016 | 11374267
Shanghai (weekends) | 289 | 14 | 3,4,10,11,24,25 Sep 2016 | 13547178
Beijing | 311 | 22 | 1 Mar 2018 | 2943270
Hangzhou (weekdays) | 79 | 3 | 7-11,14-18 Jan 2019 | 6412542
Hangzhou (weekends) | 79 | 3 | 5,6,12,13,19,20 Jan 2019 | 3349697

Table 1: Summary of metro data.

In this work, we aim to characterize regional importance in cities by
analyzing passengers’ mobility patterns in the metro networks. We speculate
that regional importance can be characterized by the importance of metro
stations in the consideration of human mobility. We expect to build human
mobility networks in metro systems to predict the importance of surrounding
areas of metro stations. As the saying goes, “There are three factors that
determine the house price: location, location, and location.” In first-tier
cities in China, house prices are a concentrated manifestation of the level of
importance of regions. The stronger the importance of a place, the more
attractive it is for people to live in, thereby driving up house prices.
Therefore, house price is used in the evaluation of our frameworks. We crawl
second-hand house prices around the metro stations during the studied years
from a large real estate agency website222https://fang.com/. The weighted
average prices of houses around each metro station (total transaction price
divided by total transaction area) are considered as the criterion to evaluate
regional importance, which is shown in Fig. 1. As commonly experienced, house
prices are indeed higher in the downtown area and lower in the suburbs. It is
also consistent with our intuitive cognition of regional importance in these
cities.

Figure 2: Illustration of three strategies of human mobility network
construction. Consider a metro system with 5 stations (A-E) and 3 passengers
(1-3). (a) Table list of nine Origin-Destination (OD) pairs extracted from raw
transportation card data of three passengers in one day. Records with the same
card ID have been sorted by time. Different colors are used to distinguish
passengers and their trips. (b) Visualization of three mobility motifs
generated by OD pairs. To clarify the direction of mobility motifs, the
initial station of travel paths is marked in red. (c) Topological structures
and corresponding adjacency matrices of human mobility networks with three
different constructing strategies from mobility motifs: ($\alpha$) classic
mobility network, ($\beta$) motif-based mobility network, and ($\gamma$)
motif-wise mobility network. The edge color represents the passenger who
contributes to the edge. Figure 3: Distributions of the 15 most common daily
human mobility motifs in Shanghai, Beijing, and Hangzhou. The statistics of
mobility motifs on weekdays and weekends are separated.

A human mobility motif is defined as an induced network from a passenger’s
daily trips in metro networks, in which nodes are the visited stations and
edges are the trips between visited stations. From the raw transportation card
data, we extract the daily OD pairs of each card. With the general assumption
that each passenger is endowed with a unique Card ID, the trips of individuals
are recorded as a set of temporal OD pairs. Taking stations as nodes and the
trips between stations as directed edges, we obtain a variety of daily
mobility motifs of individuals. Fig. 2(a, b) illustrates the motifs generation
process. Passenger 1 (with Card 1) first takes the metro from station $A$ to
station $B$, and his mobility motif accordingly has a directed edge from $A$
to $B$. After that, this passenger returns to $A$ from $B$, so an edge from
$B$ to $A$ is added to his mobility motif. The generation of two other
mobility motifs is also shown in detail in Fig. 2(a, b). The distributions of
the 15 most common daily human mobility motifs in Shanghai, Beijing, and
Hangzhou (in the descending order of the distributions according to Shanghai
weekdays data) are presented in Fig. 3. Moreover, the total number of all
mobility motifs in the studied cities is counted in Table 1.

##  4 Methodology

###  4.1 Classic mobility networks

Classic human mobility networks in the metro are generally defined as a
directed weighted network $G=(V,W)$, where $V$ denotes the set of metro
stations and $W=\\{W_{ij}|i,j\in V,i\neq j\\}$ denotes the set of the
magnitudes of passenger flows between stations. As such, the network is the
additive aggregation of all first-order trips. Meanwhile, human mobility
networks can also be regarded as the aggregation of daily mobility motifs of
all individuals.

Definition 1 Let $M$ be a human mobility motif. The classic mobility network
$G=(V,W)$ is defined as the additive aggregation of all such $M$s.

Although the networks constructed by Definition 1 and the general definition
are the same, these two aggregation guidelines are hugely different. We no
longer take the first-order trips (single OD pairs) as the fundamental units
of a mobility network but take the higher-order mobility motifs as the
fundamental units of a mobility network instead. We emphasize the idea of the
higher-order organization of human mobility networks on the condition of
mobility motifs as fundamental units, as visualized in Fig. 2(c-$\alpha$). We
aggregate three mobility motifs from Fig. 2(b) other than directly aggregating
single OD pairs from Fig. 2(a) to construct the human mobility network.

###  4.2 Motif-based mobility networks

Previous studies on the higher-order organization of complex networks with
network motifs introduced motif-based adjacency matrices[19, 18, 20].
According to the definition, each element of a motif-based adjacency matrix
equals the number of a specific motif that two nodes share. Formally, the
motif-based network is defined as $\mathcal{G}=(V,\mathcal{W})$, where
$\mathcal{W}_{ij}$ is the number of a specific motif containing both node $i$
and node $j$. From the meso perspective, each network motif is reorganized as
a complete graph in which each pairwise node is connected by the motif. Thus,
the motif-based mobility network is an additive aggregation of all complete
graphs induced from network motifs.

Inspired by these studies, we adopt the same reorganization strategy on human
mobility motifs. We generate mobility motifs from OD pair records of each
passenger and reorganize them as fully connected graphs of the same nodes for
the aggregation of a human mobility network.

Definition 2 Let $M$ be a human mobility motif, and $\mathcal{M}$ be the
induced undirected complete graph of $M$. The motif-based mobility network
$\mathcal{G}=(V,\mathcal{W})$ is defined as the additive aggregation of all
such $\mathcal{M}$s.

Fig. 2(c-$\beta$) shows the construction of $\mathcal{G}$ by aggregating all
reorganized motifs $\mathcal{M}$ in Fig. 2(b). Compared with the classic
mobility network, some new connections in the motif-based mobility network are
established to enhance the latent effects between nodes. For example, there is
a potential relevance between station $A$ and station $C$ in the mobility
motif $M$ of person 2, so we bridge node $A$ and node $C$ with a directly
connected edge when reorganizing the motif. Therefore, there is an edge
between node $A$ and node $C$ in Fig. 2(c-$\beta$) but not in Fig.
2(c-$\alpha$). This new connection produced by $\mathcal{M}$ of person 2
enhances the inside higher-order structural dependencies due to the transform
from indirect relevance to direct relevance. As a supplement, the motif-based
mobility network is an undirected weighted network, with an adjacency matrix
shown in Fig. 2(c-$\beta$).

We will see later that the motif-based mobility networks have slightly better
performance in characterizing regional importance than the classic mobility
network. However, the accuracy of characterization still has room for
improvement. With the inspiration of resource allocation, we further propose a
novel aggregation framework to address the defects in the motif-based
framework.

###  4.3 Motif-wise human mobility networks

According to the main idea of PageRank, each node is endued with an initial
stochastic value of importance and then iteratively allocates the value into
its out-neighbors until convergent. When considering mobility motifs of
individuals, the value of nodes would be transferred along directed edges.
However, some cases are out of our expectations. As an example, the
significance of reorganization on a four-node mobility motif is visualized in
Fig. 4(a). The person has a trip path $A\rightarrow B\rightarrow C\rightarrow
D$, thus the mobility motif has four nodes and three directed edges. In such a
case, the value of node $B$ will be taken out and allocated to node $C$ in the
mobility motif, and the value of node $C$ is then allocated to node $D$.
However, nodes $B$, $C$, and $D$ are all his destinations during different
time periods, not just roles of transits. We expect that nodes $B$ and $C$
have similar importance with respect to node $D$. The contradiction to our
expectations and the limitations of structural properties motivate us to
ponder if there is a reasonable reorganization strategy on mobility motifs to
address this problem. In this section, we propose a motif-wise framework to
reorganize diverse mobility motifs of individuals and aggregate them to
construct a human mobility network.

Figure 4: The reorganization strategy from human mobility motifs $M$ to
$\mathbb{M}$.

Inspired by the idea of PageRank, we adopt a new strategy to reorganize
directed edges and redefine the edge weight. We speculate that a passenger
would take his resources from his initial station to his travel destinations,
instead of taking the resources from one destination to another. Consequently,
assume that a passenger travels from the initial station with a value of
resource (essentially the same as node importance). Once arriving at another
location by metro, a corresponding value of resources is accordingly allocated
to the destination station from the initial station.

Definition 3 Let $V_{M}$ be the node set of a human mobility motif $M$, $s(i)$
be the weighted in-degree of node $i\in V_{M}$, and $A\in V_{M}$ be the
initial node of $M$ . The reorganized motif of $M$ is defined as an induced
graph $\mathbb{M}=(V_{M},\mathbb{W})$, where $\mathbb{W}_{Ai}=s(i),i\in
V_{M}\backslash A$.

As illustrated by Fig. 4(a), a passenger starts his trip from station $A$, and
travels to $B$, $C$ and $D$ each once sequentially. Thus, the passenger
allocates resources to these stations equally with the weight of 1. In Fig.
4(b), another passenger also travels to $B$, $C$ and $D$ from initial station
$A$. While this passenger travels to $B$ and $C$ twice, so the directed edge
weights $w_{AB}=w_{AC}=2$. Meanwhile, we also try another similar weight
allocation method. The total resource of each person is restricted to be 1,
equivalent to the sum of edge weights in a reorganized motif is 1. Each person
allocates the value of resources to each place in proportion to the visiting
frequency except the initial place. This normalizes the $\mathbb{W}_{Ai}$ in
Definition 3 as $\mathbb{W}_{Ai}=s(i)/\sum_{j\in V_{M}\backslash A}s(j)$. For
example, with this strategy, in Fig. 4(a), $w_{AB}=w_{AC}=w_{AD}=1/3$; and in
Fig. 4(b), $w_{AB}=w_{AC}=2/5$, $w_{AD}=1/5$. We attach a mark to the former
strategy with $w=1$ and the latter with $w=1/n$.

Definition 4. The motif-wise network $\mathbb{G}=(V,\mathbb{W})$ is defined as
the additive aggregation of all such $\mathbb{M}s$.

Fig. 2(c-$\gamma$) shows the construction process of the motif-wise mobility
network based on the proposed framework with $w=1$. Passenger 1 only goes to
station $B$ after starting from the initial station $A$, so he produces an
edge with a weight of 1 from $A$ to $B$. Passenger 2 goes to station $B$ and
$C$ once each after starting from the initial station $A$, so he produces an
edge from $A$ to $B$ and an edge from $A$ to $C$ with weight of 1,
respectively. Passenger 3 goes to $C$ twice, so the weight of the edge from
initial station $B$ to $C$ is 2. He goes to $D$ and $E$ only once, so he
produces an edge from $B$ to $D$ and an edge from $B$ to $E$ with weight of 1,
respectively. We then aggregate all the reorganized motifs as a human mobility
network and finally run node importance indicator calculation. Distinguished
from the full connection of motif-based mobility networks, we enhance the
directionality of mobility motifs.

###  4.4 Measures of node importance

In the proposed framework, one important task is to characterize the regional
importance by ranking nodes in human mobility networks. Node importance can be
calculated from four commonly used measures including PageRank value,
eigenvector centrality, current flow closeness centrality, and clustering
coefficient, which are respectively defined as follows.

PageRank The main idea of the weighted network PageRank is that each node
assigns its PageRank value to the nodes it points to according to the edge
weights. First, $\sum_{i=1}^{|V|}PR_{i}(0)=1$. Then, the PageRank values are
calculated iteratively:

$PR_{i}(k)=s\sum_{j=1}^{|V|}\hat{w_{ji}}PR_{j}(k-1)+(1-s)\frac{1}{|V|},$

where $\hat{w_{ji}}=w_{ji}/\sum_{k\in V}w_{jk}$, $|V|$ is the number of nodes
and $s$ is a dampening factor, usually set as 0.85[43, 3].

Eigenvector centrality The main idea of eigenvector centrality is that the
importance of a node depends not only on the number of the neighboring nodes,
but also on their importance. Let $x$ be the eigenvector of the largest
eigenvalue of the adjacency matrix $A$. Then, the eigenvector centrality of
node $i$ is the $i$-th element of $x$.

Current flow closeness centrality Current-flow closeness centrality, also
referred to as information centrality, calculates closeness centrality based
on effective resistance between nodes in a network. When $G$ is regarded as an
electrical network, the weight of each edge is equivalent to the conductance.
The current flow closeness centrality of node $i$ is defined by

$c_{i}=\frac{|V|-1}{\sum_{i\neq j}{p_{st}(i)-p_{st}(j)}},$

where $p_{st}(i)-p_{st}(j)$ corresponds to the effective resistance.

Clustering coefficient All regions of cities develop in coordination. Due to
the existence of scale effects[44, 45] and network effects[46], the contact
strength between neighboring regions of a region may also affect the
development and importance of the region itself. Here, the clustering
coefficient is used to capture the degree to which regions in a city tend to
cluster together and treated as a node importance index. The clustering
coefficient of node $i$ in a weighted network is defined as

$c_{i}=\frac{1}{k(i)(k(i)-1)max(w)}\sum_{jk}(w_{ij}w_{ik}w_{jk})^{1/3},$

where $k(i)$ is the degree of node $i$.

The larger the calculated values of these indicators, the higher the
importance of the node.

##  5 Results

In this section, through real data analysis, we explain the improvement
obtained by our frameworks and discuss some intriguing phenomena observed.

###  5.1 Motif-base human mobility networks

In this subsection, we calculate and rank the node importance in the two kinds
of human mobility networks that we constructed above ($G$ and $\mathcal{G}$).
For equivalent comparison with the undirected motif-based mobility network
$\mathcal{G}$, we also convert $G$ to an undirected network $G^{\prime}$. The
edge weight of $G^{\prime}$ is adjusted by
$W^{\prime}_{ij}=W^{\prime}_{ji}=W_{ij}+W_{ji}$. As will be discussed later in
Section 5.3, since $W_{ij}\approx W_{ji}$, the effect of the adjustment on the
network structure is extremely small. The case of the directed network $G$
will be discussed in the next subsection.

Now we compare the station rankings calculated by the node importance measures
with the weighted average house price around metro stations to evaluate the
effectiveness of the ranking results. Following [18, 20], Normalized
Discounted Cumulative Gain ($NDCG$) is used to evaluate the effectiveness of
the ranking results, which is defined as

$NDCG_{k}=\frac{DCG_{k}}{IDCG_{k}},$

where $DCG_{k}=\sum_{i=1}^{k}\frac{rel_{i}}{\log_{2}(i+1)}$ is the discounted
cumulative gain of the top $k$ stations obtained by a node importance
indicator; house price is regarded as the relevance score $rel_{i}$ in our
context; $IDCG_{k}$ is the $DCG$ of actual top $k$ stations with the highest
house prices. This indicator ranges from 0 to 1. The larger the $NDCG$ is, the
better the ranking performance is. We also introduce the Pearson correlation
coefficient $r$ to depict the correlations.

Figure 5: Correlation between Shanghai house price and calculated station
rankings in $G$ and $\mathcal{G}$. Different rows show the ranking results by
PageRank, eigenvector centrality, current flow closeness centrality, and
clustering coefficient, respectively. The left two columns respectively depict
the correlations of the weighted average house price against a measure of the
rankings of metro stations in $G^{\prime}$ and $\mathcal{G}$; 95% confidence
intervals are displayed. The Pearson correlation coefficient is shown in each
subgraph. The right column compares $NDCG_{k}$ of $G^{\prime}$ and
$\mathcal{G}$. In order to present a clearer comparison, the inset window
shows $NDCG_{k}$ of $\mathcal{G}$ minus $NDCG_{k}$ of $G^{\prime}$. The orange
dotted line is the datum line with $y=0$.

We present a comparison of the data from Shanghai (weekdays) in Fig. 5 as an
example and also list data from other cities to verify the robustness of the
results in Table 2. We take the ranking of node importance as the x-axis and
house price as the y-axis in the first two columns in Fig. 5. The trends of
the negative correlations show that higher-ranking places have higher house
prices, which is consistent with life experience. From the metrics of four
node importance indicators, rankings of stations in $\mathcal{G}$ exhibit a
slightly stronger linear correlation with house prices, as indicated by
Pearson correlation coefficient $r$. Comparisons between the calculated
$NDCG_{k}$ of $G^{\prime}$ and $\mathcal{G}$ are shown in the right panel of
Fig. 5. To make it clearer, we make a difference calculation between
$NDCG_{k}$ of $G^{\prime}$ and $NDCG_{k}$ of $\mathcal{G}$ in the inset.
$NDCG_{k}$ of $\mathcal{G}$ are larger than those of $G^{\prime}$ with respect
to most $k$s, indicating that motif-based mobility networks can help better
characterize the regional importance. Furthermore, Table 2 shows the
comprehensive results of the five studied objects according to the four
metrics of node importance calculation. We highlight better results in bold.
It can be seen that in all cities, the performance of motif-based mobility
networks is generally better than that of classic mobility networks.

|  |  | Shanghai
---
(weekdays)
| Shanghai
---
(weekends)
Beijing |  | Hangzhou
---
(weekdays)
| Hangzhou
---
(weekends)
Measures | Indicators | $G^{\prime}$ | $\mathcal{G}$ | $G^{\prime}$ | $\mathcal{G}$ | $G^{\prime}$ | $\mathcal{G}$ | $G^{\prime}$ | $\mathcal{G}$ | $G^{\prime}$ | $\mathcal{G}$
PageRank | $r$ | -0.46665 | -0.47895 | -0.39862 | -0.41291 | -0.30185 | -0.32199 | -0.37409 | -0.37876 | -0.28968 | -0.30941
$NDCG_{5}$ | 0.80752 | 0.80636 | 0.76455 | 0.73755 | 0.53385 | 0.54724 | 0.70932 | 0.70932 | 0.74616 | 0.74616
$NDCG_{10}$ | 0.78606 | 0.7909 | 0.76598 | 0.76615 | 0.60653 | 0.62435 | 0.77669 | 0.76278 | 0.74751 | 0.74803
$NDCG_{30}$ | 0.78925 | 0.80109 | 0.77105 | 0.79075 | 0.65223 | 0.65897 | 0.83598 | 0.83119 | 0.8114 | 0.82537
$NDCG_{\infty}$ | 0.95405 | 0.95487 | 0.94823 | 0.94994 | 0.91469 | 0.9183 | 0.93111 | 0.93085 | 0.92612 | 0.92707
Eigenvector centrality | $r$ | -0.44537 | -0.48593 | -0.39148 | -0.42817 | -0.27852 | -0.30874 | -0.39567 | -0.40914 | -0.32824 | -0.35526
$NDCG_{5}$ | 0.80537 | 0.80537 | 0.76455 | 0.80467 | 0.56548 | 0.56316 | 0.72803 | 0.72803 | 0.74616 | 0.74616
$NDCG_{10}$ | 0.76883 | 0.79306 | 0.78463 | 0.7943 | 0.57262 | 0.62769 | 0.75086 | 0.75131 | 0.73821 | 0.74613
$NDCG_{30}$ | 0.79576 | 0.82797 | 0.80284 | 0.80998 | 0.61835 | 0.64429 | 0.82442 | 0.82767 | 0.80787 | 0.82032
$NDCG_{\infty}$ | 0.95253 | 0.9555 | 0.94964 | 0.95375 | 0.91034 | 0.91676 | 0.9287 | 0.9291 | 0.92667 | 0.92774
Current flow closeness centrality | $r$ | -0.47191 | -0.49028 | -0.40531 | -0.42364 | -0.30237 | -0.32131 | -0.38624 | -0.39283 | -0.31552 | -0.3281
$NDCG_{5}$ | 0.80752 | 0.80636 | 0.76455 | 0.76455 | 0.55359 | 0.57103 | 0.70932 | 0.70932 | 0.74616 | 0.74616
$NDCG_{10}$ | 0.79219 | 0.7909 | 0.76598 | 0.76757 | 0.62058 | 0.62564 | 0.77632 | 0.75592 | 0.74803 | 0.74803
$NDCG_{30}$ | 0.79853 | 0.79825 | 0.79281 | 0.79623 | 0.65868 | 0.65887 | 0.83509 | 0.83094 | 0.83161 | 0.83389
$NDCG_{\infty}$ | 0.95449 | 0.95525 | 0.94871 | 0.95077 | 0.91672 | 0.91816 | 0.93091 | 0.93102 | 0.92737 | 0.92755
Clustering | $r$ | -0.51834 | -0.53873 | -0.44969 | -0.46788 | -0.34343 | -0.36488 | -0.43742 | -0.44209 | -0.36639 | -0.38343
$NDCG_{5}$ | 0.80752 | 0.76396 | 0.73755 | 0.75747 | 0.57692 | 0.56709 | 0.70932 | 0.70932 | 0.72815 | 0.74616
$NDCG_{10}$ | 0.78795 | 0.79129 | 0.76494 | 0.76554 | 0.61572 | 0.62358 | 0.77699 | 0.76303 | 0.74765 | 0.74819
$NDCG_{30}$ | 0.79776 | 0.82022 | 0.79734 | 0.82093 | 0.67449 | 0.66871 | 0.83746 | 0.8377 | 0.82552 | 0.83347
$NDCG_{\infty}$ | 0.95701 | 0.95798 | 0.95111 | 0.95279 | 0.92056 | 0.92086 | 0.93313 | 0.9333 | 0.92919 | 0.92996
Table 2: Metric comparisons of the classic mobility network and the motif-
based mobility network.

Figure 6: The upper bounds of the ranking improvements and the relative
ranking improvements. The dark bars are the upper bounds and the light bars
inside are those of the relative ranking improvements.

Next, we explain how much improvement is made by the motif-based mobility
networks in characterizing regional importance ranking. Let
$r_{G^{\prime}}(i)$ and $r_{\mathcal{G}}(i)$ be the ranking of station $i$
calculated by a certain node importance indicator, $r_{hp}(i)$ be the house
price ranking around station $i$. Then, $\sum_{i\in
V}|r_{G^{\prime}}(i)-r_{\mathcal{G}}(i)|$ is the sum of differences of the
calculated rankings of the same station in the two mobility networks. This
absolute difference of node rankings based on the two networks is the upper
bound of ranking improvement. $\sum_{i\in
V}(|r_{G^{\prime}}(i)-r_{hp}(i)|-|r_{\mathcal{G}}(i)-r_{hp}(i)|)$ is the
relative ranking improvement of $r_{\mathcal{G}}$ with respect to
$r_{G^{\prime}}$. Fig. 6 shows the upper bounds of ranking improvements and
the relative ranking improvements with different node importance indicators
and different data sets. Except that the ranking improvement of Hangzhou
weekdays by current flow closeness is $-2$, in all other cases, the motif-
based mobility networks have made evident improvements in ranking compared
with the classic mobility networks. Especially, when the eigenvector
centrality is used as the indicator of node importance, the improvements are
fairly obvious (this can also be observed from Fig. 5).

From a network science perspective, we explore the higher-order structure of
mobility networks by analyzing actual mobility motifs instead of exhaustively
enumerating network motifs or simple subgraphs. This approach holds practical
significance, and our results validate that employing higher-order network
concepts can indeed yield better results in our scenario. This enhancement is
not a result of selectively choosing favorable outcomes from an exhaustive
search of network motifs or simple subgraphs.

###  5.2 Motif-wise human mobility networks

Figure 7: The correlation between house price and node ranking by PageRank.
Data from different cities and time periods are divided into five columns. The
top two rows respectively depict the correlations of the weighted average
house price against a measure of the rankings of metro stations in $G$ and
$\mathbb{G}(w=1)$; 95% confidence intervals are displayed. The Pearson
correlation coefficient is shown in each subgraph. $NDCG_{k}$ of $G$ and
$\mathbb{G}$ are compared in the bottom row.

It should be noted that people’s travel patterns are directional. Therefore,
we propose the motif-wise framework. We now compare the effectiveness of node
importance ranking in motif-wise mobility networks $\mathbb{G}$ against
classic mobility networks $G$ by PageRank. As shown in Fig. 7, the accuracy of
characterizing regional importance has increased significantly in all cities
for all time periods.

Among the four node importance indicators mentioned above, eigenvector
centrality can also be extended to directed graphs. We thus calculate the
importance of nodes by eigenvector centrality and present the comparison
results of our framework with the classic one. Meanwhile, as a comparison, we
also establish 2-dimensional de Bruijn graph $G_{de}$ of human mobility[15,
16], where the memory nodes $\overrightarrow{ij}$ represent trips in metro and
edges $\overrightarrow{ij}\rightarrow\overrightarrow{jk}$ represent connected
trips, with weights $W(\overrightarrow{ij}\rightarrow\overrightarrow{jk})$
proportional to the passenger volume between stations and conditional on the
previously visited station. The method can capture the second-order Markov
process, which is another typical model useful for exploring the higher-order
organization of complex systems.

We list comprehensive results of node importance ranking by PageRank and
eigenvector centrality in human mobility networks in Tables. 3 and 4,
respectively. In these two tables, we consider motif-wise mobility networks
with the restriction of both $w=1$ and $w=1/n$. We highlight the better
results in bold. Overall, it is obvious that $\mathbb{G}$ modeled by our
framework has a significant improvement in node importance ranking than $G$
and $G_{de}$ in almost all aspects. From the perspective of node importance
indicators, PageRank even performs slightly better than eigenvector centrality
in characterizing regional importance, likely because our framework borrows
the idea of PageRank. To our surprise, the results calculated by $G_{de}$
based on PageRank show poor performance. There is almost no correlation
between the calculated node ranking and house price. The results on $NDCG$ are
also far worse than all other methods. Only when using eigenvector centrality
as the indicator, the correlation between node importance ranking and house
price can be observed, where $G_{de}$ has a better performance compared to $G$
in Shanghai and Hangzhou. However, when $NDCG$ is used for assessment,
$G_{de}$ still performs worse than $G$. It is probably because all motifs with
only one trip in one day have to be ignored when constructing the de Bruijn
graph but these motifs are non-negligible.

The proposed motif-wise framework has a performance boost compared with the
motif-based framework according to $NDCG$. Moreover, the computed rankings of
node importance display stronger linear correlations with house prices. The
increasing performance is presented with comparisons between Table 3 (or Table
4) and Table 2.

| Network | $r$ | $NDCG_{5}$ | $NDCG_{10}$ | $NDCG_{30}$ | $NDCG_{\infty}$
---|---|---|---|---|---|---
Shanghai (weekdays) | $G$ | -0.47437 | 0.80752 | 0.79219 | 0.80156 | 0.95463
$G_{de}$ | 0.10465 | 0.58126 | 0.58793 | 0.61406 | 0.90752
$\mathbb{G}(w=1)$ | -0.64992 | 0.80837 | 0.81415 | 0.84586 | 0.9654
$\mathbb{G}(w=1/n)$ | -0.63137 | 0.81346 | 0.81752 | 0.8363 | 0.96452
Shanghai (weekends) | $G$ | -0.40172 | 0.76455 | 0.76598 | 0.78683 | 0.94858
$G_{de}$ | 0.00895 | 0.65538 | 0.6451 | 0.65953 | 0.91909
$\mathbb{G}(w=1)$ | -0.54842 | 0.76689 | 0.795 | 0.83449 | 0.959
$\mathbb{G}(w=1/n)$ | -0.51458 | 0.76689 | 0.79202 | 0.81929 | 0.95598
Beijing | $G$ | -0.30581 | 0.56548 | 0.60876 | 0.65616 | 0.91549
$G_{de}$ | 0.22892 | 0.46547 | 0.46941 | 0.50496 | 0.87686
$\mathbb{G}(w=1)$ | -0.54999 | 0.65213 | 0.64326 | 0.73026 | 0.9366
$\mathbb{G}(w=1/n)$ | -0.5167 | 0.58032 | 0.63962 | 0.72527 | 0.93266
Hangzhou (weekdays) | $G$ | -0.38125 | 0.70932 | 0.77438 | 0.837 | 0.93179
$G_{de}$ | 0.07817 | 0.51221 | 0.62363 | 0.72975 | 0.89179
$\mathbb{G}(w=1)$ | -0.50266 | 0.70932 | 0.78535 | 0.85382 | 0.93772
$\mathbb{G}(w=1/n)$ | -0.49589 | 0.70421 | 0.78128 | 0.85182 | 0.93635
Hangzhou (weekends) | $G$ | -0.29324 | 0.74616 | 0.74803 | 0.81195 | 0.92645
$G_{de}$ | 0.02113 | 0.67452 | 0.68211 | 0.75897 | 0.90957
$\mathbb{G}(w=1)$ | -0.41012 | 0.74616 | 0.76545 | 0.84227 | 0.9328
$\mathbb{G}(w=1/n)$ | -0.39366 | 0.72139 | 0.75495 | 0.83956 | 0.93092
Table 3: PageRank ranking results of the classic mobility network and the motif-wise mobility network. | Network | $r$ | $NDCG_{5}$ | $NDCG_{10}$ | $NDCG_{30}$ | $NDCG_{\infty}$
---|---|---|---|---|---|---
Shanghai (weekdays) | $G$ | -0.44611 | 0.81049 | 0.77046 | 0.79702 | 0.95287
$G_{de}$ | -0.44683 | 0.74952 | 0.71908 | 0.76939 | 0.94828
$\mathbb{G}(w=1)$ | -0.63712 | 0.81784 | 0.81262 | 0.84221 | 0.96538
$\mathbb{G}(w=1/n)$ | -0.61425 | 0.81915 | 0.81244 | 0.8314 | 0.96378
Shanghai (weekends) | $G$ | -0.38124 | 0.77995 | 0.78544 | 0.80291 | 0.94907
$G_{de}$ | -0.40532 | 0.72745 | 0.72244 | 0.76807 | 0.94611
$\mathbb{G}(w=1)$ | -0.52934 | 0.76455 | 0.79377 | 0.8283 | 0.95801
$\mathbb{G}(w=1/n)$ | -0.49215 | 0.76675 | 0.79417 | 0.82718 | 0.95562
Beijing | $G$ | -0.28222 | 0.56665 | 0.5684 | 0.61997 | 0.91154
$G_{de}$ | -0.20309 | 0.55528 | 0.55611 | 0.58689 | 0.90424
$\mathbb{G}(w=1)$ | -0.51886 | 0.59871 | 0.63777 | 0.72506 | 0.93369
$\mathbb{G}(w=1/n)$ | -0.48905 | 0.56548 | 0.61076 | 0.70807 | 0.92774
Hangzhou (weekdays) | $G$ | -0.40051 | 0.72803 | 0.75131 | 0.8254 | 0.9294
$G_{de}$ | -0.42487 | 0.71044 | 0.73556 | 0.82667 | 0.92903
$\mathbb{G}(w=1)$ | -0.45648 | 0.72803 | 0.77936 | 0.83635 | 0.9334
$\mathbb{G}(w=1/n)$ | -0.4363 | 0.70421 | 0.77485 | 0.83165 | 0.93036
Hangzhou (weekends) | $G$ | -0.32708 | 0.74616 | 0.75471 | 0.81699 | 0.92723
$G_{de}$ | -0.40993 | 0.72916 | 0.75701 | 0.8362 | 0.93062
$\mathbb{G}(w=1)$ | -0.39722 | 0.7978 | 0.78793 | 0.84913 | 0.94149
$\mathbb{G}(w=1/n)$ | -0.38363 | 0.72139 | 0.75121 | 0.82658 | 0.92811
Table 4: Eigenvector centrality ranking results of the classic mobility
network and motif-wise mobility network. Figure 8: Comparisons between $G$ and
$\mathbb{G}(w=1)$ critera on Shanghai Big Data Activity Report in 2017.

To further illustrate the superiority of our framework, we evaluate the
characterization results with an official report. Yicai, an official financial
news arm of Shanghai Media Group333https://www.yicaiglobal.com/, released the
Shanghai Big Data Activity Report in 2017. The report conducted a
comprehensive analysis of the regional functions, consumer profiles, and
business development in the vicinity of Shanghai metro stations. These factors
serve as criteria for assessing regional importance. Top 100 metro stations
are listed444https://metrocity.dtcj.com/shanghai. Among these 100 stations,
there are 5 newly built stations not shown in our data. We take the rankings
of the remaining 95 stations as the criterion and use $NDCG$ again to compare
the ranking results of our framework and the classic one. In this context, the
relevance score $rel_{i}=1$ if the $i$-th important station calculated by the
algorithm is also in the top-$k$ list of the criterion, otherwise $rel_{i}=0$.
As shown in Fig. 8, $NDCG_{k}$ calculated by our framework (solid lines) are
in the majority greater than those of traditional one (dashed lines),
indicating that our framework again achieves significantly better performance.

Figure 9: The upper bounds of the ranking improvements and the relative
ranking improvements. The dark bars are the upper bounds and the light bars
inside are those of the relative ranking improvements.

We show the upper bounds of the ranking improvements and the relative ranking
improvements in Fig. 9. With our motif-wise framework, the upper bounds of the
ranking improvements are over three times higher than that of the motif-based
network. Moreover, the relative ranking improvements are much closer to the
upper bounds of the ranking improvements in all cities. Overall, after the
construction of the motif-wise mobility network, the node importance ranking
performance is significantly improved.

Figure 10: Relationship between in-strength and out-strength and the
correlation matrix of node indicators of Shanghai (weekdays) data. (Left) The
correlation between $W_{ij}$ and $W_{ji}$ of $G$. The colors indicate the
numbers of the corresponding edges. (Right) Pearson correlation coefficients
between node strength (the magnitude of passenger flows at stations) and four
calculated node importance indicators in $G^{\prime}$. ST: strength; PR:
PageRank; EC: eigenvector centrality; CC: current flow closeness centrality;
CL: clustering coefficient.

###  5.3 Discussion

We attempt to discuss the reasons for the differences in the results under the
two network construction methods from the perspective of real urban scenarios.

In China, there exist some areas in large cities called “bedroom communities”.
Many citizens live in these communities far from the city center just to
sleep. Their working and entertainment places are probably far away from their
living places, resulting in huge passenger flows at the metro stations around
these communities. Since in human mobility network $G$, $W_{ij}\approx
W_{ji}$, node importance is strongly associated with the strength of the node
(the magnitude of passenger flow) according to the calculation of node
importance indicators in the undirected weighted network (see Fig. 10).
However, the magnitude of passenger flows may not accurately represent the
regional importance in the city. To further clarify this, we identify the top
10 stations with the largest declines in ranking obtained from the comparison
of the classic framework and the proposed framework. We observe that these
stations are primarily located in large residential communities in suburban
areas. Taking Beijing as an example, as shown in Table 5, the surrounding
regions of such stations are mostly famous super-sized communities located in
the suburbs. These areas experience super large passenger flows, leading to
their high rankings in $G$. Yet, from a public perspective, these areas are
not that comprehensively important. Our motif-wise framework addresses real
human travel purposes and establishes a new directed weight allocation method,
making the ranking results closer to reality by a large margin.

Station Name |  | PageRank
---
ranking in $G$
| PageRank
---
ranking in $\mathbb{G}$
| Actual
---
ranking
Changyang | 108 | 181 | 234
Tiantongyuan North | 21 | 94 | 261
Longze | 47 | 124 | 207
Lishuiqiao | 35 | 115 | 176
Wuzi Xueyuan Lu | 66 | 146 | 237
Tiantongyuan | 13 | 96 | 256
Jin’an Qiao | 44 | 128 | 228
Huilong Guan | 41 | 136 | 220
Huilong Guan Dongdajie | 59 | 179 | 227
Huoying | 28 | 153 | 202

Table 5: The top 10 stations with the largest declines in ranking resulted
from the two network construction methods.

##  6 Conclusion

In the existing literature, significant strides have been made in the analysis
of individual-level statistics and modeling, as well as in the exploration of
population-level mobility patterns. Recent years have witnessed a growing
emphasis on bridging the gap between meso-level individual travel patterns and
macro-level population mobility, enriching our comprehension of the intricate
dynamics of cities. This paper represents the inaugural endeavor to employ
human mobility motifs in investigating urban mobility networks and assessing
regional importance.

We first propose a bottom-up framework to model a motif-based mobility network
that aggregates the reorganized individual mobility motifs by addition. Under
this framework, the performance of characterizing the importance of regions is
indeed improved. Comparing it to the previous top-down approach in exploring
the higher-order organization of networks, our method eliminates the need for
manual specification of motifs or subgraphs. The human mobility motifs that
are aggregated to construct the whole network are all generated by real trips
of passengers. This opens up a new direction for studying the higher-order
properties of complex networks.

We then propose a weight allocation method by establishing a motif-wise
framework, where individuals carry weights from their initial station to each
destination station during trips. Under this framework, we aggregate the
reorganized human mobility motifs to construct motif-wise networks. Compared
with the classic mobility network, the performance of the motif-wise network
in characterizing the importance of regions is greatly improved.

In summary, mobility motifs, also known as higher-order mobility structures,
are considered as fundamental units of human mobility networks instead of
first-order trips. Two motif reorganization methods are proposed under two
frameworks, which enable the modeling of human mobility networks at the level
of mobility motifs. The significance lies in that these cannot be achieved
when only first-order single trips are considered. This underlines the potency
of higher-order mobility motifs as a powerful tool for unraveling the higher-
order organization within human mobility networks.

## References

  * [1] M. Batty, “The size, scale, and shape of cities,” _science_ , vol. 319, no. 5864, pp. 769–771, 2008.
  * [2] K. Pollock, “Policy: urban physics,” _Nature_ , vol. 531, no. 7594, pp. S64–S66, 2016.
  * [3] F. Xia, J. Wang, X. Kong, D. Zhang, and Z. Wang, “Ranking station importance with human mobility patterns using subway network datasets,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 7, pp. 2840–2852, 2019.
  * [4] Z. Zhou, K. Yang, Y. Liang, B. Wang, H. Chen, and Y. Wang, “Predicting collective human mobility via countering spatiotemporal heterogeneity,” _IEEE Transactions on Mobile Computing_ , 2023.
  * [5] T. Gu, M. Zhu, W. Chen, Z. Huang, R. Maciejewski, and L. Chang, “Structuring mobility transition with an adaptive graph representation,” _IEEE Transactions on Computational Social Systems_ , vol. 5, no. 4, pp. 1121–1132, 2018.
  * [6] Y. Cheng, C. Li, Y. Zhang, S. He, and J. Chen, “Spatial–temporal urban mobility pattern analysis during covid-19 pandemic,” _IEEE Transactions on Computational Social Systems_ , vol. 11, no. 1, pp. 38–50, 2024.
  * [7] X. Liu, L. Gong, Y. Gong, and Y. Liu, “Revealing travel patterns and city structure with taxi trip data,” _Journal of transport Geography_ , vol. 43, pp. 78–90, 2015.
  * [8] J. Tang, S. Zhang, W. Zhang, F. Liu, W. Zhang, and Y. Wang, “Statistical properties of urban mobility from location-based travel networks,” _Physica A: Statistical Mechanics and its Applications_ , vol. 461, pp. 694–707, 2016.
  * [9] C. Zhong, S. M. Arisona, X. Huang, M. Batty, and G. Schmitt, “Detecting the dynamics of urban structure through spatial network analysis,” _International Journal of Geographical Information Science_ , vol. 28, no. 11, pp. 2178–2199, 2014.
  * [10] S. Shi, L. Wang, and X. Wang, “Uncovering the spatiotemporal motif patterns in urban mobility networks by non-negative tensor decomposition,” _Physica A: Statistical Mechanics and its Applications_ , vol. 606, p. 128142, 2022.
  * [11] H. Barbosa, M. Barthelemy, G. Ghoshal, C. R. James, M. Lenormand, T. Louail, R. Menezes, J. J. Ramasco, F. Simini, and M. Tomasini, “Human mobility: Models and applications,” _Physics Reports_ , vol. 734, pp. 1–74, 2018.
  * [12] Y. Zhou, B. P. L. Lau, C. Yuen, B. Tunçer, and E. Wilhelm, “Understanding urban human mobility through crowdsensed data,” _IEEE Communications Magazine_ , vol. 56, no. 11, pp. 52–59, 2018.
  * [13] H. Nilforoshan, W. Looi, E. Pierson, B. Villanueva, N. Fishman, Y. Chen, J. Sholar, B. Redbird, D. Grusky, and J. Leskovec, “Human mobility networks reveal increased segregation in large cities,” _Nature_ , pp. 1–7, 2023.
  * [14] W. Jia, K. Zhao, and S. Zhao, “The hierarchical clustering of human mobility behaviors,” _IEEE Transactions on Computational Social Systems_ , pp. 1–12, 2023.
  * [15] R. Lambiotte, M. Rosvall, and I. Scholtes, “From networks to optimal higher-order models of complex systems,” _Nature Physics_ , vol. 15, no. 4, pp. 313–320, 2019.
  * [16] M. Rosvall, A. V. Esquivel, A. Lancichinetti, J. D. West, and R. Lambiotte, “Memory in network flows and its effects on spreading dynamics and community detection,” _Nature Communications_ , vol. 5, no. 1, pp. 1–13, 2014.
  * [17] C. M. Schneider, V. Belik, T. Couronné, Z. Smoreda, and M. C. González, “Unravelling daily human mobility motifs,” _Journal of The Royal Society Interface_ , vol. 10, no. 84, p. 20130246, 2013.
  * [18] H. Zhao, X. Xu, Y. Song, D. L. Lee, Z. Chen, and H. Gao, “Ranking users in social networks with motif-based pagerank,” _IEEE Transactions on Knowledge and Data Engineering_ , 2019.
  * [19] A. R. Benson, D. F. Gleich, and J. Leskovec, “Higher-order organization of complex networks,” _Science_ , vol. 353, no. 6295, pp. 163–166, 2016.
  * [20] X. Li, R. Cheng, K. C.-C. Chang, C. Shan, C. Ma, and H. Cao, “On analyzing graphs with motif-paths,” _Proceedings of the VLDB Endowment_ , vol. 14, no. 6, pp. 1111–1123, 2021.
  * [21] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “Network motifs: simple building blocks of complex networks,” _Science_ , vol. 298, no. 5594, pp. 824–827, 2002.
  * [22] H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich, “Local higher-order graph clustering,” in _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2017, pp. 555–564.
  * [23] F. Xia, S. Yu, C. Liu, J. Li, and I. Lee, “Chief: Clustering with higher-order motifs in big networks,” _IEEE Transactions on Network Science and Engineering_ , vol. 9, no. 3, pp. 990–1005, 2022.
  * [24] P.-Z. Li, L. Huang, C.-D. Wang, J.-H. Lai, and D. Huang, “Community detection by motif-aware label propagation,” _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , vol. 14, no. 2, pp. 1–19, 2020.
  * [25] Y. Gao, H. Zhang, and X. Yu, “Higher-order community detection: On information degeneration and its elimination,” _IEEE/ACM Transactions on Networking_ , 2022.
  * [26] C. Ma, B.-B. Xiang, H.-S. Chen, M. Small, and H.-F. Zhang, “Detection of core-periphery structure in networks based on 3-tuple motifs,” _Chaos: An Interdisciplinary Journal of Nonlinear Science_ , vol. 28, no. 5, p. 053121, 2018.
  * [27] J. Chen, M. Feng, D. Zhao, C. Xia, and Z. Wang, “Composite effective degree markov chain for epidemic dynamics on higher-order networks,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , vol. 53, no. 12, pp. 7415–7426, 2023.
  * [28] M. Liu, J. Li, Z. Yang, and K. Yang, “Higher-order functional structure exploration in heterogeneous combat network based on operational motif spectral clustering,” _IEEE Systems Journal_ , vol. 17, no. 3, pp. 4279–4290, 2023.
  * [29] J. Cao, Q. Li, W. Tu, and F. Wang, “Characterizing preferred motif choices and distance impacts,” _PloS One_ , vol. 14, no. 4, p. e0215242, 2019.
  * [30] R. Su, E. C. McBride, and K. G. Goulias, “Pattern recognition of daily activity patterns using human mobility motifs and sequence analysis,” _Transportation Research Part C: Emerging Technologies_ , vol. 120, p. 102796, 2020.
  * [31] ——, “Unveiling daily activity pattern differences between telecommuters and commuters using human mobility motifs and sequence analysis,” _Transportation Research Part A: Policy and Practice_ , vol. 147, pp. 106–132, 2021.
  * [32] Z. Liu, J. Yu, W. Xiong, J. Lu, J. Yang, and Q. Wang, “Using mobile phone data to explore spatial-temporal evolution of home-based daily mobility patterns in shanghai,” in _2016 International Conference on Behavioral, Economic and Socio-cultural Computing (BESC)_. IEEE, 2016, pp. 1–6.
  * [33] S. Jiang, J. Ferreira, and M. C. Gonzalez, “Activity-based human mobility patterns inferred from mobile phone data: A case study of singapore,” _IEEE Transactions on Big Data_ , vol. 3, no. 2, pp. 208–219, 2017.
  * [34] Y. Chen, N. Xie, H. Xu, X. Chen, and D.-H. Lee, “A multi-context aware human mobility prediction model based on motif-preserving travel preference learning,” _IEEE Transactions on Intelligent Transportation Systems_ , pp. 1–14, 2023.
  * [35] Q. Xiong, Y. Liu, P. Xie, Y. Wang, and Y. Liu, “Revealing correlation patterns of individual location activity motifs between workdays and day-offs using massive mobile phone data,” _Computers, Environment and Urban Systems_ , vol. 89, p. 101682, 2021.
  * [36] X. Ling, Z. Huang, C. Wang, F. Zhang, and P. Wang, “Predicting subway passenger flows under different traffic conditions,” _PLoS One_ , vol. 13, no. 8, p. e0202707, 2018.
  * [37] E. Chen, Z. Ye, C. Wang, and M. Xu, “Subway passenger flow prediction for special events using smart card data,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 3, pp. 1109–1120, 2019.
  * [38] S. Shi, L. Wang, S. Xu, and X. Wang, “Prediction of intra-urban human mobility by integrating regional functions and trip intentions,” _IEEE Transactions on Knowledge and Data Engineering_ , 2020.
  * [39] K. He, Z. Xu, P. Wang, L. Deng, and L. Tu, “Congestion avoidance routing based on large-scale social signals,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 17, no. 9, pp. 2613–2626, 2015.
  * [40] Y. Xing, J. Lu, and S. Chen, “Weighted complex network analysis of shanghai rail transit system,” _Discrete Dynamics in Nature and Society_ , vol. 2016, 2016.
  * [41] 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.
  * [42] N. Yong, S. Ni, S. Shen, P. Chen, and X. Ji, “Uncovering stable and occasional human mobility patterns: A case study of the beijing subway,” _Physica A: Statistical Mechanics and its Applications_ , vol. 492, pp. 28–38, 2018.
  * [43] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web.” Stanford InfoLab, Tech. Rep., 1999.
  * [44] L. M. Bettencourt, J. Lobo, D. Helbing, C. Kühnert, and G. B. West, “Growth, innovation, scaling, and the pace of life in cities,” _Proceedings of the National Academy of Sciences_ , vol. 104, no. 17, pp. 7301–7306, 2007.
  * [45] L. M. Bettencourt, “The origins of scaling in cities,” _science_ , vol. 340, no. 6139, pp. 1438–1441, 2013.
  * [46] J. Raimbault, “Indirect evidence of network effects in a system of cities,” _Environment and Planning B: Urban Analytics and City Science_ , vol. 47, no. 1, pp. 138–155, 2020.


# Deep Contextual Bandits for Fast Neighbor-Aided Initial Access in mmWave
Cell-Free Networks

Insaf Ismath, Samad Ali, Nandana Rajatheva, and Matti Latva-aho  Center for
Wireless Communication, University of Oulu, Oulu, Finland {insaf.ismath,
samad.ali, nandana.rajatheva<EMAIL_ADDRESS>
###### Abstract

Access points (APs) in millimeter-wave (mmWave) and sub-THz-based user-centric
(UC) networks will have sleep mode functionality. As a result of this, it
becomes challenging to solve the initial access (IA) problem when the sleeping
APs are activated to start serving users. In this paper, a novel deep
contextual bandit (DCB) learning method is proposed to provide instant IA
using information from the neighboring active APs. In the proposed approach,
beam selection information from the neighboring active APs is used as an input
to neural networks that act as a function approximator for the bandit
algorithm. Simulations are carried out with realistic channel models generated
using the Wireless Insight ray-tracing tool. The results show that the system
can respond to dynamic throughput demands with negligible latency compared to
the standard baseline 5G IA scheme. The proposed fast beam selection scheme
can enable the network to use energy-saving sleep modes without compromising
the quality of service due to inefficient IA.

###### Index Terms:

Initial access, mmWave, deep contextual bandits, user-centric, deep
reinforcement learning.

##  I Introduction

To facilitate applications like extended reality (XR) that demand high-
throughput low-latency communication, networks of the future are expected to
provide at least a 1000-fold increase in network throughput [1]. Despite high
sensitivity to blockages, millimeter wave (mmWave) and sub-THz bands will be
exploited to attain throughput goals[2]. Massive multiple-input multiple-
output (MIMO) enabled user-centric (UC) topology is proposed as an alternative
to the cellular architecture[3]. Users in a UC network are simultaneously
served with coherent transmissions made by multiple APs. Since mmWave and THz
communications rely mostly on line-of-sight (LOS) links, APs are needed to be
densely deployed to ensure reliability. However, all the APs might not be
required all the time to provide a good quality of service[4]. Therefore,
maintaining a network with a large number of otherwise redundant APs causes
considerably inefficient power usage.

The work in [5, 4, 6] present strategies to optimize the energy consumption of
the network; each user is only served by a sub-set of APs. The network power
consumption is minimized by optimizing the AP sub-set selection to meet a
minimum user throughput requirement. The functionality of the redundant APs is
reduced and put into a low power consumption mode called the sleep-state.
Although having the sleep-state improves energy efficiency, it compromises the
agility of the network. With highly dynamic mmWave channels, users may
suddenly lose connections to some APs[2]. Furthermore, users may instantly
need additional radio resources to begin or maintain high-throughput low-
latency applications. To maintain a consistent quality of service against the
above-discussed scenarios and more, sleep-state APs are required to start
contributing to the network capacity as soon as the normal functionality is
restored. However, the 5G IA system achieves synchronization and identifies
beams to serve users using a lengthy exhaustive search-based beam-sweep which
is performed in a dedicated time-slot in the radio frame [7]. Since radio
frames have to be synchronized between the APs to enable simultaneous user
serving, a newly restored AP has to wait for the next common IA period to
perform IA. Hence, the 5G IA method adds two latency components: lengthy IA
procedure and the wait for the next IA slot, leading to a compromise between
energy efficiency and quality of service. Therefore, with the 5G initial
access (IA) procedure newly restored APs are unable to instantly contribute to
the network.

Recently, a new wave of interest has surged in using machine learning (ML) in
wireless communications [8]. Some ML methods can be applied to the IA problem.
For example, the work in [9] presents an ML-based approach for fast IA in
ultra-dense UC systems. Inspired by ML solutions, in this work we propose a
novel deep contextual bandit (DCB) based neighbor-aided IA approach to avoid
the compromise between energy efficiency and quality of service. With this
novel approach, a newly woken AP can instantaneously start serving the users
irrespective of where the AP was restored in the radio frame. The DCB model in
each AP learns about the environment through the beam choices made by the
neighboring APs. Using this knowledge, the DCB model learns to map a given set
of beam choices made by neighbors to one of its beams. Strictly speaking, the
DCB model takes the beam choice made by its neighboring APs to serve a user as
the input and predicts the beam which it should select to serve the same user
as the output.

The proposed method provides instantaneously beam selection for recently
restored APs irrespective of the location at the radio frame. Hence, the
energy efficiency is enhanced by enabling the use of a sleeping mechanism for
APs without incurring a latency penalty, and therefore, the network
flexibility is not compromised. The performance of this neighbor-aided IA
system is evaluated using realistic scenarios generated using a ray-tracing
tool. Simulation results for the considered scenario show that the
instantaneous predictions of the DCB model achieve 96% of the best case
signal-to-noise ratio (SNR) while maintaining a negligible latency.

The rest of this paper is organized as follows. Section II explains the system
model used in this work and introduces the IA problem. Section III formally
presents the proposed approach and provides a quick primer on DCB. Section IV
explains details about the simulations and presents numerical results and
Section V concludes the paper.

Notations: $(.)^{T}$, and $(.)^{H}$ denote transpose and Hermitian transpose,
respectively. $\mathcal{R}(\mathbf{x})$ and $\mathcal{I}(\mathbf{x})$
represents the real and imaginary parts of $\mathbf{x}$, respectively.
$||\mathbf{x}||$ and $|\mathbf{x}|$ denote the euclidean norm and cardinality
of $\mathbf{x}$, respectively.

Figure 1: The system model of a UC network where a subset of APs would
simultaneously serve a single user[3]. APs can either operate as awake-state
PAPs or as sleep-state SAPs.

##  II System Model and Problem Formulation

###  II-A System Model

Consider a UC network with a set of $N$ densely deployed APs and one user as
presented in Fig. 1. APs are equipped with uniform rectangular planar antenna
arrays (URPA) with $M$ antenna-elements. According to the UC architecture[3],
the single antenna user is simultaneously served by multiple APs to ensure
reliability and to maintain high throughput communication. All APs are
connected to their controlling entity, the central processing unit (CPU) via
backhaul links. To conserve energy APs can operate in two power consumption
modes: the fully functional awake-state and the reduced functionality power-
saving sleep-state[6]. APs in the awake-state and sleep-state are defined as
primary APs (PAPs) and secondary APs (SAPs), respectively. Only a subset of
APs are maintained as PAPs; remaining APs are put to the sleep-state. Each PAP
periodically performs the 5G IA procedure using beam-sweeps to identify the
user serving beam and to synchronize the network.

The mmWave channel is modeled with a clustered model[10]. Each channel is
generated using $K$ clusters which are made combining $Q$ paths characterized
by path loss, fading, and array gain at the AP. The subscript notations
$k=1,\dots,K$ and $q=1,\dots,Q$ represent cluster and path index,
respectively. The channel from an AP to the user
$\mathbf{h}\in\mathbf{C}^{1\times M}$ is presented as

$\mathbf{h}=\frac{1}{\sqrt{Q}}\sum_{k=1}^{K}\sum_{q=1}^{Q}p_{k,q}r_{k,q}\mathbf{a}(\theta_{k,q},\phi_{k,q}),$
(1)

where $p_{k,q}\in\mathbf{C}$ and $r_{k,q}\in\mathbf{C}$ represent the path
loss and small-scale fading gain, respectively, and
$\mathbf{a}(\theta_{k,q},\phi_{k,q})\in\mathbf{C}^{1\times M}$ is the AP’s
array gain. Here $\theta_{k,q}$ and $\phi_{k,q}$ are the azimuth and elevation
angles of arrival at the AP, respectively. The channels used in this work are
generated using a ray-tracing tool called Wireless Insight[11] to capture
realistic mmWave behaviors.

Due to the cost and power consumption reasons, the authors in [2] suggest
using analog beamforming techniques for mmWave MIMO enabled APs. Hence, this
work considers analog beamforming which is implemented using an array of $M$
quantized phase shifters. Beamforming codebook $\mathbf{F}$ is the finite set
of $M$ beams generated using this arrangement and the $i$th beam
$\mathbf{f_{i}}\in\mathbf{F}$ is
$\frac{1}{\sqrt{M}}\left[e^{j\Theta_{i,1}}\;\dots\;e^{j\Theta_{i,M}}\right]^{T}$.
Here $\Theta_{i,m}$ is the phase shift added to the signal emitted from the
$m$th antenna-element corresponding to the $i$th beam.

###  II-B Problem Formulation

During IA, every AP has to identify the beam that maximizes the received SNR
at the user. The SNR component provided by the $n$th PAP to the user
$\Gamma_{n}$ is expressed as

$\displaystyle\Gamma_{n}=\frac{P_{n}||\mathbf{h_{n}}\mathbf{b_{n}}||^{2}}{\sigma^{2}},$
(2)

where $P_{n}$ is the transmit power of $n$th PAP, $\mathbf{h_{n}}$ is the
channel $\mathbf{h}$ from $n$th PAP to the user, $\mathbf{b_{n}}$ is the beam
chosen by $n$th PAP to serve the user, $\sigma^{2}$ is the noise power at the
user, and $\bar{N}$ is the number of PAPs serving the user. The IA problem for
the network is presented as

$\displaystyle\mathop{\operatorname{maximize}}_{\mathbf{B}}$
$\displaystyle\sum_{n=1}^{\bar{N}}\Gamma_{n}$ (3)
$\displaystyle\operatorname{subject\;to}$
$\displaystyle\mathbf{b_{n}}\in\mathbf{F}$ $\displaystyle\forall
n=1,\dots,\bar{N},$

where $\mathbf{B}=\left[\mathbf{b_{1}},...,\mathbf{b_{\bar{N}}}\right]$. The
5G IA procedure solves (3) using a beam-sweep at each PAP. Beam-sweeping is
performed using sequential transmissions of all or part of the beams in
$\mathbf{F}$ using orthogonal resources. The user reports the best beam from
each beam sweep to the corresponding AP. Furthermore, 5G IA is performed in a
dedicated time slot called physical broadcast channel (PBCH)111Commonly just
one IA opportunity is allocated per radio frame[7].. Since APs in the UC
architecture perform cooperative simultaneous serving, PBCHs have to be
synchronized between the APs. When an SAP has been restored the problem
formulation in (3) changes and the new problem is defined as

$\displaystyle\mathop{\operatorname{maximize}}_{\mathbf{B},\mathbf{b_{0}}}$
$\displaystyle\sum_{n=1}^{\bar{N}}\Gamma_{n}+\frac{P_{0}||\mathbf{h_{0}}\mathbf{b_{0}}||^{2}}{\sigma^{2}}$
(4) $\displaystyle\operatorname{subject\;to}$
$\displaystyle\mathbf{b_{n}}\in\mathbf{F}$ $\displaystyle\forall
n=0,\dots,\bar{N},$

where the familiar quantities with $0$th index correspond to the quantities of
the newly restored AP. With the 5G IA method, the newly restored AP has to
wait till the next PBCH to perform IA. Hence, although having a sleep-state
improves energy efficiency, the use of conventional beam-sweep-based IA
systems for this scenario introduces an additional latency component.

However, beam choices of PAPs, i.e., $\mathbf{B}$, were found when (3) was
resolved using 5G IA during the previous PBCH. This solution for $\mathbf{B}$
is valid for (4) since the next PBCH is yet to arrive. Hence, finding just
$\mathbf{b_{0}}$ is adequate to solve (4). The proposed approach solves (4) by
predicting $\mathbf{b_{0}}$ for the newly restored AP with a DCB model which
uses $\mathbf{B}$ and PAP location information $\mathbf{L}$ as inputs. Since
the proposed method avoids beam-sweeps, waiting for the next PBCH is not
required, and therefore, $\mathbf{b_{0}}$ is solved instantly irrespective of
the position in the radio frame. Hence, the proposed method enables any
recently restored AP to instantaneously supplement the throughput provided by
the PAPs to a user. With the IA-related latency component eradicated, the CPU
is free to adjust the network capacity to satisfy user demands in an energy-
efficient manner without compromising the quality of service.

##  III DCB based Neighbor-Aided Initial Access Approach

###  III-A Proposed Approach

The PAPs periodically share beam choices among the neighbors. The CPU may
utilize an algorithm similar to the work presented in [4, 5, 6] to determine
which SAP to be restored. In the proposed approach, the restored AP
approximates the achievable SNR for each $\mathbf{f_{i}}$ using the function
$\mathbf{g}(\mathbf{L},\mathbf{B})$ which is defined as

$\displaystyle\mathbf{g}(\mathbf{L},\mathbf{B}):\left\\{\mathbf{L}\right\\}\times\left\\{\mathbf{B}\right\\}\rightarrow\left\\{\frac{P_{0}||\mathbf{h_{0}}\mathbf{f_{i}}||^{2}}{\sigma^{2}}\right\\},\forall\mathbf{f_{i}}\in\mathbf{F},$
(5)

where $\left\\{\mathbf{L}\right\\}$ and $\left\\{\mathbf{B}\right\\}$
represents the vector space containing all possibilities for $\mathbf{L}$ and
$\mathbf{B}$, respectively. The optimum beam is selected as
$\mathbf{b_{0}}=\mathbf{f_{i^{*}}}$ where

$\mathbf{i^{*}}=\mathop{\operatorname{argmax}}_{\mathbf{i}\in\left\\{1,\dots|\mathbf{F}|\right\\}}\mathbf{g}(\mathbf{L},\mathbf{B}).$
(6)

Nevertheless, practical deployment settings experience a plethora of phenomena
such as the absence of LOS paths and shadowing among others which makes the
mathematical characterization of $\mathbf{g}(\mathbf{L},\mathbf{B})$ complex.

Authors of [12] use a DNN to approximate a similarly complex function which
maps beams between sub-6 GHz and mmWave bands. Inspired by this solution,
$\mathbf{g}(\mathbf{L},\mathbf{B})$ in this work is approximated using a DNN
based DCB black-box function approximator. Each AP is equipped with a DCB
model which explores the environment and learns
$\mathbf{g}(\mathbf{L},\mathbf{B})$ for the respective AP.

###  III-B An Introduction to Deep Contextual Bandits (DCB)

The contextual bandit is a special instance of the reinforcement learning
model called multi-arm bandits (MABs)[13]. Reinforcement learning
architectures have a software entity called the agent in an environment. The
agent can interact with the environment by performing actions selected from
the action-space that contains all possible actions. Each action entails a
numerical reward that judges the quality of the action. The goal of the agent
is to maximize the reward. Over time, the agent discovers the best action
which in the case of MAB is a constant. However, problems in domains like
wireless communication are dynamic in nature and may have different best
actions depending on the circumstance.

In contextual bandits, the agent learns the best actions for a given context
$\mathcal{X}$ which characterize the state of the environment; in the MAB
case, only one context exists and hence, the best action is a constant. The
agent can select an action by either referring to a simple context-action-
reward table or using advanced algorithms like Thompson sampling[14]. After
receiving the reward for the performed action, the parameters of the selection
mechanism are updated. However, in problems where the context space is
continuous and large, neither maintaining tables nor running these algorithms
is feasible, and therefore, a deep neural network (DNN) is used to predict the
reward for actions given $\mathcal{X}$ [15]. Contextual bandit models with
DNNs are called DCB. The agent follows a decaying $\epsilon$-greedy
exploration policy where the state-action-reward relationships are learned by
exploring the environment by taking random actions with a probability of
$\epsilon$. Otherwise, the agent leverages the already acquired knowledge to
choose actions to maximize reward. Initially, $\epsilon$ is set to 1 and in
every training episode, it decays by a factor of $\epsilon_{dec}$ until
$\epsilon=\epsilon_{min}$.

Since the DNN has to cater to two types of inputs: location data from
$\mathbf{L}$ and beam choices from $\mathbf{B}$, the context is ingested
through two independent input layers. Hence, the context is defined as

$\mathcal{X}\coloneqq\left[\begin{matrix}\mathbf{L}\\\
\left[\mathcal{R}\left(\mathbf{B}\right),\mathcal{I}\left(\mathbf{B}\right)\right]\end{matrix}\right].$
(7)

Most neural network tools only support real numbers, hence real and imaginary
parts of $\mathbf{B}$ are split and concatenated. The two rows of
$\mathcal{X}$ corresponds to the two input layers of the DNN. The outputs from
these two input layers are concatenated and fed into the rest of the DNN. The
action-space of the agent corresponds to the beam codebook, hence each action
represents a beam. Ideally, the reward should only represent the throughput
provided to the user by the AP using the beam choice made by the agent.
However, since multiple APs coherently serve the user, measuring individual
contributions is not straightforward. The reward $\alpha$ is defined as

$\alpha\coloneqq\frac{||\mathbf{h_{0}}\mathbf{b_{0}}||^{2}}{\sigma^{2}}\times\dfrac{1}{||\mathbf{h_{0}}\mathbf{h_{0}}^{H}||^{2}}.$
(8)

The normalization with $||\mathbf{h_{0}}\mathbf{h_{0}}^{H}||^{2}$ term in eq.
(8) benchmarks the performance of the chosen beam against the theoretical
optimum beam $\mathbf{h_{0}}^{H}$[16]. Instantaneous $\mathbf{h_{0}}$ is
approximated using the last available channel estimate
$\mathbf{\tilde{h}_{0}}$ which is assumed to be in the same channel coherence
interval with $\mathbf{h_{0}}$, and therefore,
$\mathbf{h_{0}}\approx\mathbf{\tilde{h}_{0}}$.

The performance of the DCB agent is evaluated using regret $\delta$ that
benchmarks the chosen action against the action which provides the highest
reward $\alpha_{max}$. In this work, $\delta$ is defined as

$\delta\coloneqq\alpha_{max}-\alpha.$ (9)

##  IV Simulations

###  IV-A Simulation Environment

Figure 2: The indoor office simulation environment.

The indoor office shown in Fig. 2 is considered for the simulations. An area
of 60 m $\times$ 30 m is partitioned using dry-wall into smaller office
spaces. The ceiling and the floor are built with concrete. This environment is
modeled using ITU 60 GHz compliant material models provided with Wireless
Insite ray-tracer[11]. A set of 6 APs is located 10 m apart in a grid
formation centering the ceiling which is 2.6 m above the floor. A grid of
possible user locations is defined spanning the office area. All AP and
possible user locations are denoted in red and green color markings in Fig. 2.

A carrier frequency of 60 GHz and a channel bandwidth of 100 MHz is
considered. All APs are equipped with URPA antennas with 16 elements in the 4
$\times$ 4 configuration. The gain and the noise figure of every antenna are
set to 5 and 3 dB, receptively. The transmit power of the APs, and the users
are set to 20 and 5 dBm, respectively. Each AP in the awake-state and sleep-
state is assumed to consumes 1 W[6] and 0.01 W, respectively. The beam
codebook is comprised of 16 beams.

A simulation round consists of 50,000 episodes. At the beginning of each
simulation round, a fixed number of PAPs are chosen at random. The
optimization of the PAP selection criterion is not considered since it is out
of the scope of this work. At each episode, the user is placed randomly in the
grid of possible user locations.

The DNN of the DCB model has 3 hidden layers with each containing 100 neurons.
Input layer one intakes $\mathbf{L}$ where each entry is comprised of latitude
and longitude value, and therefore, it has $2\times\bar{N}$ neurons. Input
layer two ingests $\mathbf{B}$ and it has $2\times M\times\bar{N}$ neurons.
The output layer contains $M$ neurons corresponding to $M$ beams (actions).
ReLu and Adam have been used as the layer activation function and the
optimizer respectively. Both dropout and learning rates are set to 0.01.

The performance of the proposed approach is analyzed in terms of regret,
network capacity, and energy efficiency.

###  IV-B Simulation Results

Figure 3: Regret incurred by the contextual bandit model during training.

To analyze regret, the DCB in a single SAP is trained in two scenarios where
the number of PAPs is set to 4 and 5, respectively. Fig. 3 presents the regret
incurred by the DCB agent over the training episodes. Due to higher number of
neighbor in the 5 PAP case, the DCB model has access to more information
compared to the 4 PAP case. Therefore, the DCB model in the 5 PAP case could
learn faster and better compared to the 4 PAP case and results in a regret
measure around 4%.

In Fig. 4, a scenario capturing system performance under changing user
throughput demand is investigated. Fig. 4(a) and 4(b) present network capacity
and energy efficiency, respectively. Here the user requests for additional
throughput at $t=10$ ms. The user is served by 5 and 6 APs to meet the
throughput demand before and after the $t=10$ ms mark, respectively. The
performance of the proposed approach is compared with several IA schemes:
sleep-state enabled conventional 5G IA, always-on approach, and ideal genie-
aided system.

The ideal system knows the future demand and maintains the network capacity
accordingly. The always-on approach keeps all APs only in the awake-state.
Although always-on is robust against sudden changes in the user throughput
demand, it has the least overall energy efficiency. The user may need
throughput at any point in the 10 ms long radio frame[17]. Assuming only one
beam-sweeping slot is available per radio frame, the user experiences a
latency of 5 ms on average to get additional throughput from the newly
restored AP using 5G IA. With a trained DCB model, the proposed approach
enables the newly restored AP to performs IA instantaneously to start
providing throughput with negligible processing delay. The proposed approach
and the 5G IA both have similar power consumption profiles since they both
turn on the SAP at the same time. Nevertheless, overall energy efficiency is
higher in the proposed system compared to 5G IA since the proposed system
enables the AP to contribute to the network instantaneously. Although the
analyzed case only has 5 PAPs and an SAP, the proposed method can be easily
extended to other configurations.

(a) Network capacity.

(b) Energy efficiency.

Figure 4: Performance of proposed method, conventional sleep-state enabled
algorithm, always-on approach, and ideal genie-aided system under dynamic user
throughput demand. Markers in these figures are used merely to differentiate
between the plots, and hence, do not represent specific simulation points.

##  V Conclusion

In this paper, we have proposed a neighbor-aided approach based on DCB to
provide instantaneous IA to APs waking up from a sleep mode. First, we have
defined the function which maps beam choices made by the neighbors of an AP to
its beam codebook. Then, we have used a deep learning-based contextual bandit
approach to solve the IA mapping problem. Finally, we have carried out
simulations using realistic channels generated using the Wireless Insight
raytracing tool. The results show that the DCB model can successfully learn
the mapping function and provide instantaneous IA. This work, therefore,
presents a faster way to provide IA using neighbor information for APs in
dense mmWave-based UC networks.

## References

  * [1] Qualcomm, “The 1000x Mobile Data Challenge,” _White paper_ , no. November, pp. 1–38, 2013. [Online]. Available: https://www.qualcomm.com/media/documents/files/1000x-mobile-data-challenge.pdf
  * [2] I. K. Jain, R. Kumar, and S. S. Panwar, “The Impact of Mobile Blockers on Millimeter Wave Cellular Systems,” _IEEE Journal on Selected Areas in Communications_ , vol. 37, no. 4, pp. 854–868, 2019.
  * [3] S. Buzzi and C. D’Andrea, “Cell-free massive MIMO: User-centric approach,” _IEEE Wireless Communications Letters_ , vol. 6, no. 6, pp. 706–709, 2017\.
  * [4] T. Van Chien, E. Bjornson, and E. G. Larsson, “Joint power allocation and load balancing optimization for energy-efficient cell-free massive mimo networks,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 10, pp. 6798–6812, 2020.
  * [5] L. D. Nguyen, T. Q. Duong, H. Q. Ngo, and K. Tourki, “Energy Efficiency in Cell-Free Massive MIMO with Zero-Forcing Precoding Design,” _IEEE Communications Letters_ , vol. 21, no. 8, pp. 1871–1874, 2017.
  * [6] M. Feng, S. Mao, and T. Jiang, “BOOST: Base station on-off switching strategy for green massive MIMO HetNets,” _IEEE Transactions on Wireless Communications_ , vol. 16, no. 11, pp. 7319–7332, 2017.
  * [7] T. S. G. RAN, “3GPP TR 38.912 (2020-07): Study on New Radio (NR) access technology-Rel.16,” 3GPP, Tech. Rep., 2020.
  * [8] S. Ali, W. Saad, and N. Rajatheva, “6G White Paper on Machine Learning in Wireless Communication Networks,” _University of Oulu_ , 2020. [Online]. Available: http://arxiv.org/abs/2004.13875
  * [9] I. Ismath, K. B. S. Manosha, S. Ali, N. Rajatheva, and M. Latva-aho, “Deep Contextual Bandits for Fast Initial Access in mmWave Based User-Centric Ultra-Dense Networks,” in _IEEE Vehicular Technology Conference_ , 2021\. [Online]. Available: https://arxiv.org/abs/2009.06974
  * [10] M. R. Akdeniz, Y. Liu, M. K. Samimi, S. Sun, S. Rangan, T. S. Rappaport, and E. Erkip, “Millimeter wave channel modeling and cellular capacity evaluation,” _IEEE Journal on Selected Areas in Communications_ , vol. 32, no. 6, pp. 1164–1179, 2014.
  * [11] REMCOM, “Wireless insite reference manual,” 2008.
  * [12] M. Alrabeiah and A. Alkhateeb, “Deep Learning for mmWave Beam and Blockage Prediction Using Sub-6 GHz Channels,” _IEEE Transactions on Communications_ , vol. 68, no. 9, pp. 5504–5518, 2020.
  * [13] S. Ali, H. Asgharimoghaddam, N. Rajatheva, W. Saad, and J. Haapola, “Contextual bandit learning for machine type communications in the null space of multi-antenna systems,” _IEEE Transactions on Communications_ , vol. 68, no. 2, pp. 1284–1296, 2020.
  * [14] W. R. THOMPSON, “On the likelihood that one unknown probability exceeds another in view of the evidence of two samples,” _Biometrika_ , vol. 25, no. 3-4, pp. 285–294, dec 1933. [Online]. Available: https://academic.oup.com/biomet/article-lookup/doi/10.1093/biomet/25.3-4.285
  * [15] V. Mnih _et al._ , “Human-level control through deep reinforcement learning,” _Nature_ , vol. 518, no. 7540, pp. 529–533, feb 2015.
  * [16] A. Goldsmith, _Wireless Communications_. Cambridge University Press, 2005.
  * [17] T. S. G. RAN, “3GPP TS 38.213 (2020-12): NR Physical layer procedures for control,” 3GPP, Tech. Rep., 2020.