[affiliation=1]JonathanSvirsky [affiliation=1]UriShaham
[affiliation=1]OfirLindenbaum

# Sparse Binarization for Fast Keyword Spotting

###### Abstract

With the increasing prevalence of voice-activated devices and applications,
keyword spotting (KWS) models enable users to interact with technology hands-
free, enhancing convenience and accessibility in various contexts. Deploying
KWS models on edge devices, such as smartphones and embedded systems, offers
significant benefits for real-time applications, privacy, and bandwidth
efficiency. However, these devices often possess limited computational power
and memory. This necessitates optimizing neural network models for efficiency
without significantly compromising their accuracy. To address these
challenges, we propose a novel keyword-spotting model based on sparse input
representation followed by a linear classifier. The model is four times faster
than the previous state-of-the-art edge device-compatible model with better
accuracy. We show that our method is also more robust in noisy environments
while being fast. Our code is available at: https://github.com/jsvir/sparknet.

###### keywords:

keyword spotting, low-resource model, sparse learning

##  1 Introduction

Keyword spotting (KWS), also known as wake word detection, plays a crucial
role in enabling voice-activated applications on micro-controllers and edge
devices. These compact models are designed to continuously listen for specific
trigger words or phrases like "Hey Siri," "Okay Google," or custom commands in
constrained environments. Given the limited computational resources, memory,
and power available on such devices, KWS models are optimized for efficiency
and low latency without compromising accuracy. Edge devices are designed to be
always operational, constantly listening for specific trigger phrases. Upon
detecting these wake-up words, the system can activate a more sophisticated
speech recognition model, either locally on the device or remotely in the
cloud. This workflow, inherent to edge computing, offers several advantages,
including reduced power consumption, minimized bandwidth usage, enhanced
privacy, improved reliability, cost efficiency, and decreased response times
[1].

The optimization of KWS models involves leveraging lightweight neural network
architectures, such as small-footprint Convolutional Neural Networks (CNNs) or
Recurrent Neural Networks (RNNs), and techniques like quantization and pruning
to reduce model size and computational demands. To be able to run KWS models
on microprocessors, e.g., STM32, two main requirements should be fulfilled.
The first one is the limited memory footprint: the random-access memory (RAM)
is used to store input/output, weights, and activation data while running. The
size of on-chip RAM (SRAM) varies from 20 KB to 512 KB. The second one is the
limited computing speed: the number of operations per second is limited. The
CPU (Cortex-M) frequency is typically between 72 MHz and 216 MHz. These
hardware constraints limit the neural network models in two ways: the
parameter count and the number of operations. To address overcome this
limitation, small-footprint deep neural networks were proposed, e.g., [2, 3,
4, 5, 6, 7].

In this work, we leverage the sparse binarized representation learning for the
KWS model. We design a fast neural network, SparkNet, that yields accurate
results that are on par with those produced by state-of-the-art (SOTA) small
models but with much fewer multiplications. While these models utilize the
two-dimensional convolutions [3] or attention blocks [5] to achieve accurate
predictions, we get SOTA results with reduced computation burn by learning
binary sparse representation based on one-dimensional convolutions.
Intuitively, we propose to learn a dynamic binarization model that discards
the non-informative features in the signal and preserves those that are
helpful for prediction. Inspired by the recently proposed SG-VAD model [8] for
voice activity detection task, we learn a sample-wise binary representation
with a tiny neural network. However, instead of jointly training the auxiliary
classifier that is fed with the binary representation multiplied by input
samples, our classifier is a single linear projection layer onto the target
space and is fed by the predicted binary representation. Learning such a
binarization of the data could be viewed as a hard compression of the input
signal into a sparse representation with limited values in the $[0,1]$ range.
In addition, we test the model robustness at different SNR scenarios, analyze
its performance with a further decrease in the number of parameters, and
provide an ablation study on model components. In the following sections, we
present the model in detail and the experimental results for applying the
method to the commonly used KWS benchmarks.

Figure 1: The proposed SparkNet model learns a binary representation $z$ by
using reparameterization trick. The random noise is added to the predicted
${\mbox{\boldmath$\mu$}}\in[-1,1]^{F\times T}$ and approximate binary $z$ is
obtained by centering the values on $0.5$ and clipping n the interval $[0,1]$.
Only most informative features for classification task get positive values in
$z$.

##  2 Proposed Method

###  2.1 Method Overview

In a recent study [8], the authors introduced a network that uses binary
masking to reduce noise in an input signal for a classification task. They
also demonstrated that the network's learned gates can detect voice activity.
Inspired by this idea, we developed a model that learns to binarize the input
time-frequency representation to enable efficient and accurate Keyword
Spotting (KWS). The model is optimized to predict local gates that depend on
the input samples. These gates open for informative features in the input
representation space and close for noisy or irrelevant features. Surprisingly,
the binary gates are sufficient for predicting keywords with high accuracy,
even with a single linear classification layer.

The proposed model utilizes a small neural network as an input binarizer that
comes equipped with a single linear projection layer. This layer allows the
network to project the binarized representation into the target categories
space. Unlike other dynamic sparsification methods such as [9] and [8], our
model predicts the target without the need for element-wise multiplication of
input samples and gates during training. Instead, it relies on the learned
approximate binary representation. This reduces the computational complexity
while preserving accuracy.

The local binarizing module predicts binary
${\mbox{\boldmath$z$}}={\mbox{\boldmath$z$}}({\mbox{\boldmath$x$}})$ of the
same size as its input $x$ while the linear classifier predicts $\hat{y}$
based on average pooling of predicted $z$ in the time dimension. The model's
design is based on the results we present in the ablation study, where we
found that $z$ themselves conditioned on the input samples $x$ are sufficient
for the classifier to produce accurate results. This observation is consistent
with the inference architecture of the SG-VAD model, where only the binary
mask serves as a classifier for the speech detection task.

###  2.2 SparkNet Architecture

The architecture of our model, SparkNet, is presented in Table 1. The main
building block of the model is a time channel separable convolution [10], an
implementation of the depth-wise separable convolutions. One-dimensional (1D)
time channel separable convolutions can be separated into two layers. The
first layer is a 1D depth-wise convolutional layer with a kernel length of
$K$. This layer operates on each channel individually across $K$ time frames.
The second layer is a point-wise convolutional layer that operates on each
time frame independently but across all channels. By using these two layers,
the model can process data in time-frequency format ($T\times F$). This
completely separates the time and channel-wise parts of the convolution.

The model includes 4 blocks with a 1D time-channel separable convolution layer
followed by batch normalization and rectified non-linearity. The last three
blocks also include the residual connections. To increase the model effective
size of receptive fields, the convolutions are equipped with kernels of widths
$K\in\\{11,15,19,29\\}$. In addition to the first 4 blocks, a 1$\times$1
convolution layer is used as an output layer, followed by batch normalization
and tanh activation.

The proposed model accepts an input sample constructed from Mel-frequency
cepstral coefficients (MFCC) features matrix
${\mbox{\boldmath$x$}}_{i}\in\mathbb{R}^{F\times T}$, where $F$ is the number
of frequency bins, and $T$ is the number of overlapping time frames. The
output linear layer projects the averaged representations across time to 12
keyword categories, where 10 are target words, one is an "unknown" category,
and one is a "silence" category.

###  2.3 Sparse Binarized Representation Learning

The convolutional neural network backbone learns a representation
${\mbox{\boldmath$\mu$}}_{i}\in[-1,1]^{F\times T}$ which is then converted to
the approximate Bernoulli variables ${\mbox{\boldmath$z$}}_{i}$, or binarized
version of $x$. To achieve that, we utilize a Gaussian-based relaxation of
Bernoulli variables [11]. The relaxation relies on the reparameterization
trick [12, 13] and was demonstrated effective in several applications [14, 15,
16]. During the training, the conversion is done by adding random noise matrix
${\mbox{\boldmath$\epsilon$}}_{i}^{F\times T}$ to the shifted
${\mbox{\boldmath$x$}}_{i}$ and clipping the values by range $[0,1]$:

${\mbox{\boldmath$z$}}_{i}=\max(0,\min(1,0.5+{\mbox{\boldmath$\mu$}}_{i}+{\mbox{\boldmath$\epsilon$}}_{i})),$
(1)

where each value in the matrix ${\mbox{\boldmath$\epsilon$}}_{i}$ is drawn
from $\mathcal{N}(0,\sigma^{2})$ and $\sigma=0.5$ is fixed throughout
training. To encourage the model to produce sparse ${\mbox{\boldmath$z$}}_{i}$
matrix, it is trained with the regularization loss term
$\mathcal{L}_{\text{sparse}}({\mbox{\boldmath$z$}}_{i})=||{\mbox{\boldmath$z$}}_{i}||_{0}$.
The loss term is approximated using a double sum in terms of the Gaussian
error function ($\operatorname{erf}$) on values of
${\mbox{\boldmath$\mu$}}_{i}$:

${\cal{L}}_{\text{sparse}}({\mbox{\boldmath$\mu$}}_{i})=\frac{1}{F\times
T}\sum^{F}_{f=1}\sum^{T}_{t=1}\left(\frac{1}{2}-\frac{1}{2}\operatorname{erf}\left(-\frac{\mu_{f,t}+0.5}{\sqrt{2}\sigma}\right)\right).$

When using the $\cal{L}_{\text{sparse}}$ term, the model tries to sparsify
time-frequency bins that are associated with nuisance input features. This
helps to simplify the data and make the model more efficient. Additionally,
the classification layer propagates gradients to the binarization module for
features that are necessary to accurately predict the targets.

Table 1: SparkNet layers with input shape of frequency$\times$time, ($F\times
T$), the number of output channels $c$, stride $s$ and dilation $d$. The model
consists of 4 blocks with time-channel separable (TCS) convolutions followed
by batch normalization and ReLU activation, and an additional 1$\times$1
convolution with batch normalization, tanh activation, and output linear
layer. For the base model, we use $C=16$.

Input | Layer | c | s | d | residual
---|---|---|---|---|---
F$\times$T | Conv1D TCS (K=11)-BN-ReLU | C | 1 | 1 | $\times$
C$\times$T | Conv1D TCS (K=15)-BN-ReLU | C | 1 | 1 | v
C$\times$T | Conv1D TCS (K=19)-BN-ReLU | C | 1 | 1 | v
C$\times$T | Conv1D TCS (K=29)-BN-ReLU | C | 1 | 1 | v
C$\times$T | Conv1D (K=1)-BN-Tanh | F | 1 | 1 | $\times$
F$\times$T | avgpool | F | - | - | -
F$\times$1 | Linear | 12 | - | - | -

###  2.4 Classification Learning

We propose to train a linear classifier based on the sparse binary
representation learned by a neural network. We apply average pooling in the
time dimension and project the obtained representation vector onto the target
space by a single linear layer. The binarizer learns class-wise patterns in
the original $F\times T$ dimension that correlate with target labels.
Additionally, in our ablation study presented in Sec. 3.3, we found that the
auxiliary classifier or decoder training on binary mask multiplied by the
original input sample is redundant in the KWS task.

$\mathcal{L}=\mathcal{L}_{\text{sparse}}({\mbox{\boldmath$z$}})+\lambda\mathcal{L}_{\text{ce}}(\hat{{\mbox{\boldmath$y$}}},{\mbox{\boldmath$y$}})$
(2)

To conclude, we train the model to minimize the loss in eq. (2) where
$\mathcal{L}_{\text{ce}}(\hat{{\mbox{\boldmath$y$}}},{\mbox{\boldmath$y$}})$
is the cross-entropy loss between the model prediction
$\hat{{\mbox{\boldmath$y$}}}$ and target $y$. By learning the binary
representation as a basis for the linear prediction layer, the model can be
more robust to noisy environments because it focuses on the indicative time-
frequency regions in MFCC representation. Table 2 shows that our model is more
robust than the recently proposed BC-Resnet state-of-the-art model at
different signal-to-noise ratios (SNRs), and we attribute this improvement to
the sparse binarized representation learning. Additionally, in section 3.2, we
demonstrate that while being as accurate or slightly better, our model is much
faster in terms of multiply-accumulate operations (MACs). This makes it more
suitable to be run on very low resource edge devices.

##  3 Experiments

###  3.1 Experimental Setup

Datasets We evaluate our method on Google Speech Commands versions 1 (SC1) and
2 (SC2) datasets [17]. Version 1 contains 64,727 utterances from 1,881
speakers for 30 word categories and version 2 has 105,829 utterances from
2,618 speakers for 35 words. Each utterance is 1 sec long, and the sampling
rate is 16 $kHz$. We divide the both datasets into training, validation and
testing set based on the validation and testing file lists [17]. The datasets
are pre-processed following [3, 4, 17] for the keyword spotting task where
only 10 words are interesting targets, specifically: “Yes”, “No”, “Up”,
“Down”, “Left”, “Right”, “On”, “Off”, “Stop”, and “Go with two additional
classes "Unknown" (words from remaining twenty categories our of 35) and
"Silence" (silence or background noise). We follow the common settings of [3,
17] and re-balance the “Unknown Word” and “Silence” with the average number of
utterances in the remaining ten classes. The audio segments are processed by
extracting Mel-frequency cepstral coefficients (MFCC) features with $F=32$
bins.

Evaluation We use the top-1 accuracy metric to evaluate the model efficacy and
we compute multiply accumulate operations (MACs) to evaluate the efficiency of
the method111Calculated by https://github.com/Lyken17/pytorch-OpCounter/ .

Robustness to noise We evaluate the model's robustness to noisy environments.
For that goal we train the model on the SC2 train set without background noise
augmentation and prepare a noisy version of the SC2 test set by adding random
background noise to the original clean test set obtained from Freesound [18]
and consists of 35 categories of noises, in total about 2,100 variable-length
audio segments, such as ”motorcycle,” ”Bus,” and ”Static”. For each sample in
the test set, we randomly pick noise and add it with SNR value in [0, 5, 10,
15, 20] decibels. We repeat this process 10 times with different random seeds.
We use the same noisy test set to evaluate the BC-Resnet-0.625 trained on the
same data as our model.

Training Setup The input was augmented with time shift perturbations in the
range of T = $[-100;100]$ $ms$ and white noise of magnitude $[-90;-46]$ $dB$
with a probability of $80\%$. In addition, we add random background noise for
SparkNet[$C=32$] with a probability of $80\%$. The model was trained with the
SGD optimizer with momentum = $0.9$ and weight decay = $1e-3$. We utilized the
Warmup-Hold-Decay learning rate schedule [19] with a warm-up ratio of 5%, a
hold ratio of 40%, and a polynomial (2nd order) decay for the remaining 85% of
the schedule. A maximum learning rate of $1e-2$ and a minimum learning rate of
$1e-6$ were used. We trained all models for 200 epochs on a single NVIDIA
GeForce GTX 1080 Ti with a batch size of 128. We use the fixed value for
$\lambda=1e+2$ for all experiments. The implementation of our model is based
on the NeMo toolkit [20].

Table 2: We compare our model against BC-Resnet for robustness to noisy
environments while being $\sim\times 4$ faster. The noisy tests are generated
at different SNRs and present the mean accuracy on each test and standard
deviation on 10 test variants for each SNR.

Model / SNR | 0 db | 5 db | 10 db | 15 db | 20 db | clean
---|---|---|---|---|---|---
BC-ResNet-0.625 | 75.72 $\pm$ 2.73 | 84.47 $\pm$ 1.82 | 90.68 $\pm$ 1.35 | 92.67 $\pm$ 0.45 | 94.18 $\pm$ 0.20 | 95.40 $\pm$ 0.31
[HTML]DDDDDD SparkNet[$C=16$] | 75.98 $\pm$ 2.66 | 85.05 $\pm$ 1.76 | 91.37 $\pm$ 1.16 | 93.58 $\pm$ 0.33 | 94.63 $\pm$ 0.30 | 95.70 $\pm$ 0.17

(a) (b)

Figure 2:  5 randomly chosen words from 5 categories in MFCC representation
(a) and the predicted binary representation (b).

###  3.2 Results

In the first experiment, we compare two versions of our model with the SOTA
low-resource BC-ResNet and other recently proposed methods. For this
comparison, we train two version of our model, the first one with number of
channels $C=16$ and in total $\sim 4.6K$ parameters and the second one with
$C=32$ and $\sim 11K$ parameters. The former one is compared against BC-
Resnet-0.625 which is a reduced version of BC-Resnet-1 following the
definition in [3]. The second small model is TinySpeech-Z [5] which has no
public implementation and the results are borrowed from the published paper.
For the second, extended version of SparkNet we present the results of BC-
ResNet-1, DS-Resnet [6], res8-narrow [4] and TinySpeech-X [5]. All models have
up to $20K$ parameters. The accuracy and measured MAC results are provided in
Table 3. The base version of the proposed model with $C=16$ is $\times$4
faster than the corresponding BC-ResNet variant while producing a slightly
improved accuracy. Our model with $C=32$ is $\times 3$ faster than BC-ResNet-1
and $\times 5$ \- than DS-ResNet10. Additionally, the base version
SparkNet[$C=16$] is more accurate than corresponding BC-ResNet version and
$\times 4$ faster than it in terms of MACs.

In the second experiment we test our model and BC-ResNet with $\sim 4.6K$
parameters on noisy test set where noises are added with varying SNRs. The
mean and std accuracy results over 10 versions for each SNR are presented in
the Table 2. It could be seen that our model is more robust to the noise than
BC-ResNet.

Finally, we challenge our model by reducing its size further by reducing the
number of output filters down to $C=4$ in the intermediate layers. We train
all versions on both SC1 and SC2 and test on the official test sets. The
accuracy results are provided in Table 4. The tiny version of the model with
only $\sim 1.4K$ parameters and $105K$ MACs is able to produce a mean accuracy
of $~{}83\%$.

Table 3: Comparison of different methods trained on Google Speech Commands v2
dataset and tested on the official test set of keyword spotting task with 12
targets. While being with the same accuracy and number parameters our model
has $\times$4 less multiply-accumulate operations (MACs)

|  |  | Accuracy
---|---|---|---
Model | Params | MACs | SC1 | SC2
TinySpeech-X [5] | 10.8K | 10.9M | 94.6 $\pm$ 0.00 | -
res8-narrow [4] | 19.9K | 5.65M | 90.1 $\pm$ 0.98 | -
DS-ResNet10 [6] | 10K | 5.8M | 95.2 $\pm$ 0.36 | -
BC-ResNet-1 [3] | 9,232 | 3.6M |  96.6 $\pm$ 0.21 | 96.9 $\pm$ 0.30
[HTML]DDDDDD SparkNet[$C=32$] | 11,500 | 1.2M | 96.2 $\pm$ 0.19 |  97.0 $\pm$ 0.18
TinySpeech-Z [5] | 2.7K | 2.6M | 92.4 $\pm$ 0.00 | -
BC-ResNet-0.625 [3] | 4,585 | 1.9M | 95.2 $\pm$ 0.37 | 95.4 $\pm$ 0.31
[HTML]DDDDDD SparkNet[$C=16$] | 4,636 | 454.5K |  95.3 $\pm$ 0.33 |  95.7 $\pm$ 0.17

Table 4: The accuracy of the proposed model as a function of number of
parameters. The smallest model is still able to produce $\sim 83\%$ accuracy
by using only 1.4K parameters and $105K$ MACs.

|  |  | Accuracy
---|---|---|---
Model Version | Params | MACs | SC1 | SC2
SparkNet[$C=32$] | 11,500 | 1.2M | 96.2 $\pm$ 0.19 | 97.1 $\pm$ 0.30
SparkNet[$C=16$] | 4,636 | 454.5K | 95.3 $\pm$ 0.33 | 95.7 $\pm$ 0.30
SparkNet[$C=8$] | 2,292 | 190K | 91.6 $\pm$ 0.76 | 92.1 $\pm$ 0.33
SparkNet[$C=4$] | 1,416 | 105K | 82.3 $\pm$ 1.91 | 83.5 $\pm$ 0.60

###  3.3 Ablation Study

To verify the essence of different parts of the proposed model we run
experiments on the modified version of SparkNet on SC2 dataset. For all
experiments we use SparkNet[$C=16$]. In the first experiment we check how an
auxiliary larger classifier influences the training of the main model
similarly to the SG-VAD model. We train SparkNet together with
MatchboxNet-4x1x64 [2] which is fed by
${\mbox{\boldmath$x$}}\odot{\mbox{\boldmath$z$}}$ and predicts target labels
as our main model. In this case, the loss becomes:
$\mathcal{L}=\mathcal{L}_{\text{sparse}}({\mbox{\boldmath$z$}})+\lambda\mathcal{L}_{\text{ce}}(\hat{{\mbox{\boldmath$y$}}},{\mbox{\boldmath$y$}})+\mathcal{L}_{\text{ce}}^{\text{aux}}(\hat{{\mbox{\boldmath$y$}}}_{\text{aux}},{\mbox{\boldmath$y$}})$
where $\hat{{\mbox{\boldmath$y$}}}_{\text{aux}}$ are the prediction labels of
MatchboxNet-4x1x64. Then we train our model without Bernoulli approximation by
removing random noise adding to network output $\mu$, clipping and loss term
$\mathcal{L}_{\text{sparse}}$. The model becomes a reduced version of
MatchboxNet with less parameters. We also try to integrate a decoder auxiliary
model that accepts ${\mbox{\boldmath$x$}}\odot{\mbox{\boldmath$z$}}$ which is
trained for reconstruction task. The intuition, is that we would like to close
the gates of correlating features and preserve the sufficient input signal for
reconstruction task. So we add
$\mathcal{L}_{\text{recon}}(\hat{{\mbox{\boldmath$x$}}},{\mbox{\boldmath$x$}})$
to the loss equation 2 where $\hat{{\mbox{\boldmath$x$}}}$ is the output from
the decoder.

Table 5: Ablation study. Adding auxiliary classifier or decoder doesn't
improve the model's accuracy. In addition, learning the binarized
representation by Bernoulli approximation contributes to the model's
performance.

Model Version | Accuracy
---|---
SparkNet |  95.7 $\pm$ 0.17
SparkNet $+$ $\mathcal{L}_{\text{ce}}^{\text{aux}}(\hat{{\mbox{\boldmath$y$}}}_{\text{aux}},{\mbox{\boldmath$y$}})$ | 95.6 $\pm$ 0.26
SparkNet $+$ $\mathcal{L}_{\text{recon}}(\hat{{\mbox{\boldmath$x$}}},{\mbox{\boldmath$x$}})$ | 95.5 $\pm$ 0.32
SparkNet w/o $\mathcal{L}_{\text{sparse}}$ | 94.7 $\pm$ 0.13

###  3.4 Binarized Representation Qualitative Analysis

We present in Figure 2 the binarized samples for 5 samples from 5 word
categories (up, right, no, stop, go, left). We extract MFCC features for each
sample and add an additional layer of open gates (with value 1). As it could
be seen, the model learns to localize the informative features and predicts
sample-specific binary patterns.

##  4 Conclusions

We proposed a fast neural network for the KWS task with increased noise
robustness. It's trained easily and makes accurate predictions while having a
few number of parameters and an increased inference speed in terms of multiply
accumulate operations. Our method is evaluated on two commonly used benchmarks
for the KWS task and found to slightly outperform the previous SOTA small
model in terms of accuracy measurements while being $\times 4$ faster in terms
of MACs. We presented the improved robustness of the model to the noisy
environments compared to the opponent model by testing the trained model at
different SNRs. While our method is proposed for supervised KWS task, an
interesting future extension for the model could be in self-supervised
learning tasks where random masks as proposed in [21] are replaced by the
learnable binary mask model.

## References

  * [1] Y. Abadade, A. Temouden, H. Bamoumen, N. Benamar, Y. Chtouki, and A. S. Hafid, ``A comprehensive survey on tinyml,'' _IEEE Access_ , 2023.
  * [2] S. Majumdar and B. Ginsburg, ``Matchboxnet: 1d time-channel separable convolutional neural network architecture for speech commands recognition,'' 2020.
  * [3] B. Kim, S. Chang, J. Lee, and D. Sung, ``Broadcasted Residual Learning for Efficient Keyword Spotting,'' in _Proc. Interspeech 2021_ , 2021, pp. 4538–4542.
  * [4] R. Tang and J. Lin, ``Deep residual learning for small-footprint keyword spotting,'' in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 5484–5488.
  * [5] A. Wong, M. Famouri, M. Pavlova, and S. Surana, ``Tinyspeech: Attention condensers for deep speech recognition neural networks on edge devices,'' _arXiv preprint arXiv:2008.04245_ , 2020.
  * [6] M. Xu and X.-L. Zhang, ``Depthwise separable convolutional resnet with squeeze-and-excitation blocks for small-footprint keyword spotting,'' 2020.
  * [7] A. Rozner, B. Battash, O. Lindenbaum, and L. Wolf, ``Efficient verification-based face identification,'' _arXiv preprint arXiv:2312.13240_ , 2023.
  * [8] J. Svirsky and O. Lindenbaum, ``Sg-vad: Stochastic gates based speech activity detection,'' in _ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2023, pp. 1–5.
  * [9] J. Yang, O. Lindenbaum, and Y. Kluger, ``Locally sparse neural networks for tabular biomedical data,'' in _International Conference on Machine Learning_. PMLR, 2022, pp. 25 123–25 153.
  * [10] S. Kriman, S. Beliaev, B. Ginsburg, J. Huang, O. Kuchaiev, V. Lavrukhin, R. Leary, J. Li, and Y. Zhang, ``Quartznet: Deep automatic speech recognition with 1d time-channel separable convolutions,'' in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 6124–6128.
  * [11] Y. Yamada, O. Lindenbaum, S. Negahban, and Y. Kluger, ``Feature selection using stochastic gates,'' in _International Conference on Machine Learning_. PMLR, 2020, pp. 10 648–10 659.
  * [12] A. Miller, N. Foti, A. D'Amour, and R. P. Adams, ``Reducing reparameterization gradient variance,'' _Advances in Neural Information Processing Systems_ , vol. 30, 2017.
  * [13] M. Figurnov, S. Mohamed, and A. Mnih, ``Implicit reparameterization gradients,'' _Advances in neural information processing systems_ , vol. 31, 2018.
  * [14] S. Jana, H. Li, Y. Yamada, and O. Lindenbaum, ``Support recovery with projected stochastic gates: Theory and application for linear models,'' _Signal Processing_ , vol. 213, p. 109193, 2023.
  * [15] J. Svirsky and O. Lindenbaum, ``Interpretable deep clustering,'' _International Conference on Machine Learning_ , 2024.
  * [16] O. Lindenbaum, M. Salhov, A. Averbuch, and Y. Kluger, ``L0-sparse canonical correlation analysis,'' in _International Conference on Learning Representations_ , 2021.
  * [17] P. Warden, ``Speech commands: A dataset for limited-vocabulary speech recognition,'' _arXiv preprint arXiv:1804.03209_ , 2018.
  * [18] F. Font, G. Roma, and X. Serra, ``Freesound technical demo,'' in _Proceedings of the 21st ACM international conference on Multimedia_ , 2013, pp. 411–412.
  * [19] T. He, Z. Zhang, H. Zhang, Z. Zhang, J. Xie, and M. Li, ``Bag of tricks for image classification with convolutional neural networks,'' in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 558–567.
  * [20] O. Kuchaiev, J. Li, H. Nguyen, O. Hrinchuk, R. Leary, B. Ginsburg, S. Kriman, S. Beliaev, V. Lavrukhin, J. Cook _et al._ , ``Nemo: a toolkit for building ai applications using neural modules,'' _arXiv preprint arXiv:1909.09577_ , 2019.
  * [21] P.-Y. Huang, H. Xu, J. Li, A. Baevski, M. Auli, W. Galuba, F. Metze, and C. Feichtenhofer, ``Masked autoencoders that listen,'' _arXiv preprint arXiv:2207.06405_ , 2022.


# Assessing the dynamic vulnerability of an urban rail transit system and a
case study of Beijing, China

Shouzheng Pan  Jia He  Ning Jia  Zhengbing He<EMAIL_ADDRESS>Beijing Key
Laboratory of Traffic Engineering, Beijing University of Technology, Beijing,
China  Institute of Systems Engineering, College of Management and Economics,
Tianjin University, Tianjin, China

###### Abstract

Urban rail transit is the backbone of urban transportation, and thus, it is
significant to understand its vulnerability, i.e., whether the system can
still maintain normal operations when facing operational disturbances of
different magnitudes. To this end, this paper proposes a network vulnerability
assessment method with the joint consideration of static network topology and
dynamic travel demand. The method includes an accessibility-based
identification of station importance with time-varying passenger demand and a
new dynamic vulnerability evaluation index. An empirical analysis was carried
out by taking the rail transit system of Beijing, China, as an example. The
results show that the distribution of high-importance stations varies with the
time of day, affected by both static topology and hourly changing passenger
flow. Under the disturbance of operation delay, the impact of high-importance
stations on the network vulnerability changes with the increase of delayed
travel demand. Some stations found to serve as bridges (i.e., reasonable paths
link the origin station and destination) and visited by large passenger flows
have the greatest impact on network vulnerability. Network performance
degradation is obviously segmented and stratified in the case of interval
continuous failure. The disruption between different lines is the main reason
for system performance degradation, and some important stations within the
line will act as catalysts to accelerate the performance degradation. This
method provides a reference for measuring dynamic passenger flow-related
network vulnerability and supplies the field with a new vulnerability
evaluation index.

###### keywords:

Subway , vulnerability , dynamic travel demand , critical stations ,
operational disturbances

††journal:

###### Contents

  1. 1 Introduction
  2. 2 Basic definitions and indices of URT network characteristics
    1. 2.1 URT network modeling
    2. 2.2 Flow changes with dynamic demand
    3. 2.3 Topological characteristics of a URT network with dynamic demand
  3. 3 Dynamic assessment of the vulnerability of a URT network
    1. 3.1 Accessibility-based dynamic identification of station importance
    2. 3.2 Vulnerability measurement of a URT network under disruptions
  4. 4 A case study of Beijing URT
    1. 4.1 Beijing URT and data description
    2. 4.2 Identification of the dynamic importance of stations
    3. 4.3 Network vulnerability under short-delay disruptions
    4. 4.4 Network vulnerability under long-delay disruptions
    5. 4.5 Regular verification
  5. 5 Discussion and conclusion

##  1 Introduction

Urban rail transit (URT) is one of the most important transportation systems
in a city, covering almost every corner in a city such as New York City,
Paris, London and Beijing. The safe and reliable operation of a URT system is
a guarantee for people’s traveling and social activities. However, a URT
system is occasionally impacted by external and internal disturbances, such as
extreme weather, large events, power and signal failures. The disturbances may
lead to train delays, station closure, or even the suspension of a whole line.
It is significant to understand the performance changes in a URT system under
disturbances, including the identification of key components, network
vulnerability, magnitude of the impact of the disturbance, etc.

Vulnerability is one of the most relevant concepts for describing system
performance under disturbances. The concept of vulnerability was first
introduced into the field of transportation in approximately 2000
(Abrahamsson, 1997), and a widely accepted definition is given as
susceptibility to unusual incidents that can result in considerable reductions
in system serviceability (Berdica, 2002). Early studies on URT vulnerability
focused mainly on static network topology. For example, Crucitti et al. (2003)
analyzed the characteristics of URT topology, including node degree,
betweenness, and global efficiency, and found that most URT networks show
small-world characteristics and have better connectivity reliability. However,
the distribution of travel demand in a city is well known to vary with the
time of day, resulting in a time-varying imbalance between transit supply and
travel demand. Therefore, the performance of a URT system is dynamic, making
the naïve analysis of static network topology insufficient to assess a URT
system with time-varying performance.

Until recently, passenger flow was introduced into the studies of the
vulnerability of a transportation network (Chen et al., 2012; Rodríguez-Núñez
and García-Palomares, 2014; Cats and Jenelius, 2014; Feng et al., 2017; Zhou
et al., 2019). For example, Feng et al. (2017) proposed a two-layer network
model to analyze the vulnerability of a URT network under the influence of
passenger flow. A weighted network was constructed based on topology structure
and passenger flow data, and network performance was evaluated using
vulnerability metrics. The results show that the flow network and train
network have similar spatiotemporal clustering characteristics and are both
affected by network topology. Ouyang et al. (2015) evaluated the vulnerability
of railway and airline systems by proposing a metric based on the number of
reachable stations within 24 hours after the occurrence of a disturbance. The
results show that components in a single system are equally important in a
comprehensive system. Lu (2018) established a resilience evaluation index for
daily operational incidents by considering both delayed origin-destination
(OD) volume and network topology. Hong et al. (2020) used daily changes in
accessibility indicators to calculate the vulnerability of integrated URT and
high-speed rail systems. The distribution of important stations under
different evaluation indices was found to be different. However, the metrics
or methods proposed in most of the existing studies are still relatively
static, i.e., network weights are measured using passenger flow that was
collected in a relatively large time period (e.g., a whole day). The
granularity is unable to accurately reflect time-varying travel demand within
a day (e.g., peak-and-off-peak patterns) as well as its impact on network
vulnerability. One of the obstacles might be the high computational efficiency
required by frequently updating the route and line passenger flow every short
time interval.

In addition, different disturbances usually have different impacts on network
vulnerability. It is necessary to distinguish disruption types and analyze
system performance in specific disturbance scenarios (Donovan and Work, 2017;
Ilbeigi, 2019; Diab and Shalaby, 2019). For a URT system, train delays that
may result from, e.g., natural disasters and operation accidents aggravate the
imbalance between demand and supply and degrade system performance. Lu (2018)
analyzed the impact of train delays on system performance under operational
incidents, showing that network resilience gradually decreases as train delay
increases and the robustness of transfer stations is better than the
robustness of nontransfer stations. The failure of stations or lines is
usually taken as a typical trigger of operational delay (Zhang and Wang,
2019). For example, Sun and Guan (2016) analyzed the vulnerability of a URT
network from the perspective of operational lines, instead of taking
traditional nodes or connecting edges as interference targets. The results
show that passenger flow is the key factor that causes network vulnerability,
and the failure of loop lines has the greatest impact on the performance of
the whole network. However, the failure of a whole line might rarely occur in
a modern URT system with advanced operation and management technologies. A
more practical scenario is the failure of multiple consecutive stations at the
same time, which is also known as interval failure. For example, a train rear-
end accident occurred in Shanghai Metro, China, due to equipment failure on
September 27, 2011. Only the nearest 9 stations along the entire line were
closed. To the best of our knowledge, few studies have focused on the impact
of interval failure in a URT system.

In summary, although travel demand obviously changes within a day and may have
a significant impact on network vulnerability during different time periods
(e.g., morning and noon), the existing literature pays less attention to it.
Moreover, the impact of the more realistic multiple consecutive station
failures in a URT system is still unclear. To fill these gaps, this paper
proposes a vulnerability assessment method to consider the impact of short-
delay and long-delay disruptions on system performance under time-varying
travel demand. The station and interval failures are explicitly tested by
taking the URT system in Beijing, China, as a case study. The main
contributions of this paper are as follows.

  * 1.

An accessibility-based identification method for station importance is
proposed by jointly considering static network topology and dynamic travel
demand. Instead of dynamic passenger flow assignment, it is calculated based
on merely passenger demand that has direct connections with the disrupted
stations, making it possible to assess network vulnerability in a real-time
manner.

  * 2.

A new dynamic vulnerability evaluation index is proposed to assess network
vulnerability changes under short-delay disruptions that result from small
disturbances such as train delay and signal failure.

  * 3.

The variation in network vulnerability under the scenarios of station and
interval failures is explicitly studied by taking the impact of operation
delay into account. To the best of our knowledge, this is the first work that
evaluates a URT network under the impact of interval failure.

The reminder of the paper is organized as follows. Section 2 introduces some
basic definitions and indices that will be used to describe URT network
characteristics. Section 3 proposes the accessibility-based identification
method for station importance and the new dynamic vulnerability evaluation
index under disruptions. By taking the URT system in Beijing, China as a case,
Section 4 demonstrates the results of the dynamic vulnerability analysis under
the scenarios of station, interval and line failures. Finally, a comprehensive
summary and discussion of future research are presented in section 5.

##  2 Basic definitions and indices of URT network characteristics

###  2.1 URT network modeling

A URT network can be abstracted as an undirected and weighted graph composed
of nodes and connecting edges. Specifically, let $\textbf{N}=\\{1,2,...,N\\}$
be a set of nodes (i.e., URT stations composed of transfer and nontransfer
stations) with size $N$ and $i\in\textbf{N}$ be a node. Let
$\textbf{E}=\left\\{e_{ij}|e_{ij}=\left\langle i,j\right\rangle,i\neq
j\right\\}$ be a set of edges between nodes $i$ and $j$. When station $i$
directly connects with station $j$, $e_{ij}=1$; otherwise, $e_{ij}=0$. Let
$\textbf{W}=\left\\{w_{ij}|w_{ij}\geq 0\right\\}$ be the weight of edge
$e_{ij}$, which can be the actual running time $\tau_{ij}$ of trains between
stations $i$ and $j$ or the passenger flow $f_{ij}$ at a given time.
Correspondingly,
$\textbf{G}=\left\\{\textbf{N},\textbf{E},\textbf{W}\right\\}$ is the graph.

###  2.2 Flow changes with dynamic demand

Strictly speaking, travel demand in a URT system is unevenly changing with
time, resulting in a time-varying spatiotemporal distribution of passenger
flow inside a URT system. Loading with such dynamic flow, a URT system that is
static in topology shows time-varying characteristics. To accurately capture
the characteristics, it is necessary to assign passenger flow into routes and
links, meaning that passenger choice of travel route inside a URT system must
be involved. Unfortunately, the smart card data collected by the most current
automatic fare collection (AFC) systems cannot reflect the detailed passenger
paths inside a URT system. To remedy this issue, we define a reasonable path
by jointly considering travel time, transfer time, and the number of transfer
stations. The detailed steps are as follows. (i) Take the train running time
as the travel time of passengers between stations. (ii) Construct a URT
topology with virtual transfer arcs according to the actual URT network.
Transfer time is assigned to the virtual arc as its weight. The number and the
weight sum of the transfer arcs along a trip are the transfer number and the
total transfer time that a passenger experiences, respectively. (iii)
Calculate the $K$ shortest path between any nodes by using the Dijkstra
algorithm. (iv) Finally, take the path with the minimum total travel time, the
smallest transfer number and the minimum transfer time as a reasonable path.
Note that if there are multiple reasonable paths between an OD pair, the paths
will be assigned in proportion to their respective travel time.

Definition 1. Among all the shortest paths of any OD pair in a fully connected
URT network, the path with the shortest travel time, the smallest transfer
number and the shortest total transfer time is a reasonable path and there is
at least one path.

The OD matrices within a time period, which are the reflection of dynamic flow
distributions, can be further obtained after possessing a reasonable path
between any stations. The characteristics of a URT system will be analyzed on
this basis.

###  2.3 Topological characteristics of a URT network with dynamic demand

Understanding the topological characteristics of a URT network is helpful to
identify high-importance stations and analyze network vulnerability. This
paper first introduces the following three indices that were proposed based on
complex network theory to describe the topological characteristics of a URT
network with the consideration of dynamic passenger flow.

Node degree weighted by passenger flow (also known as intensity) calculates
the passenger flow distribution of a network through passenger flow assignment
to reflect the local importance of a network under the influence of travel
demand. Let $D_{i}(t)$ denote the degree of station $i$ during time period
$t$, and the equation can be written as follows.

$D_{i}(t)=\sum_{j\in\textbf{N}_{i}}w_{ij}(t)$ (1)

where $w_{ij}(t)$ is the weighted flow from node $i$ to node $j$ during time
period $t$ and $\textbf{N}_{i}$ is the set of the nodes that directly connect
with node $i$.

Flow betweenness is defined as the ratio of the passenger flow passing through
station $i$ along a reasonable path to the total passenger flow at a given
time period $t$, reflecting the importance of a URT station in terms of being
a bridge in the whole network. Let $B_{i}(t)$ denote the betweenness during
time period $t$, and the equation can be written as follows.

$B_{i}(t)=\sum_{j=1}^{N}\sum_{k=1}^{N}\frac{f^{i}_{jk}(t)}{f_{jk}(t)},\ \ \
j\in\textbf{N},\ k\in\textbf{N},\ i\neq j\neq k$ (2)

where $f_{jk}(t)$ is the passenger flow between any two nodes $j$ and $k$ on a
reasonable path during time period $t$; $f^{i}_{jk}(t)$ is the passenger flow
passing through node $i$ along a reasonable path of two nodes $j$ and $k$
during time period $t$.

Demand closeness centrality, defined as the reciprocal of the ratio of the
inflow of station $i$ to the total number of stations during time period $t$,
reflects the closeness of the distance and travel demand between stations $i$
and $j$. Let $C_{i}(t)$ denote the centrality of station $i$ and the equation
can be written as follows.

$C_{i}(t)=\frac{N-1}{\sum_{j=1}^{N_{i}(t)}f_{ij}(t)}$ (3)

where $N_{i}(t)$ is the number of stations where passengers who take a URT
train from station $i$ during time period $t$ will arrive in the short future
of a URT train leaving station $i$; $f_{ij}(t)$ is the passenger flow between
stations $i$ and $j$; The larger $C_{i}(t)$ is, the smaller the closeness of
station $i$ is.

##  3 Dynamic assessment of the vulnerability of a URT network

###  3.1 Accessibility-based dynamic identification of station importance

Stations are one of the most basic and critical components for the
vulnerability of a URT network. The importance of a station is usually
affected by the topological structure of a network and the passenger flow in
the network. The existing indices that evaluate station importance from the
perspective of topological structure include node degree, betweenness
centrality and closeness centrality. To incorporate the impact of travel
demand, passenger flow is usually employed to weight the degree (Equation 1)
and betweenness (Equation 2). As mentioned above, most of the existing studies
only consider daily passenger flow, obviously ignoring the rapid changes in
passenger flow within a day. One of the reasons is that assigning fine-
granularity passenger flow to a network (in particular to a large-scale
network) usually creates a high requirement for computational efficiency,
which is a challenging task. More importantly, simply assigning the passenger
flow to the network only gives the edge section a flow attribute and cuts off
the contact of passenger flow between OD stations.

In this paper, we propose an accessibility-based station importance
identification method that does not require passenger flow assignment. In
detail, suppose that the operation of station $i$ is disturbed due to any
unexpected reason during time period $t$, and we have the following
accessibility-related variables.

  * 1.

Three groups of passengers that have direct connections with station $i$ will
be affected during time period $t$, namely, the passengers whose destination
is station $i$ (denoted by $S^{i}_{\text{out}}(t)$), the passengers whose
origin is station $i$ (denoted by $S^{i}_{\text{in}}(t)$), and the passengers
who have to pass station $i$ (denoted by $S^{i}_{\text{pass}}(t)$). The links
of the stations that contain station $i$ as an intermediate station are
predetermined using Definition 1, and there is no need to make real-time
updates. Therefore, $S^{i}_{\text{pass}}(t)$ is the number of passengers who
enter and leave the URT system from the two ends of the links of stations
during time period $t$.

  * 2.

Accordingly, three groups of stations will be affected, namely, the stations
used by $S^{i}_{\text{out}}(t)$, the stations used by $S^{i}_{\text{in}}(t)$,
and the stations used by $S^{i}_{\text{pass}}(t)$. The numbers of the three
groups of stations are denoted by $N^{i}_{\text{out}}(t)$,
$N^{i}_{\text{in}}(t)$ and $N^{i}_{\text{pass}}(t)$. Not all stations will be
used by passengers during time period $t$, particularly when $t$ is quite
short.

Generally, the influence of a station on a network, i.e., the importance of a
station for a network, is positively correlated with $S^{i}_{\text{out}}(t)$,
$S^{i}_{\text{in}}(t)$, $S^{i}_{\text{pass}}(t)$ and $N^{i}_{\text{out}}(t)$,
$N^{i}_{\text{in}}(t)$, $N^{i}_{\text{pass}}(t)$. Therefore, we propose the
following index to assess the importance of a station for a network, which not
only considers passengers who would access the disturbed station $i$ during
time period $t$ but also has no need for time-consuming passenger flow
assignment.

$\zeta_{i}(t)=\frac{S^{i}_{\text{out}}(t)N^{i}_{\text{out}}(t)+S^{i}_{\text{in}}(t)N^{i}_{\text{in}}(t)+S^{i}_{\text{pass}}(t)N^{i}_{\text{pass}}(t)}{S(t)N(t)}$
(4)

where the denominator normalizes the impact using the total passengers
(denoted by $S(t)$) that enter the URT system during time period $t$ and the
number (denoted by $N(t)$) of stations associated with the passengers. The
values of the input variables in Equation 4 can be directly and simply
obtained from the smart card data collected by the current AFC system,
guaranteeing high computational efficiency.

###  3.2 Vulnerability measurement of a URT network under disruptions

In terms of the resulting delay, the disruptions associated with a URT system
can be classified into two types: short-delay disruptions that result from
small disturbances such as train delay and signal failure (Lu, 2018) and long-
delay disruptions that result from large disturbances such as fire disaster,
heavy maintenance and flood (Sun and Guan, 2016). Passengers would choose to
wait and keep using the delayed route when a short-term disruption occurs. In
contrast, passengers may choose another travel mode for a replacement of URT
when a long-term disruption occurs, since the route affected by a long-term
disruption may not be recovered in a short time. Assume a disruption will
trigger a constant delay (denoted by $\tau_{\text{disr}}$), and we simply use
a threshold (denoted by $\tau_{\text{disr}}^{*}$) of the delay to distinguish
the short- and long-delay disruptions, i.e., a short-delay disruption occurs
when the delay $\tau_{\text{disr}}\leq\tau_{\text{disr}}^{*}$, and a long-term
disruption occurs when $\tau_{\text{disr}}>\tau_{\text{disr}}^{*}$.

To jointly incorporate the disruption delay and dynamic passenger flow, we
propose a new metric $\psi_{\text{short}}(\textbf{G},t,\tau_{\text{disr}})$ to
describe the vulnerability of a URT network under short-delay disruptions.

$\psi_{\text{short}}(\textbf{G},t,\tau_{\text{disr}})=\frac{\sum_{i=1}^{N}\sum_{j=1}^{N}\tau_{ij}(t,\tau_{\text{disr}})f_{ij}(t)}{N(N-1)},\
i\neq j,\ i\in\textbf{N},\ j\in\textbf{N},\
0<\tau_{\text{disr}}\leq\tau_{\text{disr}}^{*}$ (5)

where $\tau_{ij}(t)$ is the actual travel time between stations $i$ and $j$
during time period $t$ and is calculated as

$\tau_{ij}(t,\tau_{\text{disr}})=\tau_{ij}+\theta_{ij}(t)\tau_{\text{disr}}$
(6)

where $\tau_{ij}$ is the constant travel time between stations $i$ and $j$
under normal conditions; $\theta_{ij}(t)$ is a dummy variable, i.e.,
$\theta_{ij}(t)=1$, if the disruption with delay $\tau_{\text{disr}}$ occurs
during time period $t$ and is associated with stations $i$ or $j$;
$\theta_{ij}(t)=0$, otherwise.

To measure the vulnerability under long-delay disruptions, we first remove the
disturbance-influenced station and edges and reconstruct the network graph
$\textbf{G}^{\prime}=\\{\textbf{N}^{\prime},\textbf{E}^{\prime},\textbf{W}^{\prime}\\}$.
Then, we measure vulnerability by employing the following index (Sun and Guan,
2016).

$\psi_{\text{long}}(\textbf{G}^{\prime},t,\tau_{\text{disr}})=\frac{\sum_{i=1}^{N^{\prime}}\sum_{j=1}^{N^{\prime}}\frac{1}{\tau_{ij}^{\prime}}f_{ij}^{\prime}(t)}{N^{\prime}(N^{\prime}-1)},\
i\neq j,\ i\in\textbf{N}^{\prime},\ j\in\textbf{N}^{\prime},\
\tau_{\text{disr}}>\tau_{\text{disr}}^{*}$ (7)

where $N^{\prime}$ is the number of nodes in the reconstructed network
$\textbf{N}^{\prime}$; $\tau_{ij}^{\prime}$ and $f_{ij}^{\prime}(t)$ are the
constant travel time and the passenger flow during time period $\tau$ between
stations $i$ and $j$ on a reasonable path of the reconstructed graph
$\textbf{G}^{\prime}$;
$\psi_{\text{long}}(\textbf{G}^{\prime},t,\tau_{\text{disr}})$ is also known
as operational efficiency.

##  4 A case study of Beijing URT

###  4.1 Beijing URT and data description

By 2017, the URT system in Beijing, China, contained 19 lines (Lines 2 and 10
were circle lines), and the total lengths of the lines had reached 574
kilometers. The average number of daily passengers was approximately 12.4
million. It is representative and meaningful to assess the dynamic
vulnerability of such a URT system using the proposed indices, considering
that it is one of the largest URT systems worldwide.

The Beijing URT system is abstracted as an undirected and weighted topological
network with 287 stations, including 54 transfer stations, as the way
introduced in Section 2.1. The data used here were collected by the AFC system
of the Beijing URT in 6 days in October 2017, i.e., 9th (Monday), 10th
(Tuesday), 14th (Saturday), 15th (Sunday), 16th (Monday) and 17th (Tuesday).
The data contain every passenger’s record of entering and leaving the URT
system, including the time and the entry and exit stations. After data
cleaning, the number of valid records is approximately 5 to 6 million on
weekdays and more than 3 million on weekends. Figure 1 presents the hourly
change in the number of passengers entering and leaving the URT system in the
6 days. Peak-and-off-peak patterns in travel demand can be clearly observed.
More specifically, Figure 2 presents heterogeneous demands for URT lines. The
following observations are found: (1) different lines correspond to quite
different passenger demands, and (2) passenger demands are also different at
different time periods for the same line. The heterogeneous observations of
spatiotemporal demand in both Figures 1 and 2 clearly indicate the necessity
of the dynamic assessment of the time-changing vulnerability of a URT system
under the occurrence of the failure of stations, intervals and even whole
lines.

Figure 1: Time-varying passenger demand of using the Beijing URT system Figure
2: Passenger demands for different lines at different time periods by taking
October 16th (Monday), 2017, as an example Morning: 6:00 - 8:00; Midday: 11:00
- 13:00; Evening: 16:00 - 18:00.

###  4.2 Identification of the dynamic importance of stations

The dynamic importance of stations is identified in the Beijing URT by
employing the proposed accessibility-based index (Equation 4). The importance
of each station at different times of the day can be calculated, generating a
continuous curve that changes over time. There are 287 unique stations in the
Beijing URT network, and thus, we obtain 287 curves to represent the time-
varying importance of stations. To understand the changing patterns of these
curves, we conduct a cluster analysis on the curves by using hierarchical
clustering. In detail, the importance of each station is calculated every
three hours, and the time range is from 5:00 to 23:00, i.e., 18 hours in
total. The slope between two successive points in the curve is used as the
distance for hierarchical clustering, and four types of those curves can be
obtained, as shown in Figure 3. The variation trend and key features are
summarized as follows.

  * 1.

Type-i@: There are two peaks of importance. The moments with high importance
indices occur mainly in the morning and evening periods, which are the peak
hours of travel demand (refer to Figure 1).

  * 2.

Type-ii@: The importance of stations in Type-ii@ have a single peak in the
midday period.

  * 3.

Type-iii@: There are also has two peaks of importance. Compared with Type-i@,
the importance peak of Type-iii@ in the morning period is earlier.

  * 4.

Type-iv@: Most of these stations have small importance indices and do not have
distinct peaks, which may be related to the topological structure of the
station and constant travel demand.

(a) Type-i@

(b) Type-ii@

(c) Type-iii@

(d) Type-iv@

Figure 3: Four typical types of changes in station importance. (The proportion
is the ratio of the number of stations of one type to the total number of
stations)

Spatially, the four types of stations are marked in the Beijing URT line map,
as shown in Figure 4. The spatial distribution characteristics and potential
factors can be summarized from Figure 4 as follows.

  * 1.

<EMAIL_ADDRESS>The number of Type-i@ stations is the largest, mainly distributed on
the circle line of the central area and connected branch lines in the outer
areas of the city, and most of them are nontransfer stations represented by
small solid black circles (see Figure 4(a)). Those nontransfer stations are
more affected by passenger flow than topology, and their importance changes
significantly, especially in the morning and evening peaks.

  * 2.

<EMAIL_ADDRESS>Stations have a major relationship with surrounding land types, many
of which are near tourist attractions, airports and railway stations, as shown
in Figure 4(b). Stations include both transfer and nontransfer stations, which
represent different topological characteristics such as degree and
betweenness. However, every station has a high importance index at midday,
which may be associated with high travel demands at a certain period.

  * 3.

<EMAIL_ADDRESS>Stations are distributed mainly in the peripheral exurbs, many of
which are concentrated at the end of branch lines. Therefore, passengers who
have longer commuting distances from the suburbs to the city center usually
start off from the origin station earlier.

  * 4.

<EMAIL_ADDRESS>Stations consist mainly of transfer stations and surrounding
stations, with a few distributed at the end of branch lines. They usually have
a steady flow of passengers (staying high or low). Importance is influenced by
both topology and passenger flow.

(a) Type-i@

(b) Type-ii@

(c) Type-iii@

(d) Type-iv@

Figure 4:  A distribution map of different types of stations

In these four types of curves, the most obvious peaks of importance indices
appear mainly in the morning period (see Figure 3(a)), midday period (see
Figure 3(b)) and evening period (see Figure 3(a) and 3(c)). Therefore, we
extract those typical periods in the morning, midday and evening of the day
for further analysis. The importance index of each station in the three
periods can be obtained by using Equation 4, and the result is shown in Figure
5.

Figure 5: Importance level of each station at different times (the numbering
method is that transfer stations are numbered first and then nontransfer
stations are numbered in line order)

The importance index fluctuates from station to station over the same time
period. In particular, the difference in importance between adjacent stations
is often large, reflecting that the importance of stations within the same
line varies significantly. Therefore, even within the same line, different
stations should be protected selectively according to the importance level.
The level of importance of transfer stations is higher overall (station
identifications (IDs) that less than 54 are transfer stations). A few
nontransfer stations also have high indices of importance. Under the dual
influence of passenger flow and topological structure, the importance of
stations is not necessarily related to whether the station is a transfer
station.

As shown in Figure 5, the index of the same station at different time periods
differs. The maximum change in importance indices is found at Station 25
(difference values are 0.3662 and 0.2140) and Station 87 (difference value is
0.4396), caused mainly by the huge change in travel demand. The top 15
stations ranked with respect to importance index $\zeta_{i}(t)$ are shown in
Table 1 for further analysis. Most of the important stations are transfer
stations (represented by bold fonts), while the important nontransfer stations
are distributed mainly near the transfer stations or are the departure
stations of major branch lines (see Figure 6). In addition, the important
stations in different time periods have some changes but are more frequently
repeated. For example, a total of 12 stations are repeated in the morning and
evening periods. In conclusion, topological structure is still the main
determinant of the importance level of URT stations, while passenger flow in
the URT network is an important influencing factor.

Table 1: The importance index rank of stations | Morning | Midday | Evening
---|---|---|---
Rank |  | Station
---
ID
$\zeta_{i}(t)$ | $B_{i}(t)$ | $C_{i}(t)$ |  | Station
---
ID
$\zeta_{i}(t)$ | $B_{i}(t)$ | $C_{i}(t)$ |  | Station
---
ID
$\zeta_{i}(t)$ | $B_{i}(t)$ | $C_{i}(t)$
1 | 25 | 0.6780 | 0.0987 | 0.0065 | 87 | 0.8673 | 0.065 | 0.0273 | 16 | 0.5615 | 0.0627 | 0.0132
2 | 50 | 0.5229 | 0.0777 | 0.0229 | 149 | 0.6416 | 0.0999 | 0.0339 | 11 | 0.4764 | 0.144 | 0.0105
3 | 87 | 0.5192 | 0.0529 | 0.0172 | 16 | 0.5403 | 0.0682 | 0.0373 | 7 | 0.4701 | 0.1418 | 0.0105
4 | 16 | 0.4528 | 0.06 | 0.0219 | 8 | 0.4406 | 0.117 | 0.0424 | 8 | 0.4665 | 0.1179 | 0.0115
5 | 15 | 0.4345 | 0.1185 | 0.0612 | 72 | 0.4255 | 0.0406 | 0.0448 | 25 | 0.4641 | 0.0993 | 0.0454
6 | 11 | 0.4067 | 0.1438 | 0.0227 | 7 | 0.4084 | 0.1445 | 0.0410 | 15 | 0.4417 | 0.1258 | 0.0099
7 | 7 | 0.3953 | 0.1417 | 0.0247 | 11 | 0.3929 | 0.1538 | 0.0385 | 87 | 0.4276 | 0.0473 | 0.0220
8 | 55 | 0.3834 | 0.0143 | 0.0138 | 4 | 0.3556 | 0.1403 | 0.0562 | 50 | 0.4070 | 0.0709 | 0.0116
9 | 8 | 0.3800 | 0.1158 | 0.0282 | 25 | 0.3119 | 0.0942 | 0.0432 | 4 | 0.3860 | 0.1268 | 0.0138
10 | 149 | 0.3431 | 0.0884 | 0.0271 | 48 | 0.2955 | 0.0719 | 0.0520 | 48 | 0.3160 | 0.0755 | 0.0307
11 | 90 | 0.3277 | 0.0602 | 0.0117 | 15 | 0.2855 | 0.1266 | 0.0576 | 47 | 0.3116 | 0.0627 | 0.0167
12 | 47 | 0.3173 | 0.0639 | 0.0365 | 47 | 0.2447 | 0.0633 | 0.0651 | 75 | 0.3063 | 0.0485 | 0.0221
13 | 68 | 0.3068 | 0.0622 | 0.0634 | 75 | 0.2428 | 0.0511 | 0.0600 | 109 | 0.3042 | 0.0756 | 0.0317
14 | 48 | 0.3066 | 0.0801 | 0.0133 | 109 | 0.2308 | 0.0634 | 0.0727 | 90 | 0.2994 | 0.0637 | 0.1028
15 | 103 | 0.3007 | 0.0144 | 0.0182 | 14 | 0.2203 | 0.1276 | 0.0602 | 202 | 0.2953 | 0.0399 | 0.0184

In the Beijing URT network, the distribution of these stations in Table 1 is
shown in Figure 6. According to the frequency of one station appearing in the
top 15 of the three periods, the importance of those stations can be divided
into Importance Stations 1, 2 and 3. Importance station-1 is a situation in
which stations appear only once in the three periods. An important station-2
is a two-time situation. The importance station-3 appears in all three periods
and is relatively more important.

Figure 6: Distribution of important stations at different levels

Table 2: Several eigenvalues of importance for each operational line

Time |  Operational line |  $\zeta_{i}(t)$ |  $B_{i}(t)$ |  $C_{i}(t)$ |  $D_{i}(t)$
---|---|---|---|---|---
Morning |  Line 2 |  0.2201 |  0.0813 |  0.0609 |  265734.46
Line 13 |  0.1996 |  0.0619 |  0.043 |  197822.3339
Line AE |  0.1926 |  0.0314 |  0.4549 |  94041.1023
Line 1 |  0.177 |  0.0808 |  0.1075 |  267821.9381
Line 5 |  0.1603 |  0.0808 |  0.0648 |  269721.9532
Line 10 |  0.141 |  0.0628 |  0.067 |  207198.8144
Line 4 |  0.1326 |  0.0674 |  Inf |  224627.0213
Line 6 |  0.1323 |  0.0637 |  0.0603 |  210800.0315
Line FS |  0.1189 |  0.0389 |  0.0416 |  127107.6364
Line 9 |  0.1157 |  0.0889 |  0.0774 |  302880.9249
Line 14 |  0.0996 |  0.0406 |  0.0782 |  132499.2928
Line YZ |  0.0914 |  0.0316 |  Inf |  101934.0282
Line CP |  0.0908 |  0.0211 |  0.1442 |  64345.5229
Line BT |  0.0863 |  0.0249 |  0.0811 |  78965.7692
Line 8 |  0.0812 |  0.037 |  0.1655 |  121284.2406
Line 7 |  0.0775 |  0.0388 |  0.1337 |  128208.1818
Line 15 |  0.0697 |  0.0301 |  0.1469 |  97785.126
Line DX |  0.0459 |  0.0177 |  0.0829 |  57268.5455
Line 16 |  0.0305 |  0.0122 |  0.104 |  38257.7778
Midday |  Line AE |  0.1966 |  0.0343 |  0.3313 |  29134.8262
Line 2 |  0.1804 |  0.0846 |  0.105 |  81468.4881
Line 1 |  0.1344 |  0.0817 |  0.1198 |  79650.5256
Line 4 |  0.1277 |  0.0718 |  Inf |  69976.3691
Line 13 |  0.1251 |  0.0513 |  0.1421 |  48314.531
Line 5 |  0.0987 |  0.0794 |  0.1366 |  78350.7195
Line 9 |  0.0956 |  0.0899 |  0.1954 |  90028.0408
Line 6 |  0.0917 |  0.0623 |  0.1647 |  60788.3216
Line 10 |  0.0906 |  0.0586 |  0.1905 |  57150.413
Line 14 |  0.0687 |  0.0374 |  0.3147 |  35796.4586
Line FS |  0.0575 |  0.0384 |  0.2176 |  36908.3636
Line YZ |  0.0551 |  0.0321 |  Inf |  30616.3709
Line 7 |  0.0469 |  0.0375 |  0.404 |  36613.7326
Line BT |  0.0457 |  0.0231 |  0.344 |  21685.6923
Line CP |  0.04 |  0.0176 |  0.6999 |  16140.6783
Line 8 |  0.0312 |  0.0287 |  0.308 |  27926.9994
Line 15 |  0.0297 |  0.0243 |  0.4122 |  23350.1635
Line 16 |  0.0097 |  0.0093 |  0.6058 |  8608
Line DX |  0.0084 |  0.0108 |  0.5841 |  10274.2727
Evening |  Line 2 |  0.231 |  0.0816 |  0.0303 |  225076.6923
Line AE |  0.2184 |  0.0319 |  0.2265 |  79587.7031
Line 13 |  0.1959 |  0.0581 |  0.0562 |  156505.8522
Line 1 |  0.1859 |  0.0793 |  0.0447 |  221085.2975
Line 6 |  0.1564 |  0.0668 |  0.0849 |  186123.9364
Line 5 |  0.1521 |  0.0811 |  0.0556 |  228538.5176
Line 4 |  0.1456 |  0.0653 |  Inf |  182911.3058
Line 10 |  0.1388 |  0.0599 |  0.0799 |  166892.837
Line 14 |  0.1017 |  0.0395 |  0.1631 |  108629.9892
Line 9 |  0.1017 |  0.0829 |  0.0777 |  238347.0294
Line FS |  0.0927 |  0.0375 |  0.1592 |  103476.6364
Line YZ |  0.0915 |  0.0356 |  Inf |  97289.4317
Line CP |  0.0861 |  0.0207 |  0.6104 |  53359.2871
Line 7 |  0.0815 |  0.0378 |  0.1888 |  105210.4227
Line BT |  0.0782 |  0.0235 |  0.2372 |  62592.4615
Line 8 |  0.0743 |  0.0345 |  0.1269 |  95371.5969
Line 15 |  0.0571 |  0.0277 |  0.1376 |  76006.3561
Line DX |  0.0279 |  0.0154 |  0.4598 |  42121.8182
Line 16 |  0.0221 |  0.0102 |  0.4044 |  26957.4444

  * 1

Note: In the actual data, we found that Xinjiekou Station of Line 4 and
Xiaocun Station of Yizhuang Line had no card swiping record on that day.
Therefore, the demand closeness centrality $C_{i}(t)$ of these two lines is
infinite.

Based on the importance index of each station, the importance ranking of each
operational line can be obtained. Learning the average importance of each line
in the whole Beijing URT network (see Table 2, ranked by average importance
index $\zeta_{i}(t)$), is beneficial. The results illustrate that the
importance index of Line 2 is the highest in the morning and evening, while
the airport Line is the highest at midday, consistent with previous studies
that airports are important nodes in a URT network (Wang et al., 2020). Other
important lines, such as branch Line 13 and diameter Line 1, exist. The
traditional topological characteristics of these lines, such as flow
betweenness, demand closeness centrality and intensity, are also high, which
can reflect the effectiveness of our proposed importance index. Some of the
peripheral lines, such as the Yizhuang line, are also of high importance,
especially in the morning and evening periods. In addition, we observe a large
difference in importance between the two ring lines. Although the passenger
flow of Line 10 is larger than the passenger flow of Line 2 (as shown in
Figure 2), the importance of ring Line 2, which is closer to the center, is
higher, showing that the importance of ring lines is closely related to their
location in the city and topology in a URT network. As a reference metric, the
flow betweenness and other common indices can only represent a limited
criterion of station importance. Their ranking is normally different from our
importance index.

###  4.3 Network vulnerability under short-delay disruptions

We take $\tau_{\text{disr}}^{*}=60$ minutes considering the statistics of
travel time and passengers’ tolerance of delay. First, we analyze the
vulnerability of the Beijing URT network under short-delay disruptions when
the delay $\tau_{\text{disr}}\leq\tau_{\text{disr}}^{*}$. Different delays
caused by actual operation incidents have different impacts on passenger
demands and system performance. Therefore, the network vulnerability changes
under delays of 5, 10, 20, 40 and 60 minutes are explored. The top 15
important stations identified in the morning period (see Table 1) are selected
to be disturbed to cause short-delay disruptions. The vulnerability metric
$\psi_{\text{short}}(\textbf{G},t,\tau_{\text{disr}})$ is calculated by using
Equation 5, which represents the average delayed passenger demands. The higher
the value $\psi_{\text{short}}(\textbf{G},t,\tau_{\text{disr}})$ is, the more
vulnerable the network is. The experimental results are shown in Figure 7.
With the increase in delay, the impact of different stations on network
vulnerability also changes. Station importance is no longer linearly related
to the degree of vulnerability. Some stations that rank high in importance,
such as the 2nd, 3rd and 4th stations, may have a diminishing impact on
network vulnerability as delay increases. Some of the lower-ranked stations
can have a greater impact as delays increase (such as the 9th and 14th
stations), which may be related to the increase in travel demand affected by
operational delay.

As the delay increases, the affected travel demands vary for different
stations, and the decline rate of system performance shows a nonlinear change.
Experiments at midday and evening periods also have similar results.

(a) Changes in performance at different stations

(b) Changes in performance at different delays

Figure 7:  Network vulnerability changes under different delays during the
morning period

To explore the reasons why different stations have different impacts on
vulnerability over time, we analyze the topology and passenger flow
characteristics of those stations, as shown in Figure 8. We conduct Kendall
correlation analysis between the vulnerability curve (see Figure 7(b)) of
delay-60 minutes and the characteristic curves of the stations. The
topological betweenness is shown to have the strongest correlation with the
vulnerability curve. The intensity and flow betweenness of stations that are
related to passenger flow also have a high correlation, indicating that some
stations that serve as bridges and have a large number of passengers usually
have the greatest influence on network vulnerability.

Figure 8:  Eight typical characteristics of the station. Kendall: the
correlation coefficient between characteristic curves (when there are
different time periods, the curve of the morning time period is adopted) and
the vulnerability curve

The correlation between vulnerability curves and elected characteristics
curves under different time periods and delays is further analyzed, as shown
in Table LABEL:tab:delay. In the same period, the correlation between curves
increases gradually with increasing delay. With a longer delay, the
characteristics of the station itself influence the network vulnerability more
apparently, which can lead to the changing trend of system performance.
Notably, remarkable characteristics are different in different time periods,
as shown in bold font in Table LABEL:tab:delay. Multiple characteristics are
known to jointly determine the change in network vulnerability. However, the
key factors affecting network vulnerability may be different under different
degrees of disturbance or stages of disruption.

Table 3: Correlation analysis under different delay degrees at different time periods Time period |  |  Delay time
---
(min)
|  Topological
---
Degree
|  Topological
---
betweenness
Intensity |  |  Flow
---
betweenness
Morning |  5 |  0.38797 |  0.73333 |  0.6 |  0.6
20 |  0.45263 |  0.77143 |  0.67619 |  0.67619
60 |  0.60351 |  0.88571 |  0.82857 |  0.82857
Midday |  5 |  0.33635 |  0.71429 |  0.58095 |  0.61905
20 |  0.31232 |  0.71429 |  0.69524 |  0.65714
60 |  0.45647 |  0.79048 |  0.80952 |  0.73333
Evening |  5 |  0.39977 |  0.65714 |  0.48571 |  0.46667
20 |  0.35408 |  0.65714 |  0.67619 |  0.65714
60 |  0.51399 |  0.69524 |  0.75238 |  0.73333

###  4.4 Network vulnerability under long-delay disruptions

When $\tau_{\text{disr}}>60$ minutes, we assume that the station is completely
shut down and all transportation functions are disabled. The variation in
network vulnerability can be obtained by simulating station failure.
Furthermore, considering the particularity of URT operation delays, single
station failure and interval failure are considered in an in-depth analysis of
network vulnerability. The vulnerability metric is the operational efficiency
$\psi_{\text{long}}(\textbf{G}^{\prime},t,\tau_{\text{disr}})$ in Equation 7.

First, we study the vulnerability variation in the Beijing URT network under
single station failure. Based on the importance ranking of stations identified
in Section 4.2, the network vulnerability is simulated by means of deliberate
attack. The results are shown in Figure 9. For the three time periods, the
vulnerability of the Beijing URT network caused by station failure changes
greatly, showing an exponential decline and an obvious heavy tail
distribution. Compared with the morning and evening periods, the network
vulnerability at midday is at a lower initial level, while it also decreases
by 76% when the failed stations reach 50.

Figure 9: Network vulnerability changes under station failure

Second, we simulate the continuous failure of multiple stations based on the
importance ranking of operational lines (see Table 2). The failure process
first occurs within an operating line where the most important station first
fails. The process then fails along the direction of the second largest
importance station. Similarly, stations on other lines fail, and the results
are shown in Figure 10. The decline in system performance is obviously
segmented and stratified, and the impact of station failure in a single line
on network vulnerability shows little change. The station failure between
different lines is the main cause of the performance decline, and some
important stations within the line will act as catalysts to accelerate the
performance decline of the Beijing URT network.

Figure 10: Network vulnerability changes under interval failure

To explore the influence of the failure direction within a line on the system
performance, we carry out experiments in opposite directions and two
directions. The results show that the failure direction has little influence
on the network vulnerability, as shown in Figure 11. The degradation of system
performance depends mainly on the failure of critical lines or stations.
Combined with Figures 10 and 11, the significant decline in vulnerability
index $\psi_{\text{long}}(\textbf{G}^{\prime},t,\tau_{\text{disr}})$ occurs
mainly after the failure of several specific stations or the cumulative
failure of multiple stations. In addition, according to the importance ranking
in Section 4.2, a high level of importance of a single line or station does
not mean that it has a great influence on the network vulnerability. The
degree of influence on the network vulnerability is often the cumulative
effect of multiple stations or lines. Therefore, it is necessary to avoid the
continuous failure of multiple stations, especially the failure of an entire
line and connected lines.

(a) Failure in the direction with smaller degree value

(b) Alternating failure in both directions

Figure 11:  Interval failure in different directions

Finally, we test the influence of special interval failure, i.e., two or three
adjacent stations fail simultaneously in the Beijing URT network, on
vulnerability. The first method of interval failures is similar to the
continuous failure of multiple stations. The failure process first occurs
within an operating line where the most important interval first fails. Then,
according to the sequence of line importance, intervals on other operation
lines fail. The results are similar, as shown in Figure 12. Interval failures
within the same line degrade system performance faster than station failures.
In addition, the segmented and stratified decline of the vulnerability curve
is still evident. This further indicates that the dominant loss of the URT
system performance is due to the failure of certain critical stations and
lines.

(a) Simultaneous failure of two stations

(b) Simultaneous failure of three stations

Figure 12:  Interval failure within the same line

We then conduct further experiments of another interval failure where
intervals fail randomly between different lines. According to the rank of the
total importance of any two adjacent stations, the interval failure composed
of two stations is tested, as shown in Figure 13. The results show that the
system performance degrades faster in the case of interval failure of
different lines so that, in practice, interval failures between different
lines should be avoided as much as possible. Confining the consequences of
disturbance to a single interval or line would greatly avoid a rapid breakdown
of the entire network and race against time for rescue operations.

Figure 13: Interval failure between different lines

###  4.5 Regular verification

The experiments above use the AFC data of one day, and the results may be
contingent. We thus repeat the experiment and perform a comparative analysis
using data from the other five days of the two weeks. Most of the experimental
results are consistent. We describe mainly special findings and conclusions of
general regularity. Overall, the multiday experiment shows differences between
weekdays and weekends.

The first verification is the distribution of the importance of stations and
lines. The frequency of the top 15 important stations in each period of six
days is shown in Table 4. There are significant differences between the
important stations that appear separately on weekdays and weekends. Stations
with high frequency on weekends are located mainly near shopping malls (No. 4
Xidan station, No. 48 Shilihe station), railway stations (No. 72 Beijing
station) and hospitals (No. 75 Jishuitan station). Important stations that
appear separately on weekdays are mainly large transfer stations (No. 8
Dawanglu station, No. 15 Chaoyangmen station, No. 47 Sanyuanqiao station),
connection points between branch lines and central lines (No. 50 Xierqi
station), residential areas (No. 68 Fuchengmen station) and industrial parks
(No. 202 Jiangtai station). Compared with Table 1, stations with the highest
frequency do not change significantly, and their distribution is similar, as
shown in Figure 14, showing that changes in demand over time periods of days
and holidays have a significant impact on the importance of most stations.
While the importance of a few stations change independently from passenger
demands where topological structure has dominant effect. Stations with the
largest changes in importance at different periods are also similar, as shown
in Table 5. These stations also have obvious differences between weekdays and
weekends, reflecting the difference in travel demands. In contrast, the
changes in important lines are more stable, and few differences appear in the
midday period.

Table 4: Top 15 stations for multiple days |  Station ID
---
(Weekend)
Frequency |  |  Station ID
---
(Workday)
Frequency |  |  Station ID
---
(Six days)
Frequency
4 |  6 |  7 |  12 |  7 |  18
7 |  6 |  8 |  12 |  11 |  18
11 |  6 |  11 |  12 |  16 |  18
16 |  6 |  15 |  12 |  25 |  18
25 |  6 |  16 |  12 |  87 |  18
48 |  6 |  25 |  12 |  8 |  17
72 |  6 |  47 |  12 |  48 |  15
87 |  6 |  87 |  12 |  149 |  15
149 |  6 |  48 |  9 |  4 |  14
8 |  5 |  149 |  9 |  72 |  13
75 |  4 |  4 |  8 |  15 |  12
90 |  4 |  50 |  8 |  47 |  12
109 |  4 |  90 |  8 |  90 |  12
233 |  4 |  72 |  7 |  109 |  10
55 |  3 |  68 |  6 |  75 |  9
183 |  3 |  109 |  6 |  50 |  8
84 |  2 |  202 |  6 |  55 |  7
232 |  2 |  75 |  5 |  68 |  6
249 |  2 |  55 |  4 |  202 |  6
Figure 14: Distribution of important stations at different times during the six days Table 5: Stations with the greatest changes in importance across days Date |  |  Station ID
---
(Morning-Midday)
|  Station ID
---
(Morning-Evening)
|  Station ID
---
(Midday-Evening)
Mon.(9th) |  87 |  25 |  87
Tue.(10th) |  87 |  25 |  87
Sat.(14th) |  4 |  4 |  87
Sun.(15th) |  4 |  4 |  25
Mon.(16th) |  25 |  25 |  87
Tue.(17th) |  25 |  25 |  87

In the analysis of vulnerability, the results considering station and interval
failure are basically the same as the results of the one-day experiment.
Taking interval failure between different lines as an example, the results are
shown in Figure 15. System performance changes more slowly on weekends during
the morning period, possibly related to less travel demand in the whole
network. In fact, when the delay $\tau_{\text{disr}}$ reaches a threshold
$\tau_{\text{disr}}^{*}$ where the station is permanently closed, the affected
travel demand usually stays the same. At this point, the failure types and the
importance of the failed stations have the greatest impact on network
vulnerability.

(a) Morning

(b) Midday

(c) Evening

Figure 15:  Variation in network vulnerability in different periods of six
days (interval failure between different lines). The X-coordinate is
logarithmic

##  5 Discussion and conclusion

Considering the time-varying travel demands, this paper proposes an evaluation
method to analyze the dynamic vulnerability of a URT system from the network
perspective. Based on the static network topology and dynamic passenger flow,
the importance index of stations and the vulnerability metric are established.
By taking Beijing URT as an example, this paper analyzes the impact of
different delay disruption types disturbed by daily operation accidents on
network vulnerability. New experimental phenomena are observed and summarized
as follows.

  * 1.

The distribution of critical stations is varies in different time periods, as
there are many repeated stations, showing that the topological structure of
the network itself plays a decisive role, and the passenger flow as a
participant in the system is an important influencing factor. The properties
of critical stations are not only the transfer stations with high passenger
flow but also the nontransfer stations around them and the departure station.

  * 2.

The change in network vulnerability is different under different disruption
types. In the case of short-delay disruption, the impact of critical stations
on network vulnerability varies with the increase in delayed passenger demand.
The stations that have the greatest impact on network vulnerability are those
that act as bridges and have large passenger flows, while not all these
stations are hubs. In the case of long-delay disruption, the vulnerability of
Beijing URT decreases exponentially and has an obvious heavy tail
distribution.

  * 3.

Furthermore, the degradation of system performance under continuous interval
failure is obviously segmented and stratified. The interval failure within the
same line has little effect on network vulnerability, while the failure
between different lines and their cumulative effect is the main reason for the
sharp decrease in system performance. Some important stations or intervals
within the line can act as catalysts to accelerate the performance degradation
of the URT network, regardless of the direction of the station failure.

  * 4.

Multiple days of AFC data confirmed these results, and some special phenomena
were found. Some critical stations exist independently of the dynamic
passenger demands, which illustrates that the topological structure plays a
decisive role. The ranking of critical lines is more stable. In conclusion,
the importance of stations and lines all vary significantly during holidays
and weekdays.

In practice, protection and rescue resources are limited, and operators and
managers should selectively protect and repair critical components (stations,
intervals and lines), greatly reducing the probability of system breakdown and
recovery time. In preventing disruptions, a reasonable scheme of resource
allocation should be carried out for different components in different time
periods. Some recurring components of importance identified in different
periods need special attention, and adjacent nontransfer stations should also
be protected. In addition, components for which indices of importance vary
greatly in different periods tend to be more critical than constant importance
components regardless of whether they have a high or low index. After a
disruption occurs, the rescue force should pay more attention to the key
critical stations or intervals, i.e., the end nodes of each layer in a step-
down vulnerability curve. If the key critical stations or intervals fail, the
system performance will fall off a cliff. In the accident of continuous
station failures due to external disturbance, multiple interval failures
between different lines should be avoided as much as possible because the
multiple interval failures can cause the system performance to plummet and
crash the entire URT network.

Future research directions are as follows. The assumption that passengers will
wait when the delay time increases is not exactly consistent with reality.
Through field surveys or questionnaires, more accurate travel data can be
applied to dynamic vulnerability assessments. In the clustering process of the
importance curve, we find that the clustering results are influenced by
different time granularities, which may be related to the clustering
algorithm. New results may be found by adopting better clustering methods.

We can continue to discuss the influence of more types of interval failures on
the vulnerability of a URT network, including the division of intervals within
a line. The distribution of critical stations is also related to the
geographical environment, population density and economic activities, and the
correlation can be further explored by combining relevant data such as points-
of-interest (POIs). In addition, how to effectively recover the URT system
performance after disruptions is also an important research direction in the
future.

## Acknowledgment

The research is funded by National Natural Science Foundation of China
(71871010).

## References

  * Abrahamsson (1997) Abrahamsson, T., 1997.  Characterization of vulnerability in the road transport system.  Working report .
  * Berdica (2002) Berdica, K., 2002.  An introduction to road vulnerability: What has been done, is done and should be done.  Transport Policy 9, 117–127.
  * Cats and Jenelius (2014) Cats, O., Jenelius, E., 2014\.  Dynamic Vulnerability Analysis of Public Transport Networks: Mitigation Effects of Real-Time Information.  Networks and Spatial Economics 14, 435–463.
  * Chen et al. (2012) Chen, B.Y., Lam, W.H., Sumalee, A., Li, Q., Li, Z.C., 2012.  Vulnerability analysis for large-scale and congested road networks with demand uncertainty.  Transportation Research Part A: Policy and Practice 46, 501–516.
  * Crucitti et al. (2003) Crucitti, P., Latora, V., Marchiori, M., Rapisarda, A., 2003\.  Efficiency of scale-free networks: Error and attack tolerance.  Physica A: Statistical Mechanics and its Applications 320, 622–642.  0205601.
  * Diab and Shalaby (2019) Diab, E., Shalaby, A., 2019\.  Metro transit system resilience : Understanding the impacts of outdoor tracks and weather conditions on metro system interruptions.  International Journal of Sustainable Transportation 0, 1–14.
  * Donovan and Work (2017) Donovan, B., Work, D.B., 2017\.  Empirically quantifying city-scale transportation system resilience to extreme events.  1507.06011.
  * Feng et al. (2017) Feng, J., Li, X., Mao, B., Xu, Q., Bai, Y., 2017\.  Weighted complex network analysis of the Beijing subway system: Train and passenger flows.  Physica A: Statistical Mechanics and its Applications 474, 213–223.
  * Hong et al. (2020) Hong, L., Ouyang, M., Xu, M., Hu, P., 2020.  Time-varied accessibility and vulnerability analysis of integrated metro and high-speed rail systems.  Reliability Engineering and System Safety 193, 1–10.
  * Ilbeigi (2019) Ilbeigi, M., 2019.  Statistical process control for analyzing resilience of transportation networks.  International Journal of Disaster Risk Reduction 33, 155–161.
  * Lu (2018) Lu, Q.c., 2018.  Modeling network resilience of rail transit under operational incidents.  Transportation Research Part A 117, 227–237.
  * Ouyang et al. (2015) Ouyang, M., Pan, Z., Hong, L., He, Y., 2015.  Vulnerability analysis of complementary transportation systems with applications to railway and airline systems in China.  Reliability Engineering and System Safety 142, 248–257.
  * Rodríguez-Núñez and García-Palomares (2014) Rodríguez-Núñez, E., García-Palomares, J.C., 2014.  Measuring the vulnerability of public transport networks.  Journal of Transport Geography 35, 50–63.
  * Sun and Guan (2016) Sun, D.J., Guan, S., 2016.  Measuring vulnerability of urban metro network from line operation perspective.  Transportation Research Part A: Policy and Practice 94, 348–359.
  * Wang et al. (2020) Wang, L., Chen, Y., Wang, C., 2020.  Research on evolutionary model of urban rail transit vulnerability based on computer simulation.  Neural Computing and Applications 32, 195–204.
  * Zhang and Wang (2019) Zhang, J., Wang, M., 2019.  Transportation functionality vulnerability of urban rail transit networks based on movingblock : The case of Nanjing metro.  Physica A 535, 122367\.
  * Zhou et al. (2019) Zhou, Y., Wang, J., Huang, G.Q., 2019.  Efficiency and robustness of weighted air transport networks.  Transportation Research Part E 122, 14–26.