# FSboard: Over 3 million characters of ASL fingerspelling collected via
smartphones

Manfred Georg1 , Garrett Tanzer1∗, Saad Hassan2‡, Maximus Shengelia3‡,
Esha Uboweja1, Sam Sepah1, Sean Forbes4†, Thad Starner1∗†
1Google, 2Tulane University, 3Rochester Institute of Technology,
4Deaf Professional Arts Network
{mgeorg<EMAIL_ADDRESS>equal contribution $\dagger$ equal advising
$\ddagger$ work conducted while at Google

###### Abstract

Progress in machine understanding of sign languages has been slow and hampered
by limited data. In this paper, we present FSboard, an American Sign Language
fingerspelling dataset situated in a mobile text entry use case, collected
from 147 paid and consenting Deaf signers using Pixel 4A selfie cameras in a
variety of environments. Fingerspelling recognition is an incomplete solution
that is only one small part of sign language translation, but it could provide
some immediate benefit to Deaf/Hard of Hearing signers as more broadly capable
technology develops. At $>$3 million characters in length and $>$250 hours in
duration, FSboard is the largest fingerspelling recognition dataset to date by
a factor of $>$10x. As a simple baseline, we finetune 30 Hz MediaPipe Holistic
landmark inputs into ByT5-Small and achieve 11.1% Character Error Rate (CER)
on a test set with unique phrases and signers. This quality degrades
gracefully when decreasing frame rate and excluding face/body
landmarks—plausible optimizations to help models run on device in real
time.111We publicly release FSboard at this link under a CC BY 4.0 license.

##  1 Introduction

The quality of sign language translation, particularly from American Sign
Language (ASL) to English, has been steadily improving [14, 52, 53, 47], but
it is still far from being usable in practice. A body of work on participatory
methods for ML [9, 11] suggests dividing such an ambitious goal into
intermediate milestones that can provide concrete and immediate benefit to the
community (_i.e._ , Deaf/Hard of Hearing signers). In this manner, the work
starts addressing the community’s needs immediately, and the community can
drive the direction of future technology.

We focus on the intermediate goal of recognizing fingerspelling as an
alternative to smartphone text entry. While full signing for text entry (the
proper analogue of speech recognition) is ideal [24], fingerspelling may still
be a valuable stopgap due to improved speed or convenience vs. typing on a
keyboard. An analogy can be made to gesture keyboards [56], where the user
swipes through the letters of a word as opposed to touching and releasing each
letter’s virtual key. Even though the system uses pattern recognition to
determine which word the typist intended and sometimes returns an incorrect
word, many smartphone users prefer such gesture-based keyboards as they feel
they can enter text more quickly with the added benefit of requiring one hand
instead of two [46]. Similarly, there is evidence that Deaf signers may find
fingerspelling faster or more convenient than current smartphone text entry
keyboards [24].

In this paper we present FSboard (Fingerspelling-board, as in “keyboard”), an
ASL fingerspelling dataset situated in a mobile text entry use case. We
collect FSboard by creating a domain-appropriate phrase distribution,
recruiting 147 paid and consenting Deaf signers through the Deaf Professional
Arts Network (DPAN), and having them record one-handed fingerspelled
renditions of the phrases using Pixel 4A selfie cameras in a variety of
environments. The videos were usually recorded at 1944x2592 pixels and 30
frames per second, though sometimes the resolution varied due to participants
accidentally changing settings. At 3.2 million characters in length and 266
hours in duration, FSboard is the largest fingerspelling recognition dataset
to date by a factor of $>$10x.

As a simple baseline, we finetune 30 Hz MediaPipe Holistic landmark inputs
into ByT5-Small (300M) and achieve 11.1% Character Error Rate (CER) on
FSboard’s test set, which features 15 unique signers and no phrase overlap
with the train set. We ablate our baseline across several factors like frame
rate and exclusion of face/body landmarks which could be used to optimize
MediaPipe Holistic’s on-device performance, and find that these compromises
(in moderation) cause minimal regressions. Qualitatively, the baseline outputs
are promising but should be evaluated end-to-end in realistic settings in
future work.

We hope that FSboard will help develop text entry methods that start to give
signers a more equitable experience with technology, as well as aid in longer
term research towards full sign language understanding.

##  2 Background

Figure 1: A sample of frames from FSboard. Faces blurred here but not in the
dataset.

MacKenzie [33] | prevailing wind from the east
---|---
| elephants are afraid of mice
| my favorite place to visit
URLs | http://datastudio.google.com
| si.wikipedia.org
| /dfinance/list.asp?id=418/
Addresses | 9841 gritt hill
| 200ab lake charles
| 24 north 118th place
Phone Numbers | 166-893-6320
| +44-527-848-96-69-05
| +678-92-00-9661
Names | mohammed kim
| gustavo ho
| clifford davenport
Figure 2: A sample of phrases from each category of FSboard. Addresses, phone
numbers, and names are generated randomly; they are not real personally
identifiable information (PII).

According to the United Nations and the World Health Organization, there are
over 70 million Deaf and Hard of Hearing people in the world [1, 2]. Many use
one or more of around 150 sign languages to communicate [16]. For example,
American Sign Language (ASL) is used by about 500,000 people as a primary
language in United States alone [35].

Sign languages are complete, natural languages that can differ from one
another significantly even in societies where the same spoken language is used
[4, 16]. For example, American Sign Language differs from British Sign
Language (BSL) significantly and is instead genetically related to French Sign
Language [4]. However, almost all sign languages include a manual alphabet
used to represent letters as hand shapes and movements. Often, fingerspelling
is used for proper nouns or when introducing new concepts. Fingerspelled terms
may also be adapted into the closed vocabulary of a sign language in a process
called lexicalization [28, 55]. For example, the sign for “job” in ASL can be
seen as a combination of the letters J and B, with the O abbreviated or
elided, but the B is in a different orientation from typical fingerspelling.
The amount of fingerspelling used in conversational discourse varies depending
on the sign language. In ASL, fingerspelling is about 12%-35% of signing [40,
29].

Some fingerspelling systems are one-handed, such as ASL or Japanese Sign
Language (JSL), while others, such as BSL, are two-handed [43]. Even though
meanings may be different, similar hand shapes and movements can be seen
across sign languages due to the physical constraints of the hand [34], which
suggests that datasets collected for one sign language may offer some transfer
to others, or to recognizing handshapes and movements in signing more broadly.
This benefit may be especially true for ASL fingerspelling, which belongs to
the largest cluster of manual alphabets, the “French-origin group” [43]. For
example, many of the letters in the ASL manual alphabet have the same
handshape in French, Italian, and German Sign Languages.

There are many works, both informal and academic, which claim to study
fingerspelling recognition for ASL and other sign languages but operate on
single images. Such efforts are in reality studying handshape classification,
with exceptions for fingerspelled letters such as J and Z that incorporate
movement. Ghanem et al. [17] provide a survey. Real-time demonstrations are
often slow, with feedback on one letter at a time. These systems ignore the
co-articulation effects that occur when recognizing fingerspelling at speed as
well as the problem of determining where the space is between two
fingerspelled words. In addition, when fingerspelling at speed signers often
“bounce” or “slide” a handshape from inside to outside the body when a letter
repeats in a word. We are only aware of the ChicagoFS series of datasets [6,
7, 30] that are directly comparable to the effort here for American Sign
Language fingerspelling; we provide a detailed comparison to ChicagoFS in
Section 3.4 below.

###  2.1 Fingerspelling for smartphone text entry

Historically, most sign language recognition systems have had little
usefulness or usability for the Deaf community [9, 10, 15, 25]. Often the Deaf
community is not consulted on the technology being created, nor formative or
summative user studies performed. For this work, three of the authors are
members of the Deaf community and were integral to the selection of the task,
pilot studies and testing, and recruitment of the participants whose primary
language is ASL.

Our efforts to create a fingerspelling dataset are motivated by Hassan et al.
[24], a user study which established the potential benefits of text entry for
smartphones based on fingerspelling. It compared an emulated fingerspelling
keyboard to normal smartphone typing on Gboard (Android’s default keyboard)
for 12 Deaf participants and found that fingerspelling was faster than the
smartphone keyboard (42.5 wpm vs. 31.9 wpm), had fewer errors (4.0% vs. 6.3%)
and had higher throughput (14.2 bits/second vs. 10.9 bits/second). In post-
study surveys, 50% of these Deaf participants preferred fingerspelling for
text entry using the emulated recognition system.

Further adding support that fingerspelling may prove faster than smartphone
virtual keyboards, we examined common MacKenzie phrases fingerspelled in the
FSboard dataset presented below. Signers averaged around 65 wpm, with some
maintaining over 100 wpm. This result is significantly faster than the average
smartphone typist at around 36 wpm [41] and is consistent with the
conversational fingerspelling rates reported in the literature [44].

Texting is often the first use case that comes to mind when thinking about
text entry on a smartphone. However, members of the Deaf community have
emphasized that fingerspelling to a smartphone may be best suited for entering
names or addresses into specific smartphone applications like Google Maps. One
can imagine a Deaf signer setting their default keyboard on their smartphone
to one that shows both the on-screen keyboard as well as a selfie camera feed
that could be used for fingerspelling. In this manner, the signer could easily
switch between, or combine, input methods for all applications that require
text entry.

###  2.2 Community-centered sign language datasets

PopSign and ASL Citizen are two prior works grounded in focused tasks that
could benefit signing communities. Both are isolated sign recognition tasks
(classifying which single sign is present in a given clip). PopSign [50] is an
educational smartphone game intended to help hearing parents of deaf infants
practice sign language (and avoid language deprivation [19, 20, 21, 22, 23,
26, 27, 38]).

In the game, the user signs one of five options to select a bubble of a
particular color, and these five active options rotate among a library of 250
signs in a way that avoids recognizer confusion. Limiting the number of
classes ensures >99% top-1 accuracy [8]. As with FSboard, the PopSign dataset
is collected at high resolution (1944x2592) using Pixel 4A smartphone selfie
cameras. The PopSign dataset includes over 200,000 clips and 128 hours of
video.

ASL Citizen [13] grounds the sign recognition task in a dictionary retrieval
setting, enabling signers to record a video clip of a sign to retrieve its
dictionary entry. This task demands a much larger sign vocabulary/number of
classes, but retrieval is relatively forgiving because a number of outputs can
be returned (_i.e._ , top-N accuracy) from which the user can choose. The
authors report a top-1 accuracy of 62% but a top-10 accuracy of 90% on a 2731
sign vocabulary. The dataset contains 83,912 videos taken from webcams, and
the dataset resolution is often 640x480.

Figure 3: Monk Skin Tone Scale ratings for FSboard participants, annotated by
majority vote of three human raters trained specifically for the skin tone
task.

Figure 4: Perceived gender presentation of FSboard participants, annotated by
human raters. Note that this is not equivalent to gender identity, because it
is predicted from the videos rather than self-identified.

##  3 The FSboard Dataset

In this section we describe the set of phrases we elicited for FSboard and how
the data was collected.

###  3.1 Phrases

Numbers should not necessarily be considered fingerspelling, but they are
relatively formulaic and often appear in the same contexts as/alongside
fingerspelling. There are special signs for various numbers (such as 11, 12,
23, 25, 33, and many more) and specific movements which are generally used
while signing numbers, but for practical purposes, the systems for signing
cardinal numbers and fingerspelling words are very related, so we choose to
include numbers within the scope of our fingerspelling recognition system.

We construct our phrase set with a variety of domains: MacKenzie phrases,
URLs, addresses, phone numbers, and names. See Figure 2 for examples from each
of these categories.

First, we include the MacKenzie phrase set [33], a classic set of 500 phrases
used to evaluate text entry systems. These phrases are intended to be
collected multiple times by different signers, to serve as a closed vocabulary
testbed for sanity checking methods. The rest of the domains are intended to
be unique phrases.

Second, we include randomized URLs using URL parts from a web crawl in April
2022. The crawled URLs were broken into unique domain name parts and directory
parts. Gibberish parts were removed using a set of manual rules and a simple
two character Markov chain trained to recognize URLs a human might want to
fingerspell [39]. Finally, URLs were randomly generated from the parts,
sometimes including the protocol identifier (such as `https://`) and sometimes
removing the domain name entirely. Some URLs suggest explicit content, which
we release as a separate collection of metadata to ensure they are not
included in the dataset/models trained on it by default.

Third, we include randomly constructed street addresses. The street names were
sampled from the US Census Bureau’s 2019 TIGER release [12], filtered to
remove repetitive, uncommon, and hard to fingerspell names (such as roads that
are named by number "Co Rd 87" and "Cr-1601Q4"). Street numbers of 1 to 6
digits were randomly generated with a heavy bias towards 4 digit numbers. Some
addresses had their standard abbreviations expanded ("Lane" for "LN", "Road"
for "Rd") while others maintained the abbreviation.

Fourth, we include names randomly generated as combinations of the 1000 most
common first and last names in the United States.

Fifth, we include random phone numbers. These include 10 digit US numbers,
with and without the "+1", and semi-realistic non-US numbers. The non-US
numbers were generated with a valid country code and realistic groupings, but
no effort was made to create correct lengths for the country code used.

Although these categories are not exhaustive, they form a solid basis for
creating and evaluating a practical fingerspelling system. In the future, we
suggest improving the representation of symbols in the dataset and diversity
of formats within each category above. More care could also be taken around
the inclusion of spaces and instructions to the participants about how to
represent spaces in various contexts (either as pauses or, where appropriate,
more explicitly with a hand motion). Further clarification of the instructions
about whether and how to represent capitalization would also be helpful.

###  3.2 Data Collection

The Deaf Professional Arts Network (DPAN) recruited Deaf signers who use ASL
as their primary language to participate in the data collection, of whom 147
completed the task. DPAN shipped loaner Pixel 4A smartphones to them with a
custom data collection app installed [24]. This app was a precursor to the
open sourced Record These Hands [48] data collection app.

The app showed a phrase as text. The participant would touch an on-screen
button to begin the phrase, then fingerspell the phrase (with the other hand),
and finally press another button to advance to the next phrase. There was also
a button to be pressed if a mistake was made in fingerspelling the phrase. For
most participants, this button did not work properly, leading to issues in
data cleanup. A single video was recorded for the entire session with button
presses merely recording a timestamp.

The participants were asked to record videos in various settings and
circumstances, leading to many different views and backgrounds. Some people
wear masks; sometimes the face or portions of the hands are out of frame;
sometimes the field of view is at a strange angle recording videos from below.
Many participants opted to place the phone down in some way leading to a large
variability in distance to participant, motions required for button presses,
and timing between button press and the beginning or end of fingerspelling.
Particularly for the MacKenzie phrases, most participants ran together the
entire phrase with little regard for the separation of words.

###  3.3 Data Cleanup

Due to bugs in the data collection app and some user errors, the timespans
recorded above frequently did not capture the actual phrase. In order to
generate reasonable clips we used a bootstrapping method based on our baseline
ByT5 model, described in Section 4. First the model was trained on a large
corpus of YouTube videos with captions. Next, five models were finetuned to
transcribe folds of the noisily bounded fingerspelling data. (Each fold was
trained on 4/5 of the data and transcribed the remaining 1/5.) Since
evaluation bias was irrelevant, the dataset splits were performed at the clip
level such that every participant was in every split. Each model was then used
to predict text for the remaining 1/5th that it had not yet seen. Where the
model agreed with the clip boundaries and content, the clip was labeled as
clean, otherwise the clip was labeled as noisy. The whole process was repeated
two more times (starting each time with a fresh model) using only the clean
clips from the previous round. A significant amount of manual editing and
custom rules tailored to each participant were then used to further clean the
clips. There are still some issues with the clip boundaries in the dataset,
and it would benefit from further annotation.

###  3.4 Dataset Statistics

We divide FSboard into train, validation, and test splits with unique signers
in each split (117, 15, and 15 signers respectively) and no overlap of phrases
between splits.222Due to a bug in the data collection app, sometimes up to 3
signers were prompted to fingerspell the same phrase when we intended to keep
the phrases unique. We discarded some data in order to create splits without
overlap in signers or phrases. The signers in each split were chosen so as to
minimize the amount of data which needed to be discarded in order to keep each
phrase only in one split. This resulted in a 29% reduction in the number of
phrases in the non-MacKenzie portion of FSboard.

See Figure 5 for statistics about FSboard (and its splits) in comparison to
prior fingerspelling recognition datasets. At 3.2M characters in phrase length
and 266 hours in video duration, FSboard is more than 10x larger than
ChicagoFSWild+, the largest prior fingerspelling recognition dataset. The
number of sequences in FSboard is only about 3x that of ChicagoFS, reflecting
that the average sequence length in FSboard (21.2 characters) is much longer
than prior works (5.5 in ChicagoFSWild+) due to the domain. The number of
unique signers is also lower (147 vs. 260), since FSboard’s data is created
from new participants rather than scraped from the web like ChicagoFSWild(+).
FSboard is unique for fingerspelling datasets in that it is recorded from a
one-handed smartphone perspective, like PopSign [50] does for isolated sign
classification.

We used trained human annotators to give more visibility into FSboard’s
demographic fairness: see Figure 4 for Monk Skin Tone Scale [36] ratings and
Figure 4 for classifications of perceived gender presentation. The dataset has
a good amount of variation in skin tone but lacks the lightest and darkest
ends of the scale. It is approximately as diverse as OpenASL [49] (though the
classification system is different), and much more diverse than YouTube-SL-25
[youtubesl25]. Masculine presentation is underrepresented in FSboard, with
only 35.6% of signers. This statistic stands opposite ChicagoFSWild+ [6],
which underrepresents feminine presentation to about the same degree; OpenASL
and YouTube-SL-25 are essentially at parity.

name | lang | # seqs | # chars | # hrs | # signers | source
---|---|---|---|---|---|---
ChicagoFSVid [30] | ASL | 4K | 21K | <1 | 4 | Lab
ChicagoFSWild [7] | ASL | 7K | 38K | 2 | 160 | Web
ChicagoFSWild+ [6] | ASL | 55K | 0.3M | 14 | 260 | Web
FSboard (ours) | ASL | 151K | 3.2M | 266 | 147 | Smartphone
train | 126K | 2.8M | 224 | 117
validation | 12K | 0.2M | 19 | 15
test | 13K | 0.2M | 23 | 15
Figure 5: Summary statistics for fingerspelling recognition datasets.

##  4 Baselines

We build our baselines on ByT5 [54], a character-level encoder-decoder
language model in the T5 family [45]. Following the YouTube-ASL baselines
[53], we linearly project 85 3D MediaPipe Holistic [32, 18] landmarks into the
encoder, with one soft token for each frame of input. Unlike YouTube-ASL’s
baselines, we feed the input frames in at full (30 Hz) frame rate by default,
rather than half; we use up to 256 frames of input and 256 characters of
output and decode greedily with a beam size of 5. We train each run using 32
TPUv3 with a batch size of 64 and Adafactor optimizer with base learning rate
0.001 for up to 200k steps per run (or convergence), which takes up to 16
hours.

We report character error rate (CER), implemented as length-normalized
Levenshtein distance [31] using TensorFlow’s implementation [3], as well as
top-1 accuracy (_i.e._ , the fraction of examples that are transcribed
perfectly). We select checkpoints based on CER on the validation set. In
practice, the sampling-based metrics plateau without apparent overfitting, so
checkpoint selection is not especially sensitive.

See Figure 6 for a full table of quantitative results; see Figure 7 for a
qualitative sample of outputs. Our baseline achieves 11.1% CER and 52.9% top-1
accuracy on the FSboard test set. This baseline surpasses the best score
(16.4% CER) set in a Kaggle competition that we hosted based on FSboard [5],
though the participants were limited in terms of model size and runtime. See
the final leaderboard for descriptions of many more baseline methods. The main
difference is that, as far as we can tell, the top submissions did not use
pretrained language models but rather trained models with new, custom
architectures on FSboard only.

Our baseline is also substantially better than the 37.7% CER achieved by
ChicagoFSWild+’s baselines [6].333We are unable to evaluate our own models on
ChicagoFSWild+ due to licensing. Results obviously cannot be directly compared
across test sets in different domains, but it speaks to a combination of our
dataset’s increased size and choice of domain (including the use of new
footage from high-quality selfie cameras, rather than crops of potentially
low-resolution web videos). Our baseline results are even better than
ChicagoFSWild(+)’s references for human performance at 17.3% (Wild) and 13.9%
(Wild+), respectively. This result is because, as they note, the datasets are
mined as clips within longer signing videos, and the ground truth annotators
have access to broader context but the recognizer being tested does not. While
semantic context helps to decode fingerspelling in general, the problem is
complicated by signers who systematically fingerspell faster and more sloppily
when licensed by the discourse context [42]; to some degree attempting to
transcribe isolated fingerspelled subclips may be doomed [51]. We sidestepped
this issue by eliciting new data in the same (isolated) context as the desired
task, rather than using clips from preexisting longform data.

We ablate several factors that contribute to our baseline’s performance:

#### Pretraining.

Finetuning from the pretrained ByT5 checkpoint rather than the randomly
initialized architecture makes a massive difference in ultimate performance
(11.1% vs. 33.8% CER), and also gives much faster convergence (most of the way
by 30k steps, vs. at least 200k).

#### Model size.

We try scaling from ByT5 Small (300M) to ByT5 Base (580M), but quality
decreases. We assume that this dataset is not large enough to warrant the
extra modeling capacity, and the model overfits to the target distribution too
easily. Models even smaller than ByT5 Small might perform better, but it is
the smallest available model in its family.

#### Frame rate.

In practice, MediaPipe Holistic is the performance bottleneck for running sign
language applications on device, especially for devices that are not quite
cutting edge. We ablate frame rate to show that—as expected—quality degrades
monotonically with reduced frame rate, but 15 Hz still performs pretty well
(11.1% vs. 11.8% CER).

#### Holistic components.

Likewise, we can improve on-device performance by removing some of the
component models of MediaPipe Holistic (which consists of Hands, Pose, and
Face). Unlike other aspects of sign language, the meaning of fingerspelling
can be read purely from the shape of the hands, which makes this test more
principled than it would be in other contexts. Removing the face causes slight
degradation (11.1% to 12.0% CER), presumably due to the loss of lipreading
cues (which different signers use to varying extents), and removing pose has
seemingly no effect. It is possible that this gap could grow with more data,
if FSboard is not large enough to learn the relevant features.

Model | CER ($\downarrow$) | Top-1 Accuracy ($\uparrow$)
---|---|---
Baseline | 11.1 | 52.9
Pretrained | (11.1) | (52.9)
Scratch | 33.8 | 17.9
ByT5 Small | (11.1) | (52.9)
ByT5 Base | 13.3 | 49.1
30 Hz | (11.1) | (52.9)
30/2 Hz | 11.8 | 51.8
30/3 Hz | 13.4 | 48.2
30/4 Hz | 14.6 | 45.1
30/6 Hz | 20.0 | 33.4
30/8 Hz | 27.1 | 22.2
30/16 Hz | 64.0 | 0.9
30/32 Hz | 88.7 | 0.0
Holistic | (11.1) | (52.9)
–Face | 12.0 | 50.6
–Face –Pose | 12.5 | 49.7
Figure 6: Character error rate (CER, $\downarrow$) and top-1 accuracy ($\uparrow$) for FSboard fingerspelling recognition baselines. We provide several ablations with respect to our best-performing baseline (which uses 30 Hz MediaPipe Holistic (Hands+Pose+Face) landmarks finetuned into ByT5 Base): the effect of using pretrained language knowledge vs. training the architecture from scratch on FSboard only, building off ByT5 Small (300M) vs. Base (580M), reducing frame rates, and removing components of Holistic tracking. | Target | Prediction
---|---|---
Random | hubert avalos | elbert avalos
135-433-9049 | 135-433-9049
870055 sunset creek court | 870055 sunset creek court
+43-795-19-03-4208 | +43-795-19-03-4208
www.rehanfyzio.sk | www.rohanfyzio.sk
a131003/iandrade82 | a131003/iandrade82
eugene or | eugene or
331 super chief | 331 super chief
nashville tennessee | nashvelle tenssee
/passeig_de_maragall | /passigo-de-marsgoll
https://www.rauschenbach.de | https://www.rauschenbach.de
5225 everette mcclerran | 25225 everett mecclar road
+95-40-860-061-646 | +95-40-860-061-647
Failures | sparks nv | sparks.net
www.tttvw.com/lemoyne-pa | www.tt26.com/lenoyne-p
2786 lily xing | 78 william g
7806 skunk creek road | 378606 skunk creek road
+54-5828-275-06 | 7158 twp 2303
newark new jersey | newton jussey
Figure 7: Qualitative examples of our baseline’s predictions on the FSboard
validation set. Note that these phrases, like all in the validation set, are
unseen in the training set. “Random” examples are sampled without
cherrypicking, and “failures” are a selection of those with the worst errors.
For example, for “tttvw.com”, the fingershapes for “vw” and “two six” (not
twenty six) look identical.

##  5 Limitations

Beyond the intentional limitations in scope of the problem (tackling American
Sign Language fingerspelling recognition for a mobile keyboard use case),
FSboard has a number of areas for improvement in both data and modeling.

Our phrase set is a mixture of several relatively narrow domains, and even
within those domains the phrases follow some patterns due to the way we
synthetically generated them. An independent test set that is based on real
queries, rather than being constructed from the same synthetic grammar as the
training set (even if the phrases are unique) would give a more robust
understanding of the dataset/model’s performance and inform future data
collection efforts. We have also observed some considerations specific to the
mobile keyboard application that were underexplored in our collection because
they are not typically important for fingerspelling. One example is
capitalization. Signers only distinguish capital from lowercase letters in
rare circumstances where it is contextually relevant, but capitalization is
more important for text entry and should be elicited intentionally. Special
characters and differences in punctuation like hyphens and underscores are
also important but relatively rare/nonstandardized in signing generally.

In terms of modeling, while MediaPipe Holistic handles the vision aspects of
fingerspelling recognition in a way that is performant on device, prior work
has found limitations in the accuracy of current pose models [37] (though many
of the failure modes relate to interaction between body parts, which is less
relevant for fingerspelling). Future work should explore direct modeling of
video input, as in B. Shi and Livescu [6, 7], but for the mobile on-device
setting.

##  6 Conclusion

In this paper we introduced FSboard, the largest ASL fingerspelling dataset to
date by a factor of $>$10x. Informed by a participatory approach that
prioritizes real yet tractable needs of Deaf/Hard of Hearing users, FSboard
focuses narrowly on a mobile text entry use case to enable signers to
fingerspell short phrases and pieces of information as an analogue to faster
text entry techniques (as gesture/swipe keyboards are to two thumb typing on
smartphones) as opposed to speech recognition (for which full sign recognition
would be the analogue). Our baseline achieves 11.1% CER on FSboard’s test set
(with unique phrases and signers) and degrades minimally with compromises to
frame rate and body tracking that could help maintain real-time on-device
performance. We hope that these results (or those achieved by future modeling
work on the dataset) will prove high enough quality to be useful in practical
applications, and serve as a stepping stone on the way to more generally
capable sign language technology.

## Ethics Statement

The signers who participated in the data collection for FSboard were each paid
approximately $300 for providing 1000 fingerspelled phrases (which typically
required 8-12 hours) and consented to their videos being published for a
public dataset. Some participants were paid twice, once for the MacKenzie
phrase set and once for the addresses, phone numbers, etc. phrase set.

DPAN is a non-profit Deaf media company whose employees’ primary language is
ASL. They recruited and consented the contributors to the dataset. While names
are not affiliated with any of the videos, it was clear in the consent process
that participants’ faces would be identifiable and that the dataset would be
public.

While we release the underlying data with faces unblurred because mouthing can
be important for fingerspelling recognition, we ask that dataset users blur
the signers’ faces when including examples in publications (as we do in this
paper). Dataset users should not attempt to infer the signers’ personal
identities or use their likenesses to generate and publish other content
(deepfakes).

Given the sociohistorical context surrounding sign language technology and
perceptions of fingerspelling, it is important to emphasize that
fingerspelling recognition/transcription is not sign language translation.
Fingerspelling is an important part of ASL, but ultimately just a part of the
language. Please do not exaggerate the scope of this dataset or task in any
follow-up work.

## Acknowledgements and Disclosure of Funding

We would like to thank all the signers who contributed their data to the
project, and Michaela Jitaru and Nathan Qualls at DPAN for their contributions
to data collection logistics. Thanks to the Kaggle team (Sohier Dane, Glenn
Cameron, Mark Sherwood, Ashley Chow, and Phil Culliton) for all their advice
on how to best create useful datasets. We also thank Chris Dyer for giving
feedback on drafts of this paper and Caroline Pantofaru for institutional
support. Funding for this dataset is from Google, Inc. DPAN is a non-profit.

## References

  * UN [2021] International day of sign languages, 2021.  URL https://www.un.org/en/observances/sign-languages-day.
  * WHO [2022] Deafness and hearing loss, 2022.  URL https://www.who.int/health-topics/hearing-loss#tab=tab_1.
  * Abadi et al. [2015] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  URL https://www.tensorflow.org/.  Software available from tensorflow.org.
  * Abner et al. [2024] Natasha Abner, Grégoire Clarté, Carlo Geraci, Robin J Ryder, Justine Mertz, Anah Salgat, and Shi Yu.  Computational phylogenetics reveal histories of sign languages.  _Science_ , 383(6682):519–523, 2024.
  * Ashley Chow [2023] Manfred Georg Mark Sherwood Phil Culliton Sam Sepah Sohier Dane Thad Starner Ashley Chow, Glenn Cameron.  Google - american sign language fingerspelling recognition, 2023.  URL https://kaggle.com/competitions/asl-fingerspelling.
  * B. Shi and Livescu [2019] J. Keane D. Brentari G. Shakhnarovich B. Shi, A. Martinez Del Rio and K. Livescu.  Fingerspelling recognition in the wild with iterative visual attention.  _ICCV_ , October 2019.
  * B. Shi and Livescu [2018] J. Keane J. Michaux D. Brentari G. Shakhnarovich B. Shi, A. Martinez Del Rio and K. Livescu.  American sign language fingerspelling recognition in the wild.  _SLT_ , December 2018.
  * Bhardwaj et al. [2024] Khushi Bhardwaj, David Martin, Rajandeep Singh, Gururaj Deshpande, Matthew So, William Neubauer, and Thad Starner.  Popsignai: Using sign language recognition to improve american sign language learning in novice signers.  _IMWUT (in submission)_ , 2024.
  * Bragg et al. [2019] Danielle Bragg, Oscar Koller, Mary Bellard, Larwan Berke, Patrick Boudreault, Annelies Braffort, Naomi Caselli, Matt Huenerfauth, Hernisa Kacorri, Tessa Verhoef, Christian Vogler, and Meredith Ringel Morris.  Sign language recognition, generation, and translation: An interdisciplinary perspective.  In _The 21st International ACM SIGACCESS Conference on Computers and Accessibility_ , ASSETS ’19, page 16–31, New York, NY, USA, 2019. Association for Computing Machinery.  ISBN 9781450366762.  doi: 10.1145/3308561.3353774.  URL https://doi.org/10.1145/3308561.3353774.
  * Bragg et al. [2021a] Danielle Bragg, Naomi Caselli, Julie A Hochgesang, Matt Huenerfauth, Leah Katz-Hernandez, Oscar Koller, Raja Kushalnagar, Christian Vogler, and Richard E Ladner.  The fate landscape of sign language ai datasets: An interdisciplinary perspective.  _ACM Transactions on Accessible Computing (TACCESS)_ , 14(2):1–45, 2021a.
  * Bragg et al. [2021b] Danielle Bragg, Naomi Caselli, Julie A. Hochgesang, Matt Huenerfauth, Leah Katz-Hernandez, Oscar Koller, Raja Kushalnagar, Christian Vogler, and Richard E. Ladner.  The fate landscape of sign language ai datasets: An interdisciplinary perspective.  _ACM Transactions on Accessible Computing_ , 14(2), July 2021b.  URL https://www.microsoft.com/en-us/research/publication/the-fate-landscape-of-sign-language-ai-datasets-an-interdisciplinary-perspective/.
  * Bureau [2019] United States Census Bureau.  Tiger: Topologically integrated geographic encoding and referencing data (roads), 2019.  URL https://www2.census.gov/geo/tiger/TIGER2019/ROADS/.
  * Desai et al. [2023] Aashaka Desai, Lauren Berger, Fyodor O. Minakov, Vanessa Milan, Chinmay Singh, Kriston Pumphrey, Richard E. Ladner, Hal Daumé III au2, Alex X. Lu, Naomi Caselli, and Danielle Bragg.  Asl citizen: A community-sourced dataset for advancing isolated sign language recognition, 2023.
  * Duarte et al. [2021] Amanda Duarte, Shruti Palaskar, Lucas Ventura, Deepti Ghadiyaram, Kenneth DeHaan, Florian Metze, Jordi Torres, and Xavier Giro i Nieto.  How2sign: A large-scale multimodal dataset for continuous american sign language, 2021.
  * Erard [2017] Michael Erard.  Why sign-language gloves don’t help deaf people.  _The Atlantic_ , Nov 2017.
  * Fenlon and Wilkinson [2015] Jordan Fenlon and Erin Wilkinson.  Sign languages in the world.  _Sociolinguistics and deaf communities_ , 1:5, 2015.
  * Ghanem et al. [2017] Sakher Ghanem, Christopher Conly, and Vassilis Athitsos.  A survey on sign language recognition using smartphones.  In _Proceedings of the 10th International Conference on PErvasive Technologies Related to Assistive Environments_ , pages 171–176, 2017\.
  * Grishchenko and Bazarevsky [2020] Ivan Grishchenko and Valentin Bazarevsky.  Mediapipe holistic - simultaneous face, hand and pose prediction, on device, Dec 2020.  URL https://ai.googleblog.com/2020/12/mediapipe-holistic-simultaneous-face.html.
  * Gulati [2018] Sanjay Gulati.  Language deprivation syndrome.  In _Language deprivation and deaf mental health_ , pages 24–53. Routledge, 2018.
  * Hall et al. [2016] Matthew L. Hall, Inge-Marie Eigsti, Heather Bortfeld, and Diane Lillo-Martin.  Auditory Deprivation Does Not Impair Executive Function, But Language Deprivation Might: Evidence From a Parent-Report Measure in Deaf Native Signing Children.  _The Journal of Deaf Studies and Deaf Education_ , 22(1):9–21, December 2016.  ISSN 1081-4159.  doi: 10.1093/deafed/enw054.  URL https://doi.org/10.1093/deafed/enw054.  _eprint: https://academic.oup.com/jdsde/article-pdf/22/1/9/8675438/enw054.pdf.
  * Hall et al. [2019] Matthew L Hall, Wyatte C Hall, and Naomi K Caselli.  Deaf children need language, not (just) speech.  _First Language_ , 39(4):367–395, 2019.
  * Hall [2017] Wyatte Hall.  What You Don’t Know Can Hurt You: The Risk of Language Deprivation by Impairing Sign Language Development in Deaf Children.  _Maternal and Child Health Journal_ , 21, May 2017.  doi: 10.1007/s10995-017-2287-y.
  * Hall et al. [2017] Wyatte Hall, Len Levin, and Melissa Anderson.  Language deprivation syndrome: a possible neurodevelopmental disorder with sociocultural origins.  _Social Psychiatry and Psychiatric Epidemiology_ , 52, June 2017.  doi: 10.1007/s00127-017-1351-7.
  * Hassan et al. [2023] Saad Hassan, Abraham Glasser, Max Shengelia, Thad Starner, Sean Forbes, Nathan Qualls, and Sam S. Sepah.  Tap to sign: Towards using american sign language for text entry on smartphones.  _Proc. ACM Hum.-Comput. Interact._ , 7(MHCI), sep 2023.  doi: 10.1145/3604274.  URL https://doi.org/10.1145/3604274.
  * Hill [2020] Joseph Hill.  Do deaf communities actually want sign language gloves?  _Nature Electronics_ , 3(9):512–513, 2020.
  * Humphries et al. [2012] Tom Humphries, Poorna Kushalnagar, Gaurav Mathur, Donna Jo Napoli, Carol Padden, Christian Rathmann, and Scott R Smith.  Language acquisition for deaf children: Reducing the harms of zero tolerance to the use of alternative approaches.  _Harm Reduction Journal_ , 9(1):1–9, 2012.
  * Humphries et al. [2019] Tom Humphries, Poorna Kushalnagar, Gaurav Mathur, Donna Jo Napoli, Christian Rathmann, and Scott Smith.  Support for parents of deaf children: Common questions and informed, evidence-based answers.  _International journal of pediatric otorhinolaryngology_ , 118:134–142, 2019.
  * Johnston and Schembri [2010] Trevor Johnston and Adam Schembri.  Variation, lexicalization and grammaticalization in signed languages.  _Langage et société_ , 131(1):19–35, 2010\.
  * Keane et al. [2012] Jonathan Keane, Diane Brentari, and Jason Riggle.  Coarticulation in asl fingerspelling.  In _Proceedings of the North East Linguistic Society_ , volume 42, 2012.
  * Kim et al. [2016] Taehwan Kim, Jonathan Keane, Weiran Wang, Hao Tang, Jason Riggle, Gregory Shakhnarovich, Diane Brentari, and Karen Livescu.  Lexicon-free fingerspelling recognition from video: Data, models, and signer adaptation, 2016.
  * Levenshtein [1966] Vladimir Levenshtein.  Binary codes capable of correcting deletions, insertions, and reversals, 1966.
  * Lugaresi et al. [2019] Camillo Lugaresi, Jiuqiang Tang, Hadon Nash, Chris McClanahan, Esha Uboweja, Michael Hays, Fan Zhang, Chuo-Ling Chang, Ming Guang Yong, Juhyun Lee, Wan-Teh Chang, Wei Hua, Manfred Georg, and Matthias Grundmann.  MediaPipe: A framework for building perception pipelines, 2019.  URL https://arxiv.org/abs/1906.08172.
  * MacKenzie and Soukoreff [2003] I. Scott MacKenzie and R. William Soukoreff.  Phrase sets for evaluating text entry techniques.  In _CHI ’03 Extended Abstracts on Human Factors in Computing Systems_ , CHI EA ’03, page 754–755, New York, NY, USA, 2003. Association for Computing Machinery.  ISBN 1581136374.  doi: 10.1145/765891.765971.  URL https://doi.org/10.1145/765891.765971.
  * Miozzo and Peressotti [2022] Michele Miozzo and Francesca Peressotti.  How the hand has shaped sign languages.  _Scientific Reports_ , 12(1):11980, 2022.
  * Mitchell et al. [2006] Ross Mitchell, Travas Young, Bellamie Bachleda, and Michael Karchmer.  How many people use asl in the united states? why estimates need updating.  _Sign Language Studies_ , 6, 03 2006.  doi: 10.1353/sls.2006.0019.
  * Monk [2019] Ellis Monk.  Monk skin tone scale, 2019.  URL https://skintone.google.
  * Moryossef et al. [2021] Amit Moryossef, Ioannis Tsochantaridis, Joe Dinn, Necati Cihan Camgoz, Richard Bowden, Tao Jiang, Annette Rios, Mathias Muller, and Sarah Ebling.  Evaluating the immediate applicability of pose estimation for sign language recognition.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , pages 3434–3440, June 2021.
  * Napoli et al. [2015] Donna Jo Napoli, Nancy K Mellon, John K Niparko, Christian Rathmann, Gaurav Mathur, Tom Humphries, Theresa Handley, Sasha Scambler, and John D Lantos.  Should all deaf children learn sign language?  _Pediatrics_ , 136(1):170–176, 2015.
  * Neuhaus [2014] Rob Neuhaus.  Gibberish detector, 2014.  URL https://github.com/rrenaud/Gibberish-Detector.
  * Padden and Gunsauls [2003] Carol A Padden and Darline Clark Gunsauls.  How the alphabet came to be used in a sign language.  _Sign Language Studies_ , pages 10–33, 2003.
  * Palin et al. [2019] Kseniia Palin, Anna Maria Feit, Sunjun Kim, Per Ola Kristensson, and Antti Oulasvirta.  How do people type on mobile devices? observations from a study with 37,000 volunteers.  In _Proceedings of the 21st International Conference on Human-Computer Interaction with Mobile Devices and Services_ , pages 1–12, 2019\.
  * Patrie and Johnson [2011] Carol J Patrie and Robert E Johnson.  _RSVP: Fingerspelled word recognition through rapid serial visual presentation_.  2011\.
  * Power et al. [2020] Justin M Power, Guido W Grimm, and Johann-Mattis List.  Evolutionary dynamics in the dispersal of sign languages.  _Royal Society Open Science_ , 7(1):191100, 2020\.
  * Quinto-Pozos [2010] David Quinto-Pozos.  Rates of fingerspelling in american sign language.  In _Poster presented at 10th Theoretical Issues in Sign Language Research conference, West Lafayette, Indiana_ , volume 30, 2010.
  * Raffel et al. [2020] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer, 2020.
  * Reyal et al. [2015] Shyam Reyal, Shumin Zhai, and Per Ola Kristensson.  Performance and user experience of touchscreen and gesture keyboards in a lab setting and in the wild.  In _Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems_ , pages 679–688, 2015.
  * Rust et al. [2024] Phillip Rust, Bowen Shi, Skyler Wang, Necati Cihan Camgöz, and Jean Maillard.  Towards privacy-aware sign language translation at scale, 2024.
  * [48] Sahir Shahryar, Manfred Georg, and Matthew So.  Record these hands android app.  URL https://github.com/Accessible-Technology-in-Sign/RecordTheseHands.
  * Shi et al. [2022] Bowen Shi, Diane Brentari, Greg Shakhnarovich, and Karen Livescu.  Open-domain sign language translation learned from online video, 2022\.
  * Starner et al. [2023] Thad Starner, Sean Forbes, Matthew So, David Martin, Rohit Sridhar, Gururaj Deshpande, Sam Sepah, Sahir Shahryar, Khushi Bhardwaj, Tyler Kwok, Daksh Sehgal, Saad Hassan, Bill Neubauer, Sofia Anandi Vempala, Alec Tan, Jocelyn Heath, Unnathi Utpal Kumar, Priyanka Vijayaraghavan Mosur, Tavenner M. Hall, Rajandeep Singh, Christopher Zhang Cui, Glenn Cameron, Sohier Dane, and Garrett Tanzer.  Popsign ASL v1.0: An isolated american sign language dataset collected via smartphones.  In _Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track_ , 2023.  URL https://openreview.net/forum?id=yEf8NSqTPu.
  * Tanzer et al. [2024] Garrett Tanzer, Max Shengalia, Ken Harrenstien, and David Uthus.  Reconsidering sentence-level sign language translation, 2024.
  * Tarrés et al. [2023] Laia Tarrés, Gerard I. Gállego, Amanda Duarte, Jordi Torres, and Xavier Giró i Nieto.  Sign language translation from instructional videos, 2023.
  * Uthus et al. [2023] David Uthus, Garrett Tanzer, and Manfred Georg.  Youtube-asl: A large-scale, open-domain american sign language-english parallel corpus, 2023.
  * Xue et al. [2022] Linting Xue, Aditya Barua, Noah Constant, Rami Al-Rfou, Sharan Narang, Mihir Kale, Adam Roberts, and Colin Raffel.  Byt5: Towards a token-free future with pre-trained byte-to-byte models, 2022.
  * Yanovich et al. [2016] Polina Yanovich, Carol Neidle, and Dimitris Metaxas.  Detection of major ASL sign types in continuous signing for ASL recognition.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16)_ , pages 3067–3073, Portorož, Slovenia, May 2016. European Language Resources Association (ELRA).  URL https://www.aclweb.org/anthology/L16-1490.
  * Zhai and Kristensson [2012] Shumin Zhai and Per Ola Kristensson.  The word-gesture keyboard: reimagining keyboard interaction.  _Communications of the ACM_ , 55(9):91–101, 2012\.


# Horospherical random graphs and lockdown strategies

Indira Chatterji  Indira Chatterji, LJAD, Université Côte d’Azur, France
<EMAIL_ADDRESS>and  Austin Lawson  Austin Lawson, University of
Tennessee, USA<EMAIL_ADDRESS>
###### Abstract.

Expanders are sparse graph that are strongly connected, where connectivity is
quantified using eigenvalues of the adjacency matrix, and sparsity in terms of
vertex valency. We give a model of random graphs and study their connectivity
and sparsity. This model is a particular case of soft geometric random graphs,
and allows to construct sparse graphs with good expansion properties, as well
as highly clustered ones. On those graphs, we study the speed at which random
walks spread in the graph, and visit all vertices. As an illustration, we
build a model for mainland France and study the spread of random walks under
several types of lockdown. Our experiments show that completely closing medium
and long distance travel to slow down the spread of a random walk is more
efficient than than local restrictions.

###### Contents

  1. 1 Introduction
  2. 2 Background on graphs
  3. 3 Description of the probabilistic graph
  4. 4 Related models
  5. 5 Application
    1. 5.1 Uniformly distributed vertices
    2. 5.2 A model for mainland France
  6. 6 Discussion on the findings and future work

##  1\. Introduction

A common way to model real life phenomena relies on graphs. Here we describe a
model where the edges of the graph represent possible routes a contaminant can
take to travel, and vertices represents possible sites to infect. A simple
random walk represents a theoretical immortal virus strain, and a self-
replicating random walk would model an actual spread if one includes a
replicating rate. In this work we aim to heuristically illustrate how the
underlying geometry of travels plays a crucial role in the spread of a
contaminant, as it is closely related to the conductance of the graph, which
governs the speed at which a simple random walk visits all the vertices.

Recall from the seminal work of Gromov in [6] that a metric space $(Y,d_{Y})$
is called hyperbolic if loosely speaking every geodesic triangle is uniformly
thin regardless of the size of that triangle. Example 1.8.A (b) on page 99 of
[6] allows to embed any metric space $(X,d)$ as a horosphere in a hyperbolic
metric space: a horosphere is a sphere centered at infinity. The construction
consists in adding scaled down layers of the original space thus creating
shortcuts in the metric space $(X,d)$, consisting in going up the layers to
travel. With this construction, sets that had a small boundary in $X$, have a
much larger one when embedded in the hyperbolic space.

We apply this idea to define a model of random graphs, that we call
horospherical random graphs, defined by growing layers of graphs and whose
limit is a particular case of soft geometric random graphs. Loosely speaking,
we start with a metric space, choose vertices using some distribution, and
then start at the first level by adding edges between points that are not too
distant. Then at the second level, we add edges between points that are
further away, etc. After a few levels, those graphs start to exhibit good
expanding properties, in the sense that a random walk is very quick to visit
all the vertices.

Modelling our random graphs according to the population density of a country
(we worked on mainland France for our application in Section 5), the edges
represent possible routes that people can take, and hence the paths a virus
can use to spread. Different layers of our sequence of graphs illustrate
several confinement strategies, giving very different rates at which a random
walk visits all the vertices.

Acknowledgements: The authors thank Laurent Saloff-Coste for the reference
[10], Goulnara Arzhantseva for discussions and references [12], [8] and [11]
as well as Patricia Reynaud-Bouret for interesting conversations and
suggesting to look at the Small World features of horospherical graphs. The
authors also thank CNRS for making this collaboration materialize.

##  2\. Background on graphs

Recall that a graph $\Gamma$ is the data of a set $V$ of vertices and
$E\subseteq V\times V$. Here we will assume our graphs to be undirected
simplicial and connected. The adjacency matrix $A=A_{(i,j)}$ of $\Gamma$ is an
$n\times n$ matrix, where $n=|V|$ with values 1 when $\\{i,j\\}\in E$ and 0
otherwise. For an undirected simplicial graph, $A$ is a symmetric matrix with
0’s on the diagonal. We further define the following

  1. (1)

The degree matrix $D=D_{(i,j)}$ is a diagonal matrix with $D_{(i,i)}$ equals
to the degree of the $i$-th vertex: $D_{(i,i)}=\sum_{j}A_{(i,j)}=d_{i}$

  2. (2)

The normalized adjacency matrix is given by $\overline{A}=AD^{-1}$.

  3. (3)

The laplacian is given by $L=D-A$.

  4. (4)

The normalized laplacian is given by
$\overline{L}=I-\sqrt{D^{-1}}A\sqrt{D^{-1}}$.

######  Definition 2.1.

For any two disjoint subsets of vertices $A,B\subseteq V$ , we denote
$E(A,B)=E\cap(A\times B\cup B\times A)$, that is the set of edges of $\Gamma$
with one extremity in $A$ and the other in $B$. We denote by
$\partial_{E}(A)=E(A,A^{c})$, which are edges of the boundary of $A$. For a
subset $A$ in $V$ we define its volume by $\nu(A)=\sum_{x\in A}\nu(x)$, where
$\nu(x)=|\\{y\in V|\\{x,y\\}\in E\\}|$ is the degree of the vertex $x$. Hence
$\nu(\Gamma)=\sum_{x\in V}\nu(x)$ is the total volume of the graph. The
conductance of the graph $\Gamma$ is given by

$\varphi(\Gamma)=\min\\{\frac{|\partial_{E}(S)|}{\min\\{\nu(S),\nu(V\setminus
S)\\}}|\emptyset\not=S\subset V\\}$

The conductance is a measure on how well connected the graph $\Gamma$ is. This
quantity is difficult to compute, but it is related to the first non-trivial
eigenvalue of the normalized laplacian as follows (see for instance Theorem
14.4 of [10] or Fact 6. page 5 of [3])

######  Theorem 2.2 (Cheeger inequality).

Let $\Gamma$ be a connected graph and let $\lambda_{1}$ be the first non-zero
eigenvalue of its normalized laplacian. Then

$\frac{\lambda_{1}}{2}\leq\varphi(\Gamma)\leq\sqrt{2\lambda_{1}}.$

######  Remark 2.3.

Many references (such as for instance [9]) use the expansion constant (or
sometimes called Cheeger constant), which is defined by

$h(\Gamma)=\min\\{\frac{|\partial_{E}(A)|}{|A|}\hbox{ such that
}\emptyset\not=A\subset V,\ 2|A|\leq|V|\\}$

with the convention that $h(\Gamma)=\infty$ if $\Gamma$ has at most one
vertex. The expansion constant measures how difficult it is to separate the
graph in two pieces of roughly the same size. Given its definition as a
minimum over subsets, the computation of the expansion constant is notoriously
difficult to compute. It is also related to the the smallest non-zero
eigenvalue of the normalized laplacian, in a similar way as the conductance
is.

We will be interested in simple random walks on connected graphs, a walk going
to each neighbor with equal probability at each step.

######  Definition 2.4.

A simple random walk on $\Gamma$ is a sequence $(X_{n})_{n\geq 0}$ of
$V$-valued random variables (measurable functions) defined on a common
probability space $(\Omega,\Sigma,P)$, with joint distribution satisfying that
for any $n\geq 0$, and any vertices $x_{0},\dots,x_{n}$ and $y\in V$, with
$\\{x_{i},x_{i+1}\\}\in E$, then

$P\\{X_{n+1}=y|(X_{n},\dots,X_{0})=(x_{n},\dots,x_{0})\\}=P\\{X_{n+1}=y|X_{n}=x_{n}\\}$

with

$P\\{X_{n+1}=y|X_{n}=x_{n}\\}=\left\\{\begin{array}[]{cc}0&\hbox{ if
}\\{x_{n},y\\}\not\in E\\\ \frac{1}{|\\{x\in V|\\{x_{n},x\\}\in E\\}|}&\hbox{
if }\\{x_{n},y\\}\in E\end{array}\right.$

This means that the walk at time $n+1$ doesn’t depend on what happened on the
$n-1$ first steps, only on its position in the graph at time $n$.

If the graph is not bipartite, then the walker is, after a time $n$ large
enough, as likely to be located at any of the vertices of the graph,
independently of the starting point or of the steps taken to get there. We say
that the walk converges to the uniform distribution, and $n$, which is the
speed at which this convergence occurs, is related to the first eigenvalue
$\lambda_{1}$ as follows (see [3] or [10])

$\left|P(X_{n}=x)-\frac{\nu(x)}{N}\right|\leq\sqrt{\frac{\nu(x)}{v_{-}}}|\lambda_{1}-1|^{n}$

Intuitively, this means that the walk could be anywhere in the graph, hence
has been everywhere in the graph.

######  Definition 2.5.

The clustering coefficient at a vertex $v_{i}\in V$ is given by

$C_{i}=2\sum_{j,k}\frac{A_{(i,j)}A_{(j,k)}A_{(k,i)}}{d_{i}(d_{i}-1)}$

and the average clustering coefficient is the mean value over all vertices, of
local clustering coefficients. The clustering coefficient at a vertex $v_{i}$
counts the proportion of closed paths of length 3 at $v_{i}$ among all
neighbors of $v_{i}$.

######  Remark 2.6.

Clustering coefficients are used to give a measure of Small World, those are
graphs with a large amount of nodes, that are sparse , with a large average
clustering coefficient and small average distances between pairs of points in
the graph, see [5] or [14].

##  3\. Description of the probabilistic graph

The general settings for constructing our horospherical random graphs is a
particular case of soft random geometric graphs described by Penrose [12], and
is described in the following.

######  Definition 3.1 (Horospherical random graphs).

Suppose that $(X,d)$ is a discrete metric space (for instance obtained from a
finite subset of $\mathbb{R}^{n}$ with the induced Euclidean metric from
$\mathbb{R}^{n}$). Moreover, suppose that $r_{1}<r_{2}<\ldots\in\mathbb{R}$ is
an increasing sequence of real numbers and
$\phi=(p_{1},p_{2}\ldots),p_{i}\in[0,1]$ is any sequence of real numbers in
the unit interval. This defines a piece-wise constant function $\phi$, taking
the value $p_{k}$ in the interval $[r_{k},r_{k+1})$, for any $k\in\mathbb{N}$,
called connection function. We define a collection of random graphs
$\mathcal{G}=\\{\Gamma_{n}\\}_{n=1}^{\infty}$ in the following way

  * •

$\Gamma_{1}=(X,E_{1})$ where for all $x\in X$ and for all $x^{\prime}\in X\cap
N_{r_{1}}(x)$, the edge $\\{x,x^{\prime}\\}$ is added to $E_{1}$ with
probability $p_{1}$.

  * •

$\Gamma_{n}=(X,E_{n})$ where the edge set is generated randomly as follows:

    * –

$E_{n-1}\subseteq E_{n}$

    * –

For all $x\in X$ and for all $x^{\prime}\in X\cap\left(N_{r_{n}}(x)\setminus
N_{r_{n-1}}(x)\right)$, the edge $\\{x,x^{\prime}\\}$ is added to $E_{n}$ with
probability $p_{n}$.

The collection $\mathcal{G}$ is what we call horospherical random graph, and
for each $i\in{\bf N}$, the graph $\Gamma_{i}$ is the $i$-th layer, or the
graph at height $i$. If the connection function $\phi$ is finitely supported,
then the collection stabilizes at $\Gamma_{n}$ for $n$ large enough.

######  Remark 3.2.

If $\Gamma_{1}$ is connected, then $\Gamma_{n}$ is connected for all $n>1$.
Moreover, from the definition of conductance it follows that
$\varphi(\Gamma_{i})\leq\varphi(\Gamma_{j})$ when $i\leq j$ and according to
[4] Theorem 2.1 $\lambda_{k}(\gamma_{j})\geq\lambda_{k}(\Gamma_{i})$ when
$j\geq i$, with equality when the eigenvalues are 0. Our goal will be to study
the behavior of $\lambda_{1}(\Gamma_{i})$ as $i$ increases.

######  Remark 3.3.

Our sequence of horospherical random graphs can be viewed in the more general
following setting, where we start with $(X,d)$ a metric space, with the
following additional data.

  * •

Let $\phi:\mathbb{R}^{+}\to[0,1]$ be a measurable function, called connection
function.

  * •

For $r>0$, define $W_{r}=\\{(x,y)\in X\times X\mid d(x,y)=r\\}$. This is the
cylinder of diameter $r$ around the diagonal in $X\times X$.

  * •

Define $\hat{W}_{r}\subset W_{r}$ to be a random subset where each
$w\in\hat{W}_{r}$ appears with probability $\phi(r)$.

    * –

Technically, we can see this is ($|W_{r}|$) samples from a
Bernoulli($\phi(r)$) distribution

    * –

Also, we can view $\hat{W}:\mathbb{R}^{+}\to X\times X$ where
$r\mapsto\hat{W}_{r}$.

  * •

Define $E_{r}=\bigcup_{r^{\prime}\leq r}\hat{W}_{r}$.

  * •

The graph $\Gamma_{r}=(X,E_{r})$ is the graph obtained at height $r$.

For modelling purpose and to recover our definition and several models from
the literature, we restrict our attention to a discretization of the above
construction, done as follows. Choose $h>0$, which will be the step size and
define $\bar{p}:\mathbb{R}^{+}\to[0,1]$ to be the step (i.e. piece-wise
constant) function obtained from $p$ above on the intervals $[kh,(k+1)h)$,
where $k\in\mathbb{N}$ by

$\int_{kh}^{(k+1)h}p(t)dt$

and we recover the $i$-th layer $\Gamma_{i}=E_{r_{i}}$ from Definition 3.1.

##  4\. Related models

Let us first notice that for a finitely supported connection function $p$, or
for a finite diameter metric space $(X,d)$ the sequence of graphs stabilizes
after some height.

The random Erdös-Rényi graphs are instances of horospherical random graphs in
case where the parameter $p$ is a constant function. The first level of a
horospherical random graph is a geometric random graph, see [8] or [11] for
related studies. The limiting graph in our horospherical random graphs are
instances of soft geometric random graphs studied by Penrose [12]. For us,
keeping track of the layers is a way of understanding how the long distance
connections influence the behavior of the first eigenvalue and hence of the
conductance.

When $X\subset\mathbb{R}^{d}$ our horospherical random graphs $\Gamma_{n}$ are
instances of geometric inhomogeneous random graphs studied by [2], also called
spatial inhomogeneous random graphs in [13], in the particular case where all
the weights at vertices are constants. If the metric space one starts with, is
the hyperbolic plane in the Poincaré disk model, horospherical random graphs
are generalizations of hyperbolic random graphs: we do not require the
underlying metric space to be hyperbolic, but choosing the connection function
well, the resulting graph could be hyperbolic. In hyperbolic random graphs,
the connection function is a formula in terms of the hyperbolic distance, see
[7].

##  5\. Application

By using the first graphs in the sequence of graphs defined in Section 3, we
can produce a model that simulates the effects of lockdown measures taken
during a pandemic. Our model has two sets of parameters, a nondecreasing
sequence of distances $0\leq r_{1}\leq r_{2}\leq\ldots$ and a sequence of
probabilities $p_{1},p_{2},\ldots\in[0,1]$, giving a connection function
$\phi$. The distance $r_{i}$ represents the possible range of interaction and
the probability $p_{i}$ represents the probability of interaction between the
vertices. In this section, we produce simulations for two difference sets of
vertices and examine the resulting $\lambda_{1}$ values111Code for this
project available at:
https://gist.github.com/azlawson/a545b341f5621cabbb649e75a55a4fca.

###  5.1. Uniformly distributed vertices

For our first simulation, we will explore some statistical quantities for
horospherical random graphs with five different probability parameter
functions $p_{i}$ for $i=1,\ldots 5$. In this case, we generate a single
random set of 200 points sampled uniformly from an 8 by 8 square. For each
probability parameter and each point set, we generate 20 horospherical random
graphs by adding a level at each of 100 evenly spaced values of $r$ between 0
and $8\sqrt{2}$. For each level we recorded the values of $\lambda_{1}$,
maximum valency, average valency, and sparsity. Our goal is to explore the
similarities in the different choices of $p_{i}$ within and across the
different point sets as well as the variance in these selections. Figure 1
contains four plots, one for each of these statistics. Each plot contains the
average value considered along with a band of one standard deviation for each
probability parameter function. These functions consist of two constant
functions, $\phi_{1}(r)=0.5$ and $\phi_{2}(r)=1$, an affine function
$\phi_{3}(r)=\frac{-r}{8\sqrt{2}}+1$, an exponential $\phi_{4}(r)=e^{-r}$, and
$\phi_{5}(r)=\frac{\exp\\{-(r-\sqrt{32})^{2}/16\\}}{\sqrt{16\pi}}$, a normal
density with mean $\sqrt{32}$ and standard deviation $2$.

Figure 1. Four plots of graph properties over 5 different connection
functions. For each connection function and each property, the given property
was averaged over 20 iterations on a uniformly distributed set, then plotted
with a band of one standard deviation.

###  5.2. A model for mainland France

We construct a model of mainland France by selecting the most populated
metropolitan areas such as Paris, Toulouse, Bordeaux, Lyon, Strasbourg,
Nantes, Lille, and Côte d’Azur (comprised of Nice, Marseille, and Toulon),
using the picture from
Wikipedia222https://fr.wikipedia.org/wiki/Liste$\underline{\
}$des$\underline{\ }$aires$\underline{\ }$urbaines$\underline{\
}$de$\underline{\ }$France copied on an $8\times 8$ square. The vertices of
our graph sequence were drawn from bivariate normal distributions centered at
each of those cities. The number of points drawn from each city is
proportional to the population of the city relative to the population of
mainland France. Finally, we overlayed a grid of 60 by 60 points (so a mesh of
8/60 ¡0.15) to represent the distribution of the remaining population
throughout the country side, and will allow us to force all graphs to be
connected. Figure 2 depicts the resulting vertices, 6’000 dots, so that each
point is then roughly 10’000 people if we estimate mainland France population
by 60 million.

Figure 2. The vertex set $X$, obtained with a simulation of major metropolitan
areas of mainland France along with a grid of points representing the rest of
the population.

On this set of vertices, denoted by $X$, we compute several simulations with
four different connection functions, named $U,C,S$ and $I$, heuristically
depicting daily people movements in different situations, and that we now
describe. First, we consider the connection function given by

$U(r)=\begin{cases}1&r\leq 0.15\\\ 0.05&0.15<r\leq 0.3\\\ 0.03&0.3<r\leq 1\\\
0.02&1<r\leq 3\\\ 0.01&3<r\leq 10\\\ \end{cases}$

with the corresponding random graph $\Gamma_{U}=(X,E_{10})$. This corresponds
to a daily situation that we estimated very roughly using 2019 official data
available on-line 333https://www.ecologie.gouv.fr/statistiques-du-trafic-
aerien and
https://www.autorite-transports.fr/wp-content/uploads/2021/01/bilan-
ferroviaire-2019.pdf before any type of lockdown. Next, we consider the
connection function given by

$S(r)=\begin{cases}1&r\leq 0.15\\\ 0.1&0.15<r\leq 0.3\\\ 0.05&0.3<r\leq 1\\\
0.01&1<r\leq 3\\\ 0.005&3<r\leq 10\\\ \end{cases}$

with corresponding graph $\Gamma_{S}=(X,E_{10})$. This corresponds to some
soft travel restrictions, simulating the case where all means of travel are
open, but are operating at limited capacity. The connection function

$C(r)=\begin{cases}1&r\leq 0.15\\\ 0.05&0.15<r\leq 0.3\\\ 0.003&0.3<r\leq 1\\\
0.002&1<r\leq 3\\\ 0.001&3<r\leq 10\\\ \end{cases}$

corresponds to our estimates of long distance travels in France during the
2020 first lockdown, one of the hardest ones, where some 90 percent of
airplane activity was cancelled, with the corresponding random graph
$\Gamma_{C}=(X,E_{10})$. Finally the connection function

$I(r)=\begin{cases}1&r\leq 0.3\\\ 0&\hbox{otherwise}\end{cases}$

with corresponding graph $\Gamma_{I}=(X,E_{10})$. This corresponds to a
theoretical lockdown, where long distance travel is completely stopped but
locally, everything is widely open, without restrictions. In that way, travel
between cities is eventually possible, but takes place at a very slow pace.

We seek to compare these graphs through various statistics. Specifically, for
each graph we compute the first eigenvalue $\lambda_{1}$, Sparsity, Max
Valency, and Average Valency. Because $X$ is fixed and $p_{1}\equiv 1$, the
graph $\Gamma_{I}$ is not random, and the probability 1 for $r_{1}\leq 0.15$
on all the graphs is to ensure that those graphs are connected. However, the
next layers in the graphs $\Gamma_{U},\Gamma_{S}$ and $\Gamma_{C}$ are random;
thus, we choose to compute 20 iterations and average the relevant statistics.
The results are summarized in Table 1. We can see that the graphs are nearly
equal in Sparsity, except for $\Gamma_{C}$, the hard confinement graph which
is much more sparse than the three others and has significantly lower max and
average valency while its first eigenvalue $\lambda_{1}$ is roughly a third of
the ones in the unconfined graph $\Gamma_{U}$ and the lightly confined model
$\Gamma_{S}$. But comparing it to $\Gamma_{I}$, we notice that
$\lambda_{1}(\Gamma_{I})$ is $3.5\times 10^{-4}$, so several orders of
magnitude smaller than the other graphs. This indicates that random walks on
$\Gamma_{I}$ (and unsurprisingly on, $\Gamma_{U}$ and $\Gamma_{S}$) will
spread much faster than random walks on $\Gamma_{I}$.

To illustrate this, we consider two different types of random walks. First, we
simulate a simple random walk on the four graphs. For each graph, we generate
100 different 100-step random walks with a random starting points. For each
walk, we compute the average and maximum pairwise distances. These numbers
suggest that traveling long distances is much easier to achieve in the set up
for $\Gamma_{C}$ than for that of $\Gamma_{I}$. We summarize these numbers in
Table 2. Figure 3 illustrates an example walk resulting from the simulation.
We can see that, as expected, the walk for $\Gamma_{U}$ very quickly spreads
everywhere, while the walk for $\Gamma_{I}$ remains concentrated near its
inception. What is interesting is the fact that for $\Gamma_{S}$ and
$\Gamma_{C}$, the walk spreads pretty much everywhere as well.

| $\Gamma_{U}$ | $\Gamma_{S}$ | $\Gamma_{C}$ | $\Gamma_{I}$
---|---|---|---|---
$\lambda_{1}$ | 0.46 | 0.29 | 0.09 | 0.00035
Sparsity | 0.019 | 0.016 | 0.006 | 0.015
Max Valency | 280 | 278 | 178 | 470
Average Valency | 121 | 96 | 40 | 97
Clustering Coefficient | 0.06 | 0.08 | 0.19 | 0.62
Table 1. Various statistics for $\Gamma_{U},\Gamma_{S},\Gamma_{C}$ and $\Gamma_{I}$. | $\Gamma_{U}$ | $\Gamma_{S}$ | $\Gamma_{C}$ | $\Gamma_{I}$
---|---|---|---|---
Mean of mean distances | 3.07 | 2.87 | 2.57 | 0.27
St. dev. of mean distances | 0.23 | 0.35 | 0.63 | 0.20
Mean of max distances | 8.2 | 7.84 | 7.2 | 0.91
St. dev. of max distances | 0.43 | 0.53 | 0.64 | 0.49
Table 2. Various statistics for 100 walks on
$\Gamma_{U},\Gamma_{S},\Gamma_{C}$ and $\Gamma_{I}$ Figure 3. A simple random
walk on $\Gamma_{U},\Gamma_{S},\Gamma_{C}$ and $\Gamma_{I}$. Figure 4. A
replicating random walk simulation on $\Gamma_{U},\Gamma_{S},\Gamma_{C}$ and
$\Gamma_{I}$.

For another illustration, we compute a replicating random walk. The walk for
each graph begins with one replicant in the same starting location (near
Lille, on the top of the grid). The walk replicates after 10 steps for each
replicant visiting a node that has not been replicated before. This walk
proceeds for 100 steps. Figure 4 shows the initial positions of each replicant
node at the end of the replicating walk. Again, the difference in spread
between the different graphs are clear.

Finally, we explore the effect of the distance parameter, $r$ when $p\equiv
1$, which we will denote as $\Gamma(r)$. Clearly, as $r$ increases,
$\lambda_{1}(\Gamma(r))$ will increase as well. Figure 5 shows the behavior of
$\lambda_{1}(\Gamma(r))$ in relation to $r$. The orange line in the Figure is
$\lambda_{1}(\Gamma_{U})$, the green line is $\lambda_{1}(\Gamma_{S})$ and the
red line is $\lambda_{1}(\Gamma_{C})$, the lowest eigenvalue. It is
interesting to note that the $\lambda_{1}(\Gamma(r))=\lambda_{1}(\Gamma_{C})$
when $r\approx 2.3$. In our model, this equates to a distance of about 300 km,
or 180 miles.

Figure 5. A graph of $\lambda_{1}(\Gamma(r))$. The horizontal line are
$\lambda_{1}(\Gamma_{U}),\lambda_{1}(\Gamma_{S})$ and
$\lambda_{1}(\Gamma_{C})$.

##  6\. Discussion on the findings and future work

The presence of edges between far away points dramatically increases the speed
at which the random walk visits all the vertices of the graph. From the view
point of the random walks, completely shutting down medium and long distance
travel (which amounts to looking at low level graphs) is more efficient in
slowing down the spread of the walk than restricting local interactions. In
fact even with high local clustering coefficient, corresponding to a level one
graph with large edge probability, the random walk is much slower than in a
sparse graph with edges linking far away points.

Our findings show that completely cutting travels over 300 kilometers would
give a random walk much slower to spread than in a graph with strict local
confinement, amounting to low average valency. Of course, at small scale a
high local clustering coefficient would give a high local spread once the walk
has reached a location.

Low level graphs, with small first eigenvalue $\lambda_{1}$, also have small
conductance and are easy to cut into pieces of similar sizes, meaning that
clusters could be disconnected from the rest of the graph. In terms of random
walks, this partial confinement mitigates the damages: if the random walk is
slow enough, one can divide a graph in $n$ pieces $R_{1},\dots,R_{n}$ easily
disconnected by cutting relatively few edges. Compared to their sizes, the
$R_{i}$’s have small isoperimetric inequality, meaning that to isolate a piece
$R_{i}$ of the rest of the graph to trap the random walk there can be done
removing relatively few edges. This can be seen in the graph $\Gamma_{I}$,
where the replicating walk starting in Lille doesn’t spread beyond Paris,
whereas on $\Gamma_{U},\Gamma_{S}$ and even on $\Gamma_{C}$ it has spread
everywhere.

The impact of long distance travel in the spread of diseases is probably well-
known by specialists, and the mathematics described in this paper are very
classical, but the conclusions seem to be
controversial444https://www.icao.int/Newsroom/Pages/Update-on-ICAO-and-WHO-
Coronavirus-Recommendations.aspx, even if a scientific consensus along those
lines seems to emerge [1].

Obviously, comparing our model with actual data, making finer estimates and
more accurate models would be interesting and could provide interesting
information, but beyond our computing capacity.

## References

  * [1] Aniruddha Adiga, Srinivasan Venkatramanan, James Schlitt, Akhil Peddireddy, Allan Dickerman, Andrei Bura, Andrew Warren, Brian D Klahn, Chunhong Mao, Dawen Xie, Dustin Machi, Erin Raymond, Fanchao Meng, Golda Barrow, Henning Mortveit, Jiangzhuo Chen, Jim Walke, Joshua Goldstein, Mandy L Wilson, Mark Orr, Przemyslaw Porebski, Pyrros A Telionis, Richard Beckman, Stefan Hoops, Stephen Eubank, Young Yun Baek, Bryan Lewis, Madhav Marathe, and Chris Barrett.  Evaluating the impact of international airline suspensions on the early global spread of covid-19.  medRxiv, 2020.
  * [2] Karl Bringmann, Ralph Keusch, and Johannes Lengler.  Geometric inhomogeneous random graphs.  Theoretical Computer Science, 760:35–54, 2019.
  * [3] Steve Butler, Fan Chung, et al.  Spectral graph theory.  Handbook of linear algebra, page 47, 2006.
  * [4] D. M. Cvetković, M. Doob, and H. Sachs.  Spectra of Graphs. 3rd revised and enlarged edition. Heidelberg/Leipzig, Johann Ambrosius Barth Verlag, 1995.
  * [5] Richard Durrett.  Random graph dynamics, volume 200.  Cambridge university press Cambridge, 2007.
  * [6] Mikhael Gromov.  Hyperbolic groups.  In Essays in group theory, pages 75–263. Springer, 1987.
  * [7] Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter.  Random hyperbolic graphs: degree sequence and clustering.  In 39th International Colloquium on Automata, Languages, and Programming (ICALP), page 573–585, 2012.
  * [8] Mounia Hamidouche.  Spectral analysis of random geometric graphs.  PhD thesis, Université Côte d’Azur, 2020.
  * [9] Emmanuel Kowalski.  An introduction to expander graphs.  Société mathématique de France, 2019.
  * [10] David A Levin and Yuval Peres.  Markov chains and mixing times, volume 107.  American Mathematical Soc., 2017.
  * [11] Amy Nyberg.  The Laplacian spectra of random geometric graphs.  PhD thesis, University of Houston, 2014.
  * [12] Mathew D Penrose.  Connectivity of soft random geometric graphs.  The Annals of Applied Probability, 26(2):986–1028, 2016.
  * [13] Remco van der Hofstad, Pim van der Hoorn, and Neeladri Maitra.  Local limits of spatial inhomogeneous random graphs.  arXiv preprint arXiv:2107.08733, 2021.
  * [14] Jie Wu and Duncan J Watts.  Small worlds: the dynamics of networks between order and randomness.  Acm Sigmod Record, 31(4):74–75, 2002.