\resizebox{\linewidth}{!}{ \input {figures/huawei-mcs}}
\caption{In IMM, Alice's read of {\tt x} may happen before Bob's write to {\tt x}.}
%    In ARM, there is control dependency between Alice's reads of {\tt me->spin} and {\tt x}, but since these are two reads,
%    the ARM model allows them to be reordered;
%        therefore, the same reordering between
%        Alice's read of {\tt x} and Bob's write to {\tt x} may happen.
\label{fig:huawei-graph}
\end{minipage}
\end{figure}
Our next study case is concerned with the MCS lock implementation found in an internal Huawei product.
In this implementation, \sys\ identified a missing \acq\ barrier that causes serious data corruption problems.
We were able to reproduce the problem on real hardware and reported the bug along with a simple fix to the maintainers.
Here, we describe this issue to illustrate the challenges of porting x86 code to ARM, which is the reason why such a bug was introduced in the code base.
With the recent increased demand of software for ARM servers, we believe that similar bugs are going to become more and more common in production.

\paragraph{The bug on IMM.}
\Cref{fig:huawei-mcs} presents a slightly simplified version of the original MCS lock implementation.
The bug is a missing \acq\ barrier at the end of {\tt mcslock_acquire()}.
To understand the scenario, consider the execution graph in \cref{fig:huawei-graph},
where the critical section is a simple increment \verb|x++|,
Alice wants to enter, and Bob is inside the critical section.
Similarly to the DPDK bug, Bob sees Alice's node when releasing the lock and sets Alice's {\tt spin = 0}; this flag is called {\tt locked} in DPDK.
The first fence in Alice's \verb|mcslock_acquire| synchronizes with the fence in Bob's \verb|mcslock_release| due to the write and read of {\tt bob->next} field.
That establishes a happens-before relation marked with the dashed arrows in the figure.
The happens-before relation, however, does not specify whether Bob's critical-section execution happens before Alice's critical-section execution, or vice-versa.
In this execution graph, Alice and Bob run their critical sections concurrently and both read from the initial write to {\tt x}, causing one of the increments to be lost.
By introducing an \acq\ barrier in the reads of {\tt me->spin} or after them (\cref{fig:huawei-mcs}, Line~\ref{ln:huawei-loop}), Alice is guaranteed to execute her critical section after Bob.
Note that, although the ARM model also introduces control dependencies, reads of {\tt me->spin} and the read of{\tt x} inside the critical section of Alice, a reordering of these operations is not precluded because they are all read operations.

\paragraph{Discussion.}
Besides the barrier bug, some issues may be interesting to point out.
The developers that implemented this code opted in using compiler specific atomic operations.
We do not recommend their use because they hide the barrier mode used underneath.
In particular,
{\tt _sync_lock_test_and_set} has an \acq\ mode,
whereas {\tt _sync_val_compare_and_swap} has an \seqc\ mode.
Moreover, the developers overuse fences:
the {\tt smb_mb()} fence in \verb|mcs_acquire()|, Line~\ref{ln:huawei-useless-fence}, is redundant and can be eliminated.

%\subsection{seL4 CLH bug}
%\subsection{Musl 9 barriers}

\input{cases-qspinlock}

%\subsection{Discussion: lack of principle and fences}

% vim: ts=4 sts=4 sw=4 et

\pagebreak
\section{Optimized-code Evaluation}
\label{s:eval}

\newcommand{\plotwidth}{0.6}

In this section, we present details of the setup used in our ``optimized-code evaluation'' section.
Moreover, we discuss the results obtained with microbenchmarks in length.
See the full paper for results with real-world workloads~[24].

\subsection{Setup details}

\subsubsection{Evaluation platforms}
\label{subsub:eval-platforms}

We conduct our experiments in the following hardware platforms:

\begin{itemize}
\item a Huawei \textbf{TaiShan 200} (Model 2280)\footnoteurl{
rack server that has \texttt{128 GB} of RAM and 2 \textbf{Kunpeng 920-6426} processors, a HiSilicon chip
with \textbf{64} \texttt{ARMv8.2} 64-bit cores\footnoteurl{
totaling 128 cores running at a nominal 2.6 GHz frequency.
The identifier to denote this machine in this document is \texttt{taishan200-128c}.

\item a GIGABYTE \textbf{R182-Z91-00}\footnoteurl{
rack server that has \texttt{128 GB} of RAM and 2 \textbf{EPYC 7352} processors, an AMD chip
with \textbf{24} \texttt{x86\_64} cores\footnoteurl{
totaling 48 cores (96 if counting hyperthreading) running at a nominal 2.3 GHz frequency.
The identifier to denote this machine in this document is \texttt{gigabyte-96c}.
\end{itemize}

We installed on all these servers the Ubuntu 18.04.4 LTS (aarch64) operating system, with the following
Linux kernel version: \texttt{5.3.0-42-generic}.

\subsubsection{Environment setup}

To produce stable benchmark results on a kernel as complex as Linux, we took some precautions in terms of
environment configuration of our experiment target platforms.
We list here such precautions:

\begin{enumerate}
\item \textbf{Atomic types isolation.}
Linux and \sys each declare their own atomic types such as \texttt{atomic\_t} and \texttt{atomic64\_t}.
When writing the kernel benchmark module, to avoid name conflicts between Linux kernel headers and \sys library headers, we separated into different translation units the benchmark ``main'' code (where the entry point lies and where the kernel threads are created) from the lock primitives function definitions and data structures instantiations (where the contention loops are executed, see Section~\ref{subsub:eval-micro-details}).
Therefore, the ``main'' code of the benchmark kernel module could use the classic Linux headers for its needs while the \sys test units could include the \sys library headers (that define the required atomic types) and use from Linux only the primitives types (such as \texttt{uint32\_t} and the likes).
This technique also enables the possibility to benchmark individually module from the Linux kernel, such as the qspinlock located in \texttt{"linux/spinlock.h"} header.

\item \textbf{Thread to core affinity assignment.}
The benchmark module spawns as many \emph{kernel} threads as requested on the module invocation command.
To measure the multi-core overheads of the locks, these threads must be pinned on individual cores (both within the same NUMA nodes and on different NUMA nodes).
For this purpose, the Linux \texttt{kthread\_bind()} function is used.

\item \textbf{Operating frequency fixing.}
To avoid suffering from thermal effects, and thus the OS dynamically changing the operating frequency while the benchmark were running (and by doing so skewing our results), we fixed the frequency to 1.5 GHz, a frequency point available on all the platforms used in our evaluations.
For this purpose, we used the Linux \texttt{cpufreq} mechanism.
We set the governor to \texttt{userspace} to be able to choose the frequency.
We observed that using a fixed governor such as \texttt{userspace} instead of an adaptive one (such as \texttt{ondemand}) yields way better predictability in our results.

\item \textbf{Disable network.}
In the preliminary experiments we conducted for our work, we observed that network introduced lots of noise into the evaluations by widely spreading the distributions of results (more than 10\% difference between minimum and maximum observed throughput for a benchmark repeated with the same parameters).
The simplest solution to avoid these interferences was to disable the network and therefore to operate the benchmarks directly on the machine workstation (on the server \texttt{tty}).

\item \textbf{Disable IRQ balancing.}
\texttt{irqbalance} is a Linux daemon in charge of distributing the hardware Interrupts Requests (IRQs) among the different processing cores of the platform for the purpose of overall system performance.
However, sporadic IRQs and subsequent execution of Interrupt Service Routines (ISRs) occurring on an \emph{uncontrolled} set of cores would bring unpredictability in the system response-time and interfere with our benchmark measurements.
We simply disable this mechanism.
Therefore, the Linux fallback strategy is to pin all IRQs to the first core, which we remove from our thread affinity assignment to completely avoid the issue of running ISRs and benchmarks concurrently on the same cores.

\item \textbf{Disable NUMA balancing.}
On platforms with a large number of cores such as the ones used in these experiments (see Section~\ref{subsub:eval-platforms}), the CPU cores are organized in NUMA nodes (for \emph{Non-Uniform Memory Access}).
This structure allows to palliate the unavoidable pressure on the memory bus due to the high amount of processing cores operating in parallel.
Banks of memory are allocated per NUMA node, reflecting the cache hierarchy.
\textbf{NUMA balancing} is a feature of Linux that periodically moves the tasks closer to the memory they use, \ie in the right NUMA node.
\textbf{NUMA control} is an additional tool allowing to configure NUMA-aware task scheduling and memory allocation in a fine-grain manner, this overriding the overall system NUMA balancing.
We disable system NUMA balancing, and we enable task-local NUMA control, using this syntax:
\begin{lstlisting}[language=bash]
sudo numactl --cpubind=0 --membind=0 <cmd_to_insert_kernel_module>
\end{lstlisting}
This goes one step further as task affinity assignment, as it forces memory allocation to be bound on NUMA node 0.
Our benchmark being inherently concurrent, as soon as there will be more threads than cores per NUMA node, these threads will be allocated on the next NUMA node.
For userspace benchmarks, we use {\tt libnuma} directly in our {\tt pthread} wrapper to pin threads to cores and control the allocation of context data structures.
Therefore, the cross-node threads will suffer some performance loss when trying to access shared data (\eg{} spinlock data structures).

\item \textbf{Completely isolate the cores.}
The Linux kernel provides the possibility to isolate a subset of the CPU cores.
To do so, the parameter \texttt{isolcpus} must be filled with the list of CPU core identifiers to isolate.
This parameter is given on the Linux boot argument command line (\ie in Grub for our case, prior to the kernel boot).
This has the effect of completely preventing the scheduling and other task balancing mechanisms (such as SMP balancing) to operate on these cores.
Unless \emph{explicitly} required with task affinity configuration (with the corresponding system calls or by using the \emph{taskset} program), the OS will not schedule any task on these isolated cores.
In our case, we decided to isolate all cores but the first, with the idea of running our benchmarks on the isolated cores, while the rest of the Linux processes would run on the Core 0 to avoid interfering with our results.

\item \textbf{Kernel threads priority.}
We tried several configurations of \texttt{niceness} for our kernel threads by calling the \texttt{set\_user\_nice()} Linux function, but this did not seem to impact the distribution of our results.
This is to be expected with the precautions described above.
The benchmark response time variability weren't influenced by the priority of the kernel threads.
\end{enumerate}

\subsection{Microbenchmark evaluation}

In this section, we present the microbenchmark experiments carried-out for the paper.
We first describe the experiment itself and then discuss the results obtained.

\subsubsection{Experiment details}
\label{subsub:eval-micro-details}

The microbenchmark works as follow:
each thread repeatedly acquires a (writer) lock, increments a shared counter, and releases the lock.
This is summarized in pseudo-C in Listing~\ref{listing:eval-benchstructure}.

\begin{lstlisting}[style=tutorialcode,label=listing:eval-benchstructure,caption=Pseudo-C code of microbenchmark]
/* the tested lock is parameterized here */
#include <vsync/<chosen>lock.h>

/* lock variable */
static lock_s lock_var;

* supposedly already allocated,
* we also take care of cacheline-alignment
* to avoid false sharing.
unsigned long long* shared_counter;

/* ... */

unsigned long long run()
*shared_counter = 0ull;

do {

} while (!thread_should_stop());

return *shared_counter;
\end{lstlisting}

\input{generated/microbench-constants}

The returned counter is used to compute the throughput (number of times the critical sections was accessed by any thread).
We vary the number of threads in the following set~\footnote{
Obviously, the 127-thread case can only be run on platforms with 128 cores.
It is omitted in the other cases.
${ }$.
We run each experiment for a fixed period of time (\evalMicrobenchDuration{} seconds) and measure the throughput (number of critical sections per second).
We run the experiments \evalMicrobenchNbRuns{} times to ensure the stability of the results (for each case, we pick the median of these repeated runs).

For spinlocks and reader-writer locks, the benchmark runs as a Linux kernel module.
It means that we insert in the kernel a kernel module (\texttt{*.ko} file) that is linked with the code listed in Listing~\ref{listing:eval-benchstructure}.
When inserted, the module runs an initialization routine that consists in spawning as many kernel threads as requested (as explained above, this is a parameter of the experiment), and each thread runs the code listed in Listing~\ref{listing:eval-benchstructure}, until interrupted by a timer (the \evalMicrobenchDuration{}-seconds execution).
This timer is triggered externally, when removing the module from the kernel, as the exit routine of the module is requiring all the threads to finish their execution (it is not possible to kill a kernel thread with a kill signal).
This kernel module is inspired by the previous work of Kashyap \etal~[14], where they (nano-)benchmarked the behavior of a hash-table in kernel-mode to evaluate several locking primitives.

For mutexes, we replace \verb|pthread_mutex| using \verb|LD_PRELOAD|, and the benchmark runs in Linux userspace.

About the selected locking primitives, we compare two variants of each primitive:
an \seqc-only variant,
and a \sys-optimized variant with barriers.

\subsubsection{Results}

\paragraph{Grouping and filtering records.}

The raw experiment results look like a list of records as showed in Table~\ref{table:raw-records}.
The \texttt{count} column represents the value returned by the function \texttt{run()} of Listing~\ref{listing:eval-benchstructure}, \ie the number of times a thread access the critical section.
The \texttt{duration} column is the measured duration (even if it is fixed, some deviation may occur).
Lastly, the \texttt{throughput} column is simply $/$, effectively capturing the number of critical sections per second.

\begin{table}
\begin{minipage}{\textwidth}
\begin{center}
\resizebox{1.0\textwidth}{!}{%
\input{generated/raw-records}
\end{center}
\end{minipage}
\caption{Raw captured records, with parameters and output values.}
\label{table:raw-records}
\end{table}

The records then get grouped together by parameters, and throughput mean, median and stability are computed, as reported on Table~\ref{table:grouped-records}.

\begin{table}
\begin{minipage}{\textwidth}
\begin{center}
\resizebox{1.0\textwidth}{!}{%
\input{generated/grouped-records}
\end{center}
\end{minipage}
\caption{Records grouped by target platform, lock algorithm, \seqc-only/\sys-optimized version and number of threads.
Computed values are median, mean, standard deviation and stability of the \texttt{throughput} column of Table~\ref{table:raw-records}.}
\label{table:grouped-records}
\end{table}

As can be seen on the table, these values are computed for different versions of the algorithm.
\texttt{opt} refers to the \sys-optimized version of the algorithm, while \texttt{seq} refers to the \seqc-only variant.

Mean, median and standard deviation are computed using the usual definitions, while the stability is computed by dividing the maximum throughput by the minimum throughput, effectively giving an indication on the stability of the data set.
The closer the stability is to $1.00$, the more stable the sample is for these fixed values of the parameters.
Figure~\ref{fig:eval-microbench-stability} shows the repartition of the stability among the records of the above table.
As can be observed on the density chart, most observed values are stable.

\begin{figure}[t]
\centering
\includegraphics[width=\plotwidth\textwidth]{generated/chart-density-stability}
\caption{Density of the stability of the different records, per architecture.
The chart exhibits the fact that most results are very stable ($<1.16$ for stability).}
\label{fig:eval-microbench-stability}
\end{figure}

Another way to see them is to group the lines of Table~\ref{table:grouped-records} by stability values as done in Table~\ref{table:stability-records}.
We see than more than 84\% of the results have a stability inferior to 10\% (value $≤1.1$ in the table), which we believe is satisfactory.

\begin{table}
\begin{minipage}{\textwidth}
\begin{center}
\input{generated/stability-table}
\end{center}
\end{minipage}
\caption{Number of experiments categorized by stability.
The mentioned records are lines of Table~\ref{table:grouped-records}.}
\label{table:stability-records}
\end{table}

In practice, we filter out all records with more than 20\% stability to avoid skewing the results.
Indeed, sometimes the optimization speedup can be in the 0 to 20\% improvement range.
Therefore, statistically-speaking computing speedups for unstable values would make little to no sense at all.
For our evaluations, it means we had to throw less than 7\% of the results (see Table~\ref{table:stability-records}).

Instead of simply dropping unstable records, an alternate method would be to redraw experiment samples until it becomes stable (\eg with a stability threshold value of $1.1$).
However, for time reasons, we did not use this method.
We believe the results obtained with this method and the method we actually used would be very similar.

\paragraph{Analysis of speedups of \sys-optimized over \seqc-only implementations.}

Then, we use the values in the filtered table of records to compute the speedup $T_o/T_s - 1$, where $T_o$ is median throughput of \sys-optimized and $T_s$ is the median throughput \seqc-only variants, respectively.
Descriptive statistics aggregates about the observed speedups are showed in Table~\ref{tab:eval-microbench-speedup} and the density of the speedup values is showed in Figure~\ref{fig:eval-microbench-speedups}.
In the paper, for the sake of space, we only reported maximum observed speedups (the \texttt{max} column in Table~\ref{tab:eval-microbench-speedup}).
We can observe on Figure~\ref{fig:eval-microbench-speedups} that most speedups are close to 0.
This effect can mainly be observed on the plot because of the highly-contended cases (number of threads from $8$ and up), where the impact of optimizing barrier is negligible.
On the other hand, if we observe the same data but split for all measured contention levels (\ie number of threads) as depicted per architecture on Figures~\ref{fig:eval-microbench-speedups-heatmap-arm} and~\ref{fig:eval-microbench-speedups-heatmap-x86}, we can analyze the results with finer-grain details.
For \texttt{ARMv8 (taishan200-128c)} (Fig.~\ref{fig:eval-microbench-speedups-heatmap-arm}), good results are scattered across the different contentions levels, but speedups tend to be better for low contention level (especially the $1$ thread case).
In the case of \texttt{x86} (Fig.~\ref{fig:eval-microbench-speedups-heatmap-x86}), the tremendous low-contention speedup case (up to $7×$ for $1$ thread) is emphasized.
This is so big that it overshadows the other cases.
However, the \texttt{qspinlock} column is clearly better than the others, illustrating that in the \texttt{x86} case, \texttt{qspinlock} has \emph{no negative speedup}.

\begin{table}
\begin{minipage}{\textwidth}
\begin{center}
\resizebox{1.0\textwidth}{!}{%
\input{generated/speedup-table}
\end{center}
\end{minipage}
\caption{Speedups of \sys-optimized version of the algorithm over \seqc-only variant.
This descriptive summary must be read with care (especially for the values of \texttt{mean}), as they are only aggregated from \emph{our own} experiment samples (our arbitrary selected thread number, etc.).}
\label{tab:eval-microbench-speedup}
\end{table}

\begin{figure}[t]
\centering
\includegraphics[width=\plotwidth\textwidth]{generated/chart-density-speedups}
\caption{Density of the speedups of the different locks, per architecture.}
\label{fig:eval-microbench-speedups}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[width=\plotwidth\textwidth]{generated/chart-heatmap-speedups-arm}
\caption{Heat map showing the speedups of the different locks on \texttt{ARMv8 (taishan200-128c)}.\\
White squares correspond to data filtered-out for instability.}
\label{fig:eval-microbench-speedups-heatmap-arm}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[width=\plotwidth\textwidth]{generated/chart-heatmap-speedups-x86}
\caption{Heat map showing the speedups of the different locks on \texttt{x86\_64 (gigabyte-96c)}.\\
White squares correspond to data filtered-out for instability.}
\label{fig:eval-microbench-speedups-heatmap-x86}
\end{figure}

\paragraph{MCS lock comparisons.}

Figure~\ref{fig:eval-microbench-mcs} compares the performance of several MCS lock implementations on \texttt{ARMv8 (taishan200-128c)} and \texttt{x86\_64 (gigabyte-96c)}.
As reported in the paper, the different MCS lock implementations are: DPDK[11], Concurrency Kit (ck)[4], CertiKOS[12] and our \sys-optimized.

\begin{figure}[t]
\centering
\includegraphics[width=1.0\textwidth]{generated/chart-mcslock}
\caption{Comparisons of performance of different MCS lock implementations on \texttt{ARMv8 (taishan-128c)} and \texttt{x86\_64 (gigabyte-96c)}.}
\label{fig:eval-microbench-mcs}
\end{figure}

\paragraph{Critical and non-critical section sizes.}

We observed a few other things by conducting this campaign of experiments.
Our benchmark setting allows for additional parameters: \texttt{cs\_size} and \texttt{es\_size} (not reported in the charts of this report).
\begin{itemize}
\item The \texttt{cs\_size} parameter (for ``critical section size'') allows to artificially increase (and control) the size of the critical section.
Instead of only touching one cache line by increasing a counter (as depicted in Listing~\ref{listing:eval-benchstructure}), we can touch an arbitrary number of cache lines, which would corresponds to the value of the \texttt{cs\_size} parameter.

\item The \texttt{es\_size} parameter allows to set an arbitrary number of cache lines touched \emph{outside} the critical section, to simulate different relative sizes of the critical section with regards to the size of the whole program.
\end{itemize}
We observed the following:
\begin{enumerate}
\item The \texttt{es\_size} parameter did not influence the results, meaning that the lock primitive performances and speedup obtained in \sys-optimized over \seqc-only are not affected by the size of the program that is not in the critical section.

\item The \texttt{cs\_size} parameter strongly influenced the results in the following way: the bigger the critical section was, the less was the impact of the barrier optimization.
Additionally, overall, all locking primitives are converging towards the same performance value for an increasing critical section, which is expected as the entry/exit protocols are negligible relatively to a sufficiently large critical section.
\end{enumerate}
From this, we can conclude that barrier optimizations and locking protocols make sense especially for small critical sections and fine-grain locking.
For the final results of the paper, we decided to set \texttt{cs\_size} to $1$ and \texttt{es\_size} to $0$.

\paragraph{Hash table benchmarks.}

Linked to these last findings, prior running our custom-made kernel benchmark module, we tried to use the work of Kashyap \etal~[14] (which is publicly available on Github~\footnote{\url{https://github.com/sslab-gatech/shfllock/tree/master/benchmarks/kernel-syncstress}}), but we were not able to produce predictable results.
Indeed, the variability of such results was very high, and each time we changed a small parameter it produced different output values.
It happened even for details that should not influence the results, such as changing the linking order of the object modules in the makefile.
This was unusable for our work, and could be explained in the following way:
basically, the critical section in the kernel \emph{syncstress} module of Kashyap~\etal{} is accessing nodes of a hash table.
The data of this hash table is randomly populated.
However, accessing a hash table is not a predictable operation in terms of run-time, and different access can yield very different execution times (especially if the hash table is seeded with different random values at each run).
This would lead to critical section size being very different for different runs (even with the same parameter values), and was therefore not usable to compare different techniques.
In comparison, our microbenchmark framework, although being simpler in its structure, produce very predictable results (with very small deviations and good stability, as showcased above in this section) and allow to precisely measure the overheads of barriers and the performance of different locking primitive implementations.

%\subsection{Real-world workload}

% vim: ts=4 sts=4 sw=4 et

\pagebreak
\bibliographystyle{plain}
\begin{thebibliography}{10}

[1]
Linux ticketlock.
\newblock
\url{https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=314cdbefd1fd0a7acf3780e9628465b77ea6a836},

[2]
{Linux-Kernel Memory Model}, 2018.
\newblock
\url{http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0124r6.html}.

[3]
{musl libc: an implementation of the C standard library}, 2020.
\newblock \url{https://musl.libc.org}.

[4]
Samy Al~Bahra.
\newblock Concurrency kit.
\newblock {\em Retrieved November}, 8:2018, 2015.
\newblock \url{https://github.com/concurrencykit/ck}.

[5]
Jonathan Corbet.
\newblock locks and qspinlocks.
\newblock \url{https://lwn.net/Articles/590243/}, 2014.

[6]
Will Deacon.
\newblock locking/qspinlock: Ensure node is initialized before updating
prev->next, Feb 13, 2018.
\newblock
\url{https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=95bcade33a8a}.

[7]
Dave Dice and Alex Kogan.
\newblock Twa -- ticket locks augmented with a waiting array.
\newblock In {\em European Conference on Parallel Processing}, pages 334--345.
Springer, 2019.

[8]
Dave Dice, Alex Kogan, Yossi Lev, Timothy Merrifield, and Mark Moir.
\newblock Adaptive integration of hardware and software lock elision
\newblock In {\em Proceedings of the 26th ACM Symposium on Parallelism in
Algorithms and Architectures}, SPAA '14, page 188–197, New York, NY, USA,
2014. Association for Computing Machinery.

[9]
David Dice, Virendra~J. Marathe, and Nir Shavit.
\newblock Lock cohorting: A general technique for designing numa locks.
\newblock {\em ACM Trans. Parallel Comput.}, 1(2), February 2015.

[10]
Ulrich Drepper.
\newblock Futexes are tricky.
\newblock {\em Futexes are Tricky, Red Hat Inc, Japan}, 4, 2005.

[11]
Linux Foundation.
\newblock {Data Plane Development Kit (DPDK)}, 2015.

[12]
Ronghui Gu, Zhong Shao, Hao Chen, Xiongnan Wu, Jieung Kim, Vilhelm Sj\"{o}berg,
and David Costanzo.
\newblock Certikos: An extensible architecture for building certified
concurrent os kernels.
\newblock In {\em Proceedings of the 12th USENIX Conference on Operating
Systems Design and Implementation}, OSDI'16, page 653–669, USA, 2016.
USENIX Association.

[13]
Maurice Herlihy and Nir Shavit.
\newblock {\em The art of multiprocessor programming}.
\newblock Morgan Kaufmann, 2011.

[14]
Sanidhya Kashyap, Irina Calciu, Xiaohe Cheng, Changwoo Min, and Taesoo Kim.
\newblock Scalable and practical locking with shuffling.
\newblock In {\em Proceedings of the 27th ACM Symposium on Operating Systems
Principles}, SOSP ’19, page 586–599, New York, NY, USA, 2019. Association
for Computing Machinery.

[15]
Michalis Kokologiannakis, Ori Lahav, Konstantinos Sagonas, and Viktor
\newblock Effective stateless model checking for c/c++ concurrency.
\newblock {\em Proceedings of the ACM on Programming Languages}, 2(POPL),
December 2017.

[16]
Michalis Kokologiannakis, Azalea Raad, and Viktor Vafeiadis.
\newblock Model checking for weakly consistent libraries.
\newblock In {\em Proceedings of the 40th ACM SIGPLAN Conference on Programming
Language Design and Implementation}, PLDI 2019, pages 96--110, New York, NY,
USA, 2019. Association for Computing Machinery.

[17]
Michalis Kokologiannakis and Viktor Vafeiadis.
\newblock Hmc: Model checking for hardware memory models.
\newblock In {\em Proceedings of the Twenty-Fifth International Conference on
Architectural Support for Programming Languages and Operating Systems},
ASPLOS '20, page 1157–1171, New York, NY, USA, 2020. Association for
Computing Machinery.

[18]
FAL Labs.
\newblock {Kyoto Cabinet: A straightforward implementation of DBM}, 2011.
\newblock \url{http://fallabs.com/kyotocabinet}.

[19]
Waiman Long.
\newblock locking/qspinlock: Use _acquire/_release() versions of cmpxchg() \&
xchg(), Nov 10, 2015.
\newblock
\url{https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=64d816cba06c}.

[20]
Waiman Long and Peter Zijlstra.
\newblock qspinlock code at version 4.4 of {Linux Kernel}, 2015.
\newblock
\url{https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/locking/qspinlock.c?h=v4.4}.

[21]
Waiman Long and Peter Zijlstra.
\newblock qspinlock code at version 5.6 of {Linux Kernel}, 2020.
\newblock
\url{https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/locking/qspinlock.c?h=v5.6}.

[22]
Victor Luchangco, Dan Nussbaum, and Nir Shavit.
\newblock A hierarchical clh queue lock.
\newblock In {\em European Conference on Parallel Processing}, pages 801--810.
Springer, 2006.

[23]
John~M. Mellor-Crummey and Michael~L. Scott.
\newblock Algorithms for scalable synchronization on shared-memory
\newblock {\em ACM Trans. Comput. Syst.}, 9(1):21--65, February 1991.

[24]
Jonas Oberhauser, Rafael~Lourenco de~Lima~Chehab, Diogo Behrens, Ming Fu,
Antonio Paolillo, Lilith Oberhauser, Koustubha Bhat, Yuzhong Wen, Haibo Chen,
Jaeho Kim, and Viktor Vafeiadis.
\newblock {VSync: Push-Button Verification and Optimization for Synchronization
Primitives on Weak Memory Models}.
\newblock In {\em Proceedings of the 26th ACM International Conference on
Architectural Support for Programming Languages and Operating Systems},
ASPLOS '21, New York, NY, USA, 2021. Association for Computing Machinery.

[25]
Anton Podkopaev, Ori Lahav, and Viktor Vafeiadis.
\newblock Bridging the gap between programming languages and hardware weak
memory models.
\newblock {\em Proceedings of the ACM on Programming Languages}, 3(POPL),
January 2019.

[26]
Christopher Pulte, Shaked Flur, Will Deacon, Jon French, Susmit Sarkar, and
Peter Sewell.
\newblock Simplifying arm concurrency: Multicopy-atomic axiomatic and
operational models for armv8.
\newblock {\em Proceedings of the ACM on Programming Languages}, 2(POPL),
December 2017.

[27]
Pan Xinhui.
\newblock locking/qspinlock: Use atomic_sub_return_release() in
queued_spin_unlock(), Jun 3, 2016.
\newblock
\url{https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=ca50e426f96c}.

\end{thebibliography}

\end{document}


# Statistics of remote regions of networks

J. G. Oliveira  S. N. Dorogovtsev  J. F. F. Mendes

###### Abstract

We delve into the statistical properties of regions within complex networks
that are distant from vertices with high centralities, such as hubs or highly
connected clusters. These remote regions play a pivotal role in shaping the
asymptotic behaviours of various spreading processes and the features of
associated spectra. We investigate the probability distribution $P_{\geq
m}(s)$ of the number $s$ of vertices located at distance $m$ or beyond from a
randomly chosen vertex in an undirected network. Earlier, this distribution
and its large $m$ asymptotics $1/s^{2}$ were obtained theoretically for
undirected uncorrelated networks [1]. Employing numerical simulations and
analysing empirical data, we explore a wide range of real undirected networks
and their models, including trees and loopy networks, and reveal that the
inverse square law is valid even for networks with strong correlations. We
observe this law in the networks demonstrating the small-world effect and
containing vertices with degree $1$ (so-called leaves or dead ends). We find
the specific classes of networks for which this law is not valid. Such
networks include the finite-dimensional networks and the networks embedded in
finite-dimensional spaces. We notice that long chains of nodes in networks
reduce the range of $m$ for which the inverse square law can be spotted.
Interestingly, we detect such long chains in the remote regions of the
undirected projection of a large Web domain.

###### keywords:

complex networks , statistics , small-world effect

††journal: Chaos, Solitons & Fractals

[label1]organization=Departamento de Física da Universidade de Aveiro $\&$
I3N,addressline=Campus Universitário de Santiago, city=Aveiro,
postcode=3810-193, country=Portugal

[label2]organization=Ioffe Physico-Technical Institute,city=St. Petersburg,
postcode=194021, country=Russia

##  1 Introduction

The particular focus within the research field of the statistical physics of
complex networks is on the exploration and comprehension of the central
regions of a network that house vertices with high centralities, such as hubs
or highly connected clusters. A large number of various centrality measures
are used for discovery and indexing of this important central part [2, 3, 4,
5, 6, 7, 8, 9, 10, 11]. The statistical properties of the remote regions of
networks, distant from vertices with high centralities, are far less studied
despite their significant role in the asymptotic behaviour of various
spreading processes, random walks, and the features of associated spectra [12,
13, 14]. One of the simplest statistical characteristics of the remote regions
of networks is the shape of the tail of the distribution of shortest-path
lengths [15, 16, 17, 1, 18, 19, 20, 21, 22, 23, 24, 25]. Notably, in the
networks demonstrating the small-world effect, this distribution approaches
the delta function shape as the network size tends to infinity [26] in
contrast to finite-dimensional networks (“large worlds”). Hence, the
exploration of remote network regions suggests a focus on networks that are
large yet finite in size. In this paper we consider another statistical
characteristic of the remote network regions in the giant connected component,
namely, the probability distribution $P_{\geq m}(s)$ of the number $s$ of
vertices located at distance $m$ or beyond from a randomly chosen vertex. This
distribution was obtained theoretically in Ref. [1] for the configuration
model of undirected uncorrelated networks with an arbitrary degree
distribution. It was shown that the large $s$ asymptotics of this
distribution, for sufficiently large $m$, follows the inverse square law

$P_{\geq m}(s)\propto s^{-2}$ (1)

if an uncorrelated network contains leaves (dead end vertices), that is
vertices of degree $1$, while for the uncorrelated networks with the lowest
non-zero degree of vertices equal $3$, the asymptotics does not follow this
law. In the intermediate case of the uncorrelated networks with the lowest
non-zero degree of vertices equal $2$, this asymptotics was obtained
theoretically, but the range of its validity turned out to be narrow in
reasonably sized networks, and so it is difficult to observe.

One should emphasize that uncorrelated networks are rather special in the
sense that they account only complex degree distributions, devoiding of the
various correlations and short cycles that are prevalent in the majority of
real-world networks. Furthermore, these compact networks, despite their
locally tree-like organization, contain cycles, and hence they cannot be
proper trees. This is why the theoretical asymptotics, Eq. (1), was obtained
only for a narrow class of networks. In this work we reveal that this inverse
square asymptotics is actually observed in diverse real-world and synthetic
undirected networks including strongly correlated networks, trees and loopy
networks, demonstrating the small-world effect. These nets belong to the class
of networks that is much wider than the uncorrelated networks. On the other
hand, we indicate a set of networks for which this law is not valid. In
particular, this set includes the finite-dimensional networks and the networks
embedded in finite-dimensional metric spaces.

Each distribution, plotted in each figure of this paper, was measured for one
network realization through numerical computation of the number $s$ of
vertices located at distance $m$ or beyond from each (and every) vertex in
that specific realization of the network.

The paper is structured as follows. In Section 2 we generate a number of
synthetic networks, including an Erdős–Rényi random graph, a random uniform
tree, growing trees and loopy networks with various degree distributions and
correlations, and measure in these networks the distribution $P_{\geq m}(s)$
and its asymptotics. In Section 3 we analyze the structure of the remote
regions of a set of real-world networks, including social networks, the
Internet and the WWW, power grids, and road networks. We classify the networks
in which the inverse square law is observed and indicate the networks in which
it is not valid. In Section 4 we discuss our results.

##  2 Inverse square law in synthetic networks

It is natural to start our study with an Erdős–Rényi random graph as the
classical paradigm for random networks, being an uncorrelated network with a
Poisson degree distribution. Figure 1(a) shows the distributions $P_{\geq
m}(s)$ for different $m$ observed in the Erdős–Rényi random graph of $10^{6}$
vertices, each pair of which is interconnected with a probability $p$, where
the average degree of a vertex $\langle{q}\rangle\cong pN$ is $5$. For the
sake of comparison, for each $m$ in the plot we indicate the corresponding
theoretical asymptotics from Ref. [1]:

$P_{\geq m}(s)\cong
N\frac{z_{c}^{-1-n_{0}}B^{2}}{\Gamma(\alpha+1)}z_{c}^{m}s^{-2}.$ (2)

In this asymptotics,

$n_{0}=\frac{\ln[\langle{q}\rangle(\langle{q}\rangle-1)N]}{\ln\langle{q}\rangle}$
(3)

and

$\displaystyle z_{c}$ $\displaystyle=$ $\displaystyle\langle{q}\rangle
X_{\infty}<1,$ (4) $\displaystyle\alpha$ $\displaystyle=$
$\displaystyle-\frac{\ln(\langle{q}\rangle
X_{\infty})}{\ln\langle{q}\rangle},$ (5)

where $X_{\infty}=1-S_{G}$ ($S_{G}$ is the relative size of the giant
connected component in the network) is the solution of the equation

$X_{\infty}=e^{\langle{q}\rangle(X_{\infty}-1)}.$ (6)

Finally, the $k\to\infty$ limit of the recursion

$X_{k+1}=e^{\langle{q}\rangle(X_{k}-1)},$ (7)

where the initial value is $X_{0}=1-\delta$, $\delta\to 0$, provides the
constant $B$ in Eq. (2),

$B=\lim_{k\to\infty}(X_{k}-X_{\infty})(\delta\langle{q}\rangle^{k})^{\alpha}.$
(8)

The function $\Gamma(x)$ in Eq. (2) is the gamma function. Similar formulas
describe the asymptotics of $P_{\geq m}(s)$ for the uncorrelated networks
containing vertices of degree $1$. Notice an excellent agreement between the
measured distribution and the theoretical one. It will be more convenient to
observe the cumulative distribution $P^{\text{(cum)}}_{\geq m}(s)=\sum_{u\geq
s}P_{\geq m}(u)$, for which this law, Eq. (1), corresponds to the $1/s$
asymptotics, see Fig. 1(b). Furthermore, Fig. 1(c) shows the distribution
$P_{m}(s)$ of the number $s$ of vertices located at distance $m$ from a
randomly chosen vertex for different $m$. One can see that for sufficiently
large $m$, the distribution $P_{m}(s)$ is close to $P_{\geq m}(s)$.

Figure 1: The statistics of the remote region of the Erdős–Rényi random graph
of $10^{6}$ vertices with the average vertex degree $\langle{q}\rangle=5$. (a)
Distribution $P_{\geq m}(s)$ for different $m$. The dotted lines show the
theoretical asymptotics provided by Eq. (2). Dashed line has slope $-2$. (b)
Cumulative distribution $P^{\text{(cum)}}_{\geq m}(s)$ for different $m$.
Dashed line has slope $-1$. (c) Distribution $P_{\geq m}(s)$ for different
$m$. Dashed line has slope $-2$.

Let us now consider synthetic correlated networks. First we explore three
recursive trees: the growth of two of them is driven by the linear
preferential attachment algorithm, and hence they are scale-free, with the
degree distribution exponents $\gamma=2.2$ and $3$ (Barabási–Albert
model—proportional preferential attachment), and the third is the random
recursive tree, for which the degree distribution is exponential
($\gamma=\infty$). The first random tree has disassortative correlations
between the degrees of the neighbouring vertices, the second has weak
correlations, and the third has assortative correlations. All these growing
random trees are small worlds. Figure 2 demonstrates that the cumulative
distributions $P^{\text{(cum)}}_{\geq m}(s)$ at sufficiently large $m$ decay
as $1/s$.

Figure 2: Cumulative distribution $P^{\text{(cum)}}_{\geq m}(s)$ of three
random growing trees. Dashed lines have slope $-1$. (a) A scale-free recursive
tree of $10^{6}$ vertices whose growth is driven by the linear preferential
attachment, $\text{Prob}(q_{i})\propto q_{i}+A$, $A=-0.8$, where $q_{i}$ is
the degree of vertex $i$. The degree distribution decays as $q^{-\gamma}$,
$\gamma=3+A$. (b) A scale-free recursive tree of $10^{5}$ vertices generated
by the Barabási–Albert model (proportional preference). The degree
distribution decays as $q^{-\gamma}$, $\gamma=3$. (c) A random recursive tree
of $10^{5}$ vertices generated by progressive attachment of new vertices to
randomly chosen vertices. Its degree distribution is exponential.

Figure 3 shows the cumulative distribution $P^{\text{(cum)}}_{\geq m}(s)$ for
a quite different tree, namely, for a connected uniform random tree, whose
Hausdorff dimension equals $2$, that is, this random tree is a “large world”.
The figure demonstrates that the cumulative distribution does not have a
power-law asymptotics.

Figure 3: Cumulative distribution $P^{\text{(cum)}}_{\geq m}(s)$ of the
connected uniform random tree of $10^{4}$ vertices. For clarity, only the
highest 30 values of $m$ are plotted. This tree was generated by the
Aldous–Broder algorithm [27, 28] which we run on the complete graph of
$10^{4}$ vertices.

Figure 4: Cumulative distribution $P^{\text{(cum)}}_{\geq m}(s)$ of six random
growing networks. Dashed lines have slope $-1$. (a,c,e) Each new vertex in a
recursive network attaches, with equal probability, to one or two existing
vertices selected by the same attachment rules as for the recursive trees in
Fig. 2(a,b,c), respectively. (b,d,f) Each new vertex in a recursive network
attaches to two existing vertices selected by the same attachment rules as for
the recursive trees in Fig. 2(a,b,c), respectively. The networks in (a)–(e)
contain $10^{6}$ vertices, the network in (f) has $2\times 10^{7}$ vertices.

Figure 4 shows the cumulative distributions $P^{\text{(cum)}}_{\geq m}(s)$ for
loopy recursive networks whose growth is similar to the recursive trees in
Fig. 2 with one difference. In contrast to the recursive trees, each new
vertex in the networks in Fig. 4(a,c,e) attaches, with equal probability, to
one or two existing vertices, and each new vertex in the networks in Fig.
4(b,d,f) attaches to two existing vertices. The existing vertices for
attachment are chosen by the rules implemented for the recursive trees in Fig.
1(a,b,c). The degree distributions and correlations of the trees in Fig.
1(a,b,c) and the loopy networks in, respectively, Fig. 4(a,c,e) and Fig.
4(b,d,f) are similar. One can see the asymptotics $1/s$ of the cumulative
distributions $P^{\text{(cum)}}_{\geq m}(s)$ for the loopy growing networks in
Fig. 4(a,c,e), which have vertices of degree $1$, while this asymptotics is
not observed in the loopy growing networks in Fig. 4(b,d,f), which have no
vertices of degree $1$, despite their large sizes.

In Table 1 we list the basic structural characteristics of the synthetic
networks considered in this paper.

Network | (Fig.) | $N$ | $k_{max}$ | $\ell$ | $\ell_{max}$
---|---|---|---|---|---
Erdős-Rényi | (1) | $10^{6}$ | 20 | 8.76 | 17
Recursive random 2.2 tree | (2a) | $10^{6}$ | 78,743 | 6.24 | 24
Recursive BA tree | (2b) | $10^{5}$ | 514 | 12.45 | 32
Recursive random tree | (2c) | $10^{5}$ | 16 | 20.54 | 51
Uniform random tree | (3) | $10^{4}$ | 8 | 106.2 | 285
Recursive 2.2 mixed | (4a) | $10^{6}$ | 119,422 | 4.173 | 13
Recursive 2.2 to two | (4b) | $10^{6}$ | 178,791 | 3.435 | 8
Recursive BA mixed | (4c) | $10^{6}$ | 2,241 | 7.66 | 18
Recursive BA to two | (4d) | $10^{6}$ | 2,647 | 6.73 | 12
Recursive random mixed | (4e) | $10^{6}$ | 32 | 11.24 | 23
Recursive random to two | (4f) | $2\times 10^{7}$ | 43 | 10.89 | 16
Table 1: Basic structural characteristics of the synthetic networks
considered: each line has information specifying a network realization, the
figure where numerical results for the distributions are plotted, the size $N$
of the largest component, the maximum degree $k_{max}$, the average path
length $\ell$, and the maximum path length $\ell_{max}$.

##  3 The statistics of remote regions in real-world networks

Real-world networks typically have more complicated architectures than
synthetic ones, and so one could expect that the observation of the inverse
square law in real networks is more difficult. Surprisingly, this is not the
case. In Table 2 we list the basic structural characteristics of the real-
world networks considered in this paper. Figure 5 shows the cumulative
distributions $P^{\text{(cum)}}_{\geq m}(s)$ for the maps of the large regions
of four collaboration and social networks, namely, the FP5 net, CiteSeer, the
Youtube friends network, and Facebook. For all four sets of cumulative
distributions we observe the $1/s$ asymptotics.

Network | (Fig.) | $N$ | $k_{max}$ | $\ell$ | $\ell_{max}$
---|---|---|---|---|---
FP5 | (5a) | 25,287 | 2,783 | 3.14 | 8
CiteSeer | (5b) | 365,154 | 1,739 | 6.470 | 34
YouTube | (5c) | 1,134,890 | 28,754 | 5.279 | 24
Facebook | (5d) | 63,392 | 1,098 | 4.322 | 15
Routers CAIDA | (6a) | 192,244 | 1,071 | 6.98 | 26
AS CAIDA | (6b) | 26,475 | 2628 | 3.876 | 17
US power grid | (7a) | 4,941 | 19 | 18.99 | 46
Road newtork PA | (7b) | 1,087,562 | 9 | 308.0 | 794
Google web | (8a) | 15,763 | 11,401 | 2.517 | 7
Web Stanford | (9) | 255,265 | 38,625 | 6.815 | 164
Table 2: Basic structural characteristics of the real-world networks
considered: each line has information specifying a network, the figure where
numerical results for the distributions are plotted, the size $N$ of the
largest component, the maximum degree $k_{max}$, the average path length
$\ell$, and the maximum path length $\ell_{max}$.

Figure 5: The cumulative distributions $P^{\text{(cum)}}_{\geq m}(s)$ for the
four large collaboration social networks. Dashed lines have slope $-1$. (a)
The FP5 net of $25,287$ vertices [29, 30]. (b) The largest component of
CiteSeer with $365,154$ vertices [31]. (c) A documented region of the Youtube
friends network of $1,134,890$ vertices [32]. (d) A large component in
Facebook with $63,394$ vertices [33].

Figure 6: The cumulative distributions $P^{\text{(cum)}}_{\geq m}(s)$ for the
Internet networks. Dashed lines have slope $-1$. (a) The CAIDA map of the
routers in the Internet including $192,244$ routers [34]. (b) The CAIDA map of
the Autonomous Systems (AS) with $26,475$ AS. [35].

We also observe this asymptotics inspecting the cumulative distributions
$P^{\text{(cum)}}_{\geq m}(s)$ for the Internet networks [36]: the maps of the
routers and the autonomous systems, see Fig. 6. On the other hand, as is
natural, the US power grid and the road network of Pennsylvania, which are
two-dimensional networks, do not demonstrate the power-law asymptotics of
$P^{\text{(cum)}}_{\geq m}(s)$, see Fig. 7.

Figure 7: The cumulative distributions $P^{\text{(cum)}}_{\geq m}(s)$ for (a)
the US power grid of $4,941$ vertices [37] and (b) the US road network
Pennsylvania with $1,087,562$ vertices [38]. For clarity, in (b), only the
highest 50 values of $m$ are plotted.

Figure 8: (a) The cumulative distributions $P^{\text{(cum)}}_{\geq m}(s)$ of
the undirected projection of a network (15,763 vertices and 171,206 edges) of
hyperlinks between pages within Google’s sites [39]. (b) The theoretical
cumulative distributions $P^{\text{(cum)}}_{\geq m}(s)$ of the model tree-like
network mimicking the Google net: it has the hub with the same numbers of the
first-, second-, third-, and fourth-nearest neighbours, $z_{1}=11,401$,
$z_{2}=4228$, $z_{3}=132$, and $z_{4}=1$, as the Google net.

Figure 8(a) shows the cumulative distributions $P^{\text{(cum)}}_{\geq m}(s)$
for a real-world network with a very large hub. This is the undirected
projection of a network of 171,206 hyperlinks between 15,763 pages within
Google’s sites. The largest hub in this network has huge degree 11,401, which
shapes the architecture of this specific network. The steps in the empirical
cumulative distributions in Fig. 8(a) can be reproduced in a tree-like model
network mimicking the structure of the Google net. Imagine a tree-like network
with the hub having the same numbers of the first-, second-, third-,
etc.-nearest neighbours as the hub in the Google net. For this model network
one can easily estimate $P^{\text{(cum)}}_{\geq m}(s)$, see Fig. 8(b), and get
a quantitative agreement with the empirical distribution for $m=2$, $3$, $4$,
and $5$. The small size of this network does not allow us to check whether
this special network architecture still provides the inverse square law or
not.

Figure 9: The cumulative distributions $P^{\text{(cum)}}_{\geq m}(s)$ for the
undirected projection of a large Stanford Web domain containing $255,265$
vertices [38]. Dashed line has slope $-1$.

Figure 9 shows an interesting set of the cumulative distributions
$P^{\text{(cum)}}_{\geq m}(s)$ for the undirected projection of a large
Stanford Web domain (notice a similar set of cumulative distributions in Fig.
6(b)). These empirical cumulative distributions have the $1/s$ asymptotics for
$m$ within the range between $10$ and $15$, but for larger $m$, the cumulative
distributions become step-like. This step-like shape suggests a specific
structure of the remote regions of this network. To understand the
organization of the connections between the vertices within the remote regions
of the network, we extract the vertices at a distance $m=25$ or beyond from
the largest hub in the undirected projection of the network, and edges between
them, and visualize the resulting clusters. In total, there are $714$ vertices
in these clusters and $842$ edges. Figure 10 demonstrates this visualization
(see also Ancillary file). For the sake of completeness, we show the directed
edges of the original directed network. Notice that almost all these directed
edges are reciprocal. Only $3$ edges are not reciprocal. This gives a value
for the fraction of reciprocal edges $(842-3)/842=0.996$. The same edge number
computation performed including the main part of the network gives a total of
$1,941,926$ edges, of which $1,649,280$ are not reciprocal, resulting in a
much lower value, $0.151$, for the fraction of reciprocal edges. We see that
in this region the network is a set of long chains. Notably, only $3$ of these
chains have one of their ends free, and the remaining $7$ chains are parts of
long cycles. Loosely speaking, the Web in this remote region is one-
dimensional.

Figure 10: Visualization of the remote clusters in the Stanford Web network.
The Pajek program package is used [40]. The vertices are labeled according to
their distances from the largest hub in the network. Three of these chains
have one of their ends free, and the remaining $7$ chains are parts of long
cycles. This Figure is provided as Ancillary file.

##  4 Discussion and conclusions

We have explored one of the basic structural statistical characteristics of
the remote regions of complex networks, which previously was known only for
uncorrelated networks. We have observed the $s^{-2}$ asymptotics of the
distribution $P_{\geq m}(s)$ of the number $s$ of vertices located at distance
$m$ or beyond from a randomly chosen vertex in a large set of real and
synthetic undirected networks—small worlds—with a surprisingly diverse
architectures. Such networks include trees and loopy networks, networks with
strong and weak correlations, the one-partite projections of bipartite
networks (FP5 net), the undirected projections of directed networks (Stanford
Web), collaboration and social networks, the Internet and Web networks. This
inverse square law is not observed in the networks having no dead ends
(vertices of degree $1$) and in finite dimensional networks (power grids, road
networks).

For each of these networks we inspected the product of the cumulative
distribution by $N$, $NP^{\text{(cum)}}_{\geq m}(s)$, which turned out
approximately symmetric for all tested cases in the sense that the $x$\- and
$y$-axes of the plots can be interchanged.

Moreover, we have revealed that the organization of connections between
vertices within the remote regions of networks differs dramatically from the
main part of the network, see Fig. 10 and Ancillary file.

One should emphasize that the theoretical results of Ref. [1] for uncorrelated
network still do not offer a compelling explanation for the consistent
observation of the inverse square law across such a wide spectrum of networks.
The explanation of this law is a challenge for the future work. Note that if
we assume that the distribution $P_{\geq m}(s)$ has a power-law asymptotics,
then, for the divergence of the first moment of this distribution (average
number of vertices at distance $m$ or beyond from a randomly chosen vertex),
the exponent of this power law must be not greater that $2$. Hence the
observed exponent $2$ of the asymptotics is the maximum possible value.

Other challenging directions for the future work are the exploration of remote
regions of directed networks and examining the role of the chain structures
observed in this work in network processes.

## CRediT authorship contribution statement

J.G. Oliveira: Planning and revision of the manuscript, Designed the study,
Carried out numerical simulations, Writing original draft. S.N. Dorogovtsev:
Planning and revision of the manuscript, Designed the study, Carried out
analytical and numerical calculations, Writing original draft. J.F.F. Mendes:
Planning and revision of the manuscript.

## Declaration of Competing Interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Acknowledgments

This work was developed within the scope of the project i3N, UIDB/50025/2020
and UIDP/50025/2020, financed by national funds through the FCT/MEC. J. G.
Oliveira acknowledges fruitful discussions with M. Argollo de Menezes and A.
Vázquez.

## References

  * Dorogovtsev et al. [2003] S. N. Dorogovtsev, J. F. F. Mendes, A. N. Samukhin,  Metric structure of random networks,  Nucl. Phys. B 653 (2003) 307.
  * Perra and Fortunato [2008] N. Perra, S. Fortunato,  Spectral centrality measures in complex networks,  Phys. Rev. E 78 (2008) 036107.
  * Katz [1953] L. Katz,  A new status index derived from sociometric analysis,  Psychometrika 18 (1953) 39.
  * Brin and Page [1998] S. Brin, L. Page,  The anatomy of a large-scale hypertextual web search engine,  in: Proceedings of the Seventh International World Wide Web Conference, Elsevier, Amsterdam, 1998, pp. 107–117.
  * Page et al. [1999] L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: Bringing order to the web, Technical Report, Stanford InfoLab, 1999.
  * Freeman [1977] L. C. Freeman,  A set of measures of centrality based on betweenness,  Sociometry 40 (1977) 35.
  * Newman [2005] M. E. J. Newman,  A measure of betweenness centrality based on random walks,  Social Networks 27 (2005) 39.
  * Newman [2010] M. E. J. Newman, Networks: An Introduction, Oxford University Press, Oxford, 2010\.
  * Martin et al. [2014] T. Martin, X. Zhang, M. E. J. Newman,  Localization and centrality in networks,  Phys. Rev. E 90 (2014) 052808.
  * Newman and Girvan [2004] M. E. J. Newman, M. Girvan,  Finding and evaluating community structure in networks,  Phys. Rev. E 69 (2004) 026113.
  * Estrada and Rodriguez-Velazquez [2005] E. Estrada, J. A. Rodriguez-Velazquez,  Subgraph centrality in complex networks,  Phys. Rev. E 71 (2005) 056103.
  * Levin and Peres [2017] D. A. Levin, Y. Peres, Markov Chains and Mixing Times, volume 107, American Mathematical Society, Providence, RI, 2017.
  * Samukhin et al. [2008] A. N. Samukhin, S. N. Dorogovtsev, J. F. F. Mendes,  Laplacian spectra of, and random walks on, complex networks: Are scale-free architectures really important?,  Phys. Rev. E 77 (2008) 036115.
  * Vukadinović et al. [2002] D. Vukadinović, P. Huang, T. Erlebach,  On the spectrum and structure of Internet topology graphs,  in: International Workshop on Innovative Internet Community Systems, Lecture Notes in Computer Science, volume 2346, Springer, Berlin, 2002, pp. 83–95.
  * Dorogovtsev and Mendes [2022] S. N. Dorogovtsev, J. F. F. Mendes, The Nature of Complex Networks, Oxford University Press, Oxford, 2022.
  * Krapivsky and Redner [2001] P. L. Krapivsky, S. Redner,  Organization of growing random networks,  Phys. Rev. E 63 (2001) 066123.
  * Dorogovtsev and Mendes [2002] S. N. Dorogovtsev, J. F. F. Mendes,  Evolution of networks,  Adv. Phys. 51 (2002) 1079.
  * Fronczak et al. [2004] A. Fronczak, P. Fronczak, J. A. Hołyst,  Average path length in random networks,  Phys. Rev. E 70 (2004) 056110.
  * van der Hofstad et al. [2005] R. van der Hofstad, G. Hooghiemstra, P. Van Mieghem,  Distances in random graphs with finite variance degrees,  Random Struct. Algorithms 27 (2005) 76.
  * van der Hofstad et al. [2007] R. van der Hofstad, G. Hooghiemstra, D. Znamenski,  Distances in random graphs with finite mean and infinite variance degrees,  Electron. J. Probab. 12 (2007) 703.
  * Dorogovtsev et al. [2006] S. N. Dorogovtsev, J. F. F. Mendes, J. G. Oliveira,  Degree-dependent intervertex separation in complex networks,  Phys. Rev. E 73 (2006) 056122.
  * Morohosi [2010] H. Morohosi,  Measuring the network robustness by Monte Carlo estimation of shortest path length distribution,  Math. Comput. Simul. 81 (2010) 551.
  * Katzav et al. [2015] E. Katzav, M. Nitzan, D. Ben-Avraham, P. L. Krapivsky, R. Kühn, N. Ross, O. Biham,  Analytical results for the distribution of shortest path lengths in random networks,  Europhys. Lett. 111 (2015) 26006.
  * Katzav et al. [2018] E. Katzav, O. Biham, A. K. Hartmann,  Distribution of shortest path lengths in subcritical Erdős–Rényi networks,  Phys. Rev. E 98 (2018) 012301.
  * Tishby et al. [2022] I. Tishby, O. Biham, R. Kühn, E. Katzav,  The mean and variance of the distribution of shortest path lengths of random regular graphs,  J. Phys. A: Mathematical and Theoretical 55 (2022) 265005.
  * Dorogovtsev et al. [2008] S. N. Dorogovtsev, J. F. F. Mendes, A. N. Samukhin, A. Y. Zyuzin,  Organization of modular networks,  Phys. Rev. E 78 (2008) 056106.
  * Aldous [1990] D. J. Aldous,  The random walk construction of uniform spanning trees and uniform labelled trees,  SIAM J. Discret. Math. 3 (1990) 450.
  * Broder [1989] A. Z. Broder,  Generating random spanning trees,  in: 30th Annual Symposium on Foundations of Computer Science (Research Triangle Park, North Carolina, 30 Oct.—1 Nov. 1989), IEEE, New York, 1989, pp. 442–447.
  * Almendral et al. [2007a] J. A. Almendral, J. G. Oliveira, L. López, J. F. F. Mendes, M. A. Sanjuán,  The network of scientific collaborations within the European Framework Programme,  Physica A: Statistical Mechanics and its Applications 384 (2007a) 675–683.
  * Almendral et al. [2007b] J. A. Almendral, J. G. Oliveira, L. López, M. A. F. Sanjuán, J. F. F. Mendes,  The interplay of universities and industry through the FP5 network,  New Journal of Physics 9 (2007b) 183 – 183.
  * Kunegis [2013] J. Kunegis,  Konect: the koblenz network collection,  Proceedings of the 22nd International Conference on World Wide Web (2013). URL: https://api.semanticscholar.org/CorpusID:15005100.
  * Mislove et al. [2007] A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, B. Bhattacharjee,  Measurement and Analysis of Online Social Networks,  in: Proceedings of the 5th ACM/Usenix Internet Measurement Conference (IMC’07), San Diego, CA, 2007\.
  * Viswanath et al. [2009] B. Viswanath, A. Mislove, M. Cha, K. P. Gummadi,  On the evolution of user interaction in facebook,  in: Proceedings of the 2nd ACM SIGCOMM Workshop on Social Networks (WOSN’09), 2009.
  * cai [2013] CAIDA Skitter Router-Level Topology and Degree Distribution, from April 21 to May 8, 2003, https://www.caida.org/catalog/datasets/router-adjacencies/, 2013\.
  * as_[2013] The dataset contains 122 CAIDA AS graphs, from January 2004 to November 2007, http://www.caida.org/data/active/as-relationships/, 2013\.
  * Pastor-Satorras and Vespignani [2004] R. Pastor-Satorras, A. Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge University Press, Cambridge, 2004.
  * Watts and Strogatz [1998] D. J. Watts, S. H. Strogatz,  Collective dynamics of ’small-world’ networks,  Nature 393 (1998) 440–442.
  * Leskovec et al. [2009] J. Leskovec, K. J. Lang, A. Dasgupta, M. W. Mahoney,  Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,  Internet Math. 6 (2009) 29–123.
  * Palla et al. [2007] G. Palla, I. J. Farkas, P. Pollner, I. Derényi, T. Vicsek,  Directed network modules,  New J. Phys. 9 (2007) 186.
  * Batagelj [1998] V. Batagelj,  Mrvar: Pajek - program for large network analysis,  Connections 21 (1998) 47–57.