# On equilibrium Metropolis simulations
on self-organized urban street networks

JGMBJérôme GM Benoit  SEGJSaif Eddin G Jabari  New York University Abu Dhabi,
Saadiyat Island, POB 129188, Abu Dhabi, UAE  Ronin Institute, NJ 07043,
Montclair, USA  New York University Tandon School of Engineering, Brooklyn, NY
11201, New York, USA

###### Abstract

Urban street networks of unplanned or self-organized cities typically exhibit
astonishing scale-free patterns. This scale-freeness can be shown, within the
maximum entropy formalism (MaxEnt), as the manifestation of a fluctuating
system that preserves on average some amount of information. Monte Carlo
methods that can further this perspective are cruelly missing. Here we adapt
to self-organized urban street networks the Metropolis algorithm. The “coming
to equilibrium” distribution is established with MaxEnt by taking scale-
freeness as prior hypothesis along with symmetry-conservation arguments. The
equilibrium parameter is the scaling; its concomitant extensive quantity is,
assuming our lack of knowledge, an amount of information. To design an ergodic
dynamics, we disentangle the state-of-the-art street generating paradigms
based on nonoverlapping walks into layout-at-junction dynamics. Our adaptation
reminisces the single-spin-flip Metropolis algorithm for Ising models. We thus
expect Metropolis simulations to reveal that self-organized urban street
networks, besides sustaining scale-freeness over a wide range of scalings,
undergo a crossover as scaling varies — literature argues for a small-world
crossover. Simulations for Central London are consistent against the state-of-
the-art outputs over a realistic range of scaling exponents. Our illustrative
Watts-Strogatz phase diagram with scaling as rewiring parameter demonstrates a
small-world crossover curving within the realistic window $2$–$3$; it also
shows that the state-of-the-art outputs underlie relatively large worlds. Our
Metropolis adaptation to self-organized urban street networks thusly appears
as a scaling variant of the Watts-Strogatz model. Such insights may ultimately
allow the urban profession to anticipate self-organization or unplanned
evolution of urban street networks.

Urban street networks,

Self-organization,

Scale-freeness,

Metropolis algorithm,

MaxEnt,

Symmetries,

Conserved quantities,

Self-similarity,

Surprisal,

Graph matchings,

Ising model,

Watts-Strogatz model,

Small-world crossover,

###### keywords:

backref Englishenotez-titleEndnotes enotez-listOEMSSOUSNparagraph heading =

## #1

, notes-sep = 0pt, format = , number = #1 additionalfilesskip
additionalfilesenumrightmargin12.75

Research 29042021

## Introduction

Unplanned or self-organized cities spontaneously undergo scaling coherences
for which a comprehensive explanation is lacking (Rybski et al., 2019).
Scaling coherence, or scale-freeness, expresses apparent invariance under
zooming-in or -out transformations. The scaling coherence of the spatial
organization of a city is reflected in its streets: the streets of a self-
organized city typically follow a scale-free behaviour which has attracted
much attention from observational and theoretical researchers (Rosvall et al.,
2005; Porta et al., 2006; Crucitti et al., 2006; Jiang et al., 2008). We
recently linked the scale-freeness of self-organized urban street networks to
a preservation principle through a fluctuating mesoscopic model (Benoit and
Jabari, 2019a, b).

The invoked preservation principle is the Jaynes’s Maximum Entropy principle
(Jaynes, 1957, 2003; Lawrence, 2019). This principle assesses the most
plausible probability distribution of a fluctuating system according to moment
constraints. We inversely applied it by envisioning streets as mesoscopic
objects governed by social interactions (Benoit and Jabari, 2019a, b). We
reflect the scaling coherence by randomly distributing their numbers of
configurations according to a scale-free distribution, specifically, a
discrete Pareto distribution (Clauset et al., 2009). The discrete Pareto
distribution results from a constraint on the first logarithm moment (Dover,
2004). Since their configurations are equally probable due to our lack of
knowledge, this constraint interprets itself as an information measure
preservation. The predominance of a number of vital connections among social
connections asymptotically leads to a discrete Pareto distribution for the
number of junctions per street. We have what is observed among self-organized
urban street networks. However promising the approach appears, we need to
investigate it completely with some specific tools.

To study such fluctuating models, analytical and simulational methods are
usually employed as complementary methods to obtain more complete and accurate
interpretations. Our analytical framework is the _maximum entropy formalism_ ,
a general formalism of modern probability theory partially inherited from
statistical physics (Grandy, 1987; Jaynes, 2003; Lawrence, 2019). For
simulating fluctuating systems, physicists mostly rely on random sampling
algorithms based on Markov chain Monte Carlo methods, often abbreviated as
_Monte Carlo methods_ (Newman and Barkema, 1999; Landau and Binder, 2015).
Each thus-generated random sample enables us to obtain numerical results that
we can confront to theoretical ones. The Monte Carlo method of first choice
remains the algorithm pioneered by Nicolas Metropolis and his co-workers
(Metropolis et al., 1953; Newman and Barkema, 1999).

Strictly speaking the _Metropolis algorithm_ may apply to configurations of
streets or their associated information networks. An information network
(Rosvall et al., 2005; Porta et al., 2006) is a dual network representation of
an urban street network that (i) associates each street to a node, and (ii)
links each pair of nodes (streets) sharing a common junction (see Figure 1 for
illustration). It is this dual graph representation that reveals the
underlying scale-freeness (Porta et al., 2006; Crucitti et al., 2006; Jiang et
al., 2008). For instance, the valence distribution of an information network
associated to a self-organized urban street network typically follows a
discrete Pareto distribution (Clauset et al., 2009). This observed scale-
freeness provides a clue to find the prior hypothesis (Grandy, 1987; Jaynes,
2003) necessary to construct a fluctuating mesoscopic model for the streets,
that is, to model the probability distribution to which Monte Carlo
simulations are _“coming to equilibrium”_ (Newman and Barkema, 1999; Landau
and Binder, 2015). For mimicking fluctuating transitions, we may use the
property that one information network transforms into another when a junction
alters its street layout.

Basically, a Monte Carlo simulation iterates a Markov process for generating a
Markov chain of states, a sequence of states whose every state depends only on
its predecessor (Newman and Barkema, 1999; Landau and Binder, 2015).A _state_
is a set of quantities completely describing a system which does not include
anything about its history. Along this notion, a _dynamics_ is a map
associating to a state another state which does not depend on the past states.
A Markov process is a dynamics. Here a state is any configuration of streets
or its associated information network (see Figure 1 for illustration). The
Markov process is built so that the Markov chain reaches, when it is iterated
enough times starting from any arbitrary state, the prescribed statistical
equilibrium. To achieve this, the Markov process has to fulfil (i) the
_condition of detailed balance_ and (ii) the _condition of ergodicity_. The
Metropolis algorithm is essentially an implementation choice for the former.
The implementation of the condition of ergodicity relies on the details of the
systems. The objective of this work is twofold. First, to present how a
Metropolis algorithm adaptation can compel these two conditions for self-
organized urban street networks. Second, to apprehend whether or not
Metropolis simulations can provide pertinent “experimental” data to
investigate their scaling coherence.

Figure 1: Notional urban street network meant to pattern throughout this paper
a real-world urban street network. The planar graph representation
($\mathrm{g}$) emphasizes a literal geometric interpretation where junctions
$j_{\ast}$ (and impasses $i_{\ast}$) are nodes and street-segments
$\bar{s}_{\ast}$ are edges. The street maps ($\mathrm{m}$) and
($\mathrm{m}^{\prime}$) show two of the possible configurations of streets
associable to graph ($\mathrm{g}$). The information networks ($\mathrm{t}$)
and ($\mathrm{t}^{\prime}$) emphasize the topological information contained in
street maps ($\mathrm{m}$) and ($\mathrm{m}^{\prime}$), respectively: they
associate streets $r_{\ast}$ to nodes and they link streets sharing common
junctions $j_{\ast}$. Information networks of self-organized or unplanned
urban street networks exhibit in general a scale-free valence distribution,
namely, they are scale-free networks. This observational fact has led us to a
fluctuating model for which configurations of streets are fluctuating as part
of a social process. So, along this paper, a street map such as ($\mathrm{m}$)
or ($\mathrm{m}^{\prime}$) is abstracted as a state[Introduction] of a
fluctuating system.

The rest of the paper presents our innovative modeling approach as follows.
The second section carries out the two requested conditions. Firstly, once the
probability distribution to come to equilibrium is established, the condition
of detailed balance reduces to writing down the emblematic Metropolis
acceptance ratio. Secondly, a short analysis enables us to disentangle the
state-of-the-art paradigms for generating information networks into a
constrained ergodic dynamics, which nonetheless recalls the classical single-
spin-flip ergodic dynamics. This dynamics can potentially become
unconstrained. Eventually, our Metropolis adaptation implements itself and
compares easily against the classical single-spin-flip adaptation for Ising
models. Next, the third section compares, over a wide range of scaling
exponents, Metropolis generation series against state-of-the-art outputs for
Central London (United Kingdom). The range of consistency renders scaling
investigations around their accepted scaling values feasible. As illustration,
we plot the Watts-Strogatz phase diagram with scaling as rewiring parameter.
We demonstrate thusly a small-world crossover curving at realistic scaling
values. Accordingly the state-of-the-art outputs underlie relatively large
worlds. In the concluding section, after a summary of the findings, we point
how the presented methodology may contribute, as part of a fluctuating system
approach, to change our perspective on urban street networks and, by
extension, on cities.

## Implementation of the Metropolis algorithm

This section shows how we can apply the classical Metropolis algorithm on
unplanned or self-organized urban street networks to generate scale-free
streets. We first adapt the most emblematic part, then we design two
appropriate dynamics. Each dynamics aims to create from any current
configuration of streets a new one. The emblematic part tells us whether or
not to accept the new configurations of streets in order for their sequences
to tend to a prescribed statistical equilibrium.

### The emblematic Metropolis acceptance ratio

Typically Monte Carlo methods are applied to thermal systems. So applying them
to a non-thermal system requires the extra preliminary work to frame the
statistics of its steady fluctuations. The framework provided by the maximum
entropy formalism allows us to derive an equilibrium distribution which is
relevant to our scale-free system. This first achievement of our paper is
necessary to implement any Monte Carlo method. The resulting Metropolis
acceptance ratio takes a typical form.

#### Scale-freeness as available information

In the classic literature, the prescribed equilibrium distribution is de facto
the Boltzmann distribution (Newman and Barkema, 1999; Landau and Binder,
2015). The same modern tools that derive the Boltzmann distribution from a
conservation argument allows us to establish the prescribed equilibrium
distribution of a scale-free system through a symmetry argument. We obtain a
discrete Pareto distribution of an undefined quantity. This result should be
folklore in some area, but we could not locate it in the literature.

At thermal equilibrium, the probability $p_{\mu}$ for a thermal system to
occupy any state[Introduction] $\mu$ is assumed to yield the Boltzmann
distribution

$p_{\mu}\propto\mathrm{e}^{-\beta{E_{\mu}}}$ (1)

with $E_{\mu}$ the energy of state $\mu$ and $\beta$ the inverse temperature
(Newman and Barkema, 1999; Landau and Binder, 2015; Grandy, 1987). We have
$\beta=1/kT$ with $k$ the Boltzmann constant and $T$ the temperature. Nowadays
the probability distribution (1) can easily be derived by applying the
_principle of maximum entropy_ (MaxEnt) formulated by Jaynes (1957) as a
general principle of probability theory (Jaynes, 2003; Grandy, 1987; Lawrence,
2019). Within the maximum entropy formalism, Boltzmann probability (1) becomes
the most plausible probability distribution that preserves the total energy of
the system on average. This preservation is formally a constraint imposed on
the mean of the energy. In practice the constraint is treated as a standard
variational problem (Jaynes, 2003; Grandy, 1987) using the method of
Lagrangian multipliers (see for example Applebaum, 2008, App. 2). The
Lagrangian writes (Jaynes, 2003)

${\mathcal{L}_{\mathrm{TE}}}\left(\left\\{p_{\mu}\right\\};\nu,\beta\right)=-\sum_{\mu}p_{\mu}\ln{p_{\mu}}-\nu\biggl{[}\sum_{\mu}p_{\mu}-1\biggr{]}-\beta\biggl{[}\sum_{\mu}p_{\mu}E_{\mu}-{\left\langle{E}\right\rangle}\biggr{]}$
(2)

where $p_{\mu}$ is our unknown probability distribution and the first Lagrange
multiplier $\nu$ forces its normalization, while the second Lagrange
multiplier $\beta$ imposes the mean energy to have the constant energy value
${\left\langle{E}\right\rangle}$. The stationary solution of Lagrangian (2) is
the desired probability distribution $p_{\mu}$ (Jaynes, 2003); we have

$0=\delta{\mathcal{L}_{\mathrm{TE}}}\left(\left\\{p_{\mu}\right\\};\nu,\beta\right)=\sum_{\mu}\Bigl{[}-\ln{p_{\mu}}-\left(\nu+1\right)-\beta
E_{\mu}\Bigr{]}\,\delta{p_{\mu}}$ (3)

for arbitrarily small variations $\delta{p_{\mu}}$ of $p_{\mu}$. Resolving (3)
immediately gives

$p_{\mu}=\frac{\mathrm{e}^{-\beta{E_{\mu}}}}{\operatorname{\mathnormal{Z}}(\beta)}\qquad\text{with}\qquad{\operatorname{\mathnormal{Z}}(\beta)}=\sum_{\mu}\mathrm{e}^{-\beta{E_{\mu}}}$
(4)

as _partition function_ (Jaynes, 2003; Grandy, 1987). Probability distribution
(4) is Boltzmann probability (1) expressed in its _canonical form_ (Jaynes,
2003; Grandy, 1987). If the maximum entropy formalism tells us how to treat
total energy preservation, noticeably it does not tell us why we choose this
constraint over another. Formally the preservation of the total energy is part
of the initial _hypothesis_ or _available information_ (Jaynes, 2003; Grandy,
1987) that we have on systems in thermal equilibrium.

For self-organized urban street networks, our only available information is
scale-freeness. However scale-freeness is not a preserved quantity but rather
a property (Stanley, 1971). But, at the same time, scale-freeness of a self-
organized information network may result from a self-similarity inherited from
its self-organized city (Kalapala et al., 2006; Batty, 2008). Self-similarity
is a symmetry (Mandelbrot, 1982), a transformation that lets an object or a
system stay invariant. Symmetries play a fundamental role in modern physics
(Gross, 1996; Romero-Maltrana, 2015; García-Pérez et al., 2018). A general
consensus in physics is that an invariance to a transformation underlies a
preserved entity, and vice versa (Gross, 1996; Romero-Maltrana, 2015). Let us
see how this idea applies here. For our purpose, we must first rewrite
Lagrangian (2) in the more generic form

${\mathcal{L}_{\operatorname{\mathnormal{f}}}}\left(\left\\{p_{\mu}\right\\};\nu,\lambda\right)=-\sum_{\mu}p_{\mu}\ln{p_{\mu}}-\nu\biggl{[}\sum_{\mu}p_{\mu}-1\biggr{]}-\lambda\biggl{[}\sum_{\mu}p_{\mu}\operatorname{\mathnormal{f}}(X_{\mu})-{\left\langle{\operatorname{\mathnormal{f}}({X})}\right\rangle}\biggr{]}$
(5)

where $X$ is an extensive quantity whose each value $X_{\mu}$ describes state
$\mu$. An extensive quantity scales linearly under scaling transformations.
The new second Lagrange multiplier $\lambda$ imposes our unknown constraint
which expresses in terms of an unknown function
$\operatorname{\mathnormal{f}}$ acting on $X$. It literally coerces the mean
value of ${\operatorname{\mathnormal{f}}({X})}$ to have the constant value
${\left\langle{\operatorname{\mathnormal{f}}({X})}\right\rangle}$. For the
sake of demonstration, we will assume exact self-similarity. Accordingly,
under the scaling transformation

$x\to\widetilde{x}=\mathfrak{s}\,{x},$ (6)

a self-similar (or homogeneous) function $\operatorname{\Phi}(x)$ will
transform as

$\operatorname{\Phi}(x)\to\widetilde{\operatorname{\Phi}(x)}=\operatorname{\Phi}(\mathfrak{s}\,{x})=\mathfrak{s}^{\alpha}\operatorname{\Phi}(x)$
(7)

with $\alpha$ a scaling exponent (Stanley, 1971, sec. 11.1). Here, the self-
similarity invariance holds in the unknown probability distribution
${p_{\mu}=\operatorname{\mathnormal{p}}(X_{\mu})}$. Under transformation (6),
$p_{\mu}$ remains unchanged as expected; we have

$p_{\mu}\to\widetilde{p_{\mu}}=\widetilde{\operatorname{\mathnormal{p}}(X_{\mu})}=\frac{\operatorname{\mathnormal{p}}(\mathfrak{s}\,{X_{\mu}})}{\sum_{\mu}\operatorname{\mathnormal{p}}(\mathfrak{s}\,{X_{\mu}})}=\frac{\mathfrak{s}^{\alpha}\,\operatorname{\mathnormal{p}}({X_{\mu}})}{\sum_{\mu}\mathfrak{s}^{\alpha}\operatorname{\mathnormal{p}}({X_{\mu}})}=\operatorname{\mathnormal{p}}(X_{\mu})=p_{\mu}.$
(8)

If we demand that Lagrangian (5) stays invariant under transformation (6),
then

$\displaystyle 0$
$\displaystyle=\left({{\mathcal{L}_{\operatorname{\mathnormal{f}}}}\left(\left\\{p_{\mu}\right\\};\nu,\lambda\right)}\right)^{~}-{{\mathcal{L}_{\operatorname{\mathnormal{f}}}}\left(\left\\{p_{\mu}\right\\};\nu,\lambda\right)}$
$\displaystyle=-\lambda\,\biggl{\\{}\sum_{\mu}p_{\mu}\bigl{[}\operatorname{\mathnormal{f}}(\mathfrak{s}\,{X_{\mu}})-\operatorname{\mathnormal{f}}(X_{\mu})\bigr{]}-\left\langle{\operatorname{\mathnormal{f}}({\mathfrak{s}\,X})}-{\operatorname{\mathnormal{f}}({X})}\right\rangle\biggr{\\}}$
$\displaystyle=-\lambda\,\biggl{\\{}\sum_{\mu}p_{\mu}\bigl{[}{\operatorname{\mathnormal{f}}(\mathfrak{s}\,{X_{\mu}})}-{\operatorname{\mathnormal{f}}(\mathfrak{s})}-{\operatorname{\mathnormal{f}}(X_{\mu})}\bigr{]}-\left\langle{\operatorname{\mathnormal{f}}({\mathfrak{s}\,X})}-{\operatorname{\mathnormal{f}}(\mathfrak{s})}-{\operatorname{\mathnormal{f}}({X})}\right\rangle\biggr{\\}}$
(9)

for any scaling factor $\mathfrak{s}$ and any possible probability
distribution $p_{\mu}$. Hence, the unknown function
$\operatorname{\mathnormal{f}}$ satisfies the functional equation

$\operatorname{\mathnormal{f}}(\mathfrak{s}\,{x})=\operatorname{\mathnormal{f}}(\mathfrak{s})+\operatorname{\mathnormal{f}}(x).$
(10)

When $X$ takes only positive values $x$, the most general solution of (10)
which is continuous is

$\operatorname{\mathnormal{f}}(x)=K\ln{x}$ (11)

with $K$ a constant (Aczél, 1966, Th. 2.1.2(2)). Substituting solution (11)
into the generic Lagrangian (5) gives the self-similar Lagrangian

${\mathcal{L}_{\mathrm{SE}}}\left(\left\\{p_{\mu}\right\\};\nu,\lambda\right)=-\sum_{\mu}p_{\mu}\ln{p_{\mu}}-\nu\biggl{[}\sum_{\mu}p_{\mu}-1\biggr{]}-\lambda\biggl{[}\sum_{\mu}p_{\mu}\ln{X_{\mu}}-{\left\langle{\ln{X}}\right\rangle}\biggr{]}$
(12)

once the useless constant $K$ is absorbed. One easily verifies that (12)
remains indeed unchanged under the scaling transformation (6). The
corresponding most plausible probability distribution $p_{\mu}$ yields the
stationary equation

$0=\delta{\mathcal{L}_{\mathrm{SE}}}\left(\left\\{p_{\mu}\right\\};\nu,\lambda\right)=\sum_{\mu}\Bigl{[}-\ln{p_{\mu}}-\left(\nu+1\right)-\lambda\ln{X_{\mu}}\Bigr{]}\,\delta{p_{\mu}}$
(13)

whose solution readily writes

$p_{\mu}=\frac{{X_{\mu}}^{-\lambda}}{\operatorname{\mathnormal{Z}}(\lambda)}\qquad\text{with}\qquad{\operatorname{\mathnormal{Z}}(\lambda)}=\sum_{\mu}{X_{\mu}}^{-\lambda}$
(14)

in the canonical form. One quickly checks that probability distribution (14)
is invariant under the scaling transformation (6), as expected. This
probability distribution is known as the discrete Pareto probability
distribution (Clauset et al., 2009). Let us summarize our result as follows.
What the maximum entropy formalism (Grandy, 1987; Jaynes, 2003; Lawrence,
2019) combined with the symmetry-conservation correspondence idea (Gross,
1996; Romero-Maltrana, 2015) tells us about statistically self-similar steady
fluctuations is threefold:

  1. i)

They follow a discrete Pareto probability distribution with the self-similar
scaling exponent as scaling exponent.

  2. ii)

They preserve on average the logarithm of an extensive quantity.

  3. iii)

Their equilibrium parameter is the self-similar scaling exponent itself.

However, it can tell us nothing about the nature of the extensive quantity.

Thusly, the prerequisite to Monte Carlo methods for self-organized urban
street networks can be expressed as follows. At scaling equilibrium, the
probability $p_{\mu}$ for a self-organized urban street network to develop its
streets in any state $\mu$ is assumed to yield the discrete Pareto
distribution

$p_{\mu}\propto\mathrm{e}^{-\lambda\ln{X_{\mu}}}$ (15)

with $X_{\mu}$ the value at state $\mu$ of an extensive quantity $X$ and
$\lambda$ the scaling exponent. Still, it remains to make a genuine hypothesis
on the extensive quantity $X$.

#### A surprisal-driven system

In our context a state $\mu$ is a possible information network, namely a
possible configuration of streets, that an urban street network can develop
(see Figure 1 for illustration). Previous investigations show that an
information network of a self-organized urban street network typically
underlies scale-freeness (Porta et al., 2006; Crucitti et al., 2006; Jiang et
al., 2008). Therefore, as shown in previous section, the distribution of their
nodes (streets) preserves on average the logarithm of an extensive quantity,
so that this distribution is most plausibly a discrete Pareto distribution of
this extensive quantity. This extensive quantity cannot be specified due to
our lack of knowledge on information networks of self-organized urban street
networks.

However, the simplest assumption we can make is that a self-organized urban
street network is a self-similar mesoscopic system whose mesoscopic objects
have equiprobable configurations. Namely, we apply to our mesoscopic objects
the _principle of indifference_ (Jaynes, 2003; Lawrence, 2019). We may call
such a system a self-similar Boltzmann-mesoscopic system. Our extensive
quantity becomes then the number of equiprobable configurations of the
mesoscopic objects. Let us denote by $\Pr(\Omega)$ the probability for a
mesoscopic object to have $\Omega$ possible equiprobable configurations, and
by $o(\Omega)$ a mesoscopic object having effectively $\Omega$ possible
equiprobable configurations. With these notations, we may say that each
mesoscopic object $o(\Omega)$ has $\Omega$ as extensive quantity. Thence, for
each mesoscopic object $o(\Omega)$, our extensive quantity logarithm
$\ln{\Omega}$ interprets itself either as the Boltzmann entropy of $o(\Omega)$
or as the surprisal associated to each configuration of $o(\Omega)$.
_Surprisal_ (or _surprise_ , or _information content_)
${\operatorname{Su}=-\ln\circ\Pr}$ measures uncertainty, astonishment, and
knowledge attached to an event (Tribus, 1961; MacKay, 2003; Applebaum, 2008;
Stone, 2015; Lawrence, 2019). While the average of surprisal over all the
possible events gives their (Shannon) entropy, the surprisal attached to a
possible event pertains its cognitive magnitude. When an event expected to be
rare occurs, we are surprised and we feel that we learn a lot: the larger the
uncertainty before the event, the greater the astonishment at the event, the
wider the knowledge after the event (MacKay, 2003; Applebaum, 2008; Lawrence,
2019). And vice versa. So that, compared to the entropy interpretation, the
surprisal interpretation appears in essence finer and more cognitive. For
these reasons, we may favour the surprisal interpretation. The preserved
moment ${\sum_{\Omega}\Pr(\Omega)\ln{\Omega}}$ interprets then itself as an
amount of surprisal that equilibria preserve on average. We interpret thusly
steady fluctuations as a manifestation of uncertainties, astonishments, and
knowledges whose the magnitudes remain on average the same. Presuming that
this manifestation actually reflects a social process, each equilibrium
becomes then a match between steady fluctuating configurations of streets and
how city-dwellers comprehend their own urban street network (Dover, 2004;
Benoit and Jabari, 2019a, b). We may expect that their comprehension reflects
their agility and proficiency to navigate their own urban street network in
normal or disrupted traffic.

With this assumption, the probability $p_{\mu}$ for a self-organized urban
street network to develop an information network (or a configuration of
streets) $\mu$ yields

$p_{\mu}\propto\prod_{o_{\mu}\in\\{s_{\mu},j_{\mu}\\}}\Omega_{o_{\mu}}^{-\lambda}=\mathrm{e}^{-\lambda{S_{\mu}}}$
(16)

with

$S_{\mu}=\sum_{o_{\mu}\in\\{s_{\mu},j_{\mu}\\}}\ln\Omega_{o_{\mu}}$ (17)

the total amount of surprisal for information network $\mu$; the product (the
sum) is over the streets $s_{\mu}$ and junctions $j_{\mu}$ of information
network $\mu$. Along the interpretation developed in the previous paragraph,
the total amount of surprisal $S_{\mu}$ (17) quantifies the comprehension of
the city-dwellers for information network $\mu$. Thus, accordingly, it is
their comprehension that drives probability distribution (16), that is, the
statistical equilibrium of their own urban street network.

#### The Metropolis acceptance ratio

Now that we have set up the fluctuating statistical model of our system, we
are ready to implement the emblematic part of the Metropolis algorithm. The
Metropolis algorithm holds its specificity among Monte Carlo methods in the
implementation details of the condition of detailed balance (Newman and
Barkema, 1999; Landau and Binder, 2015). This condition assures both that (i)
each Markov chain (or sequence) reaches an equilibrium and that (ii) the
equilibrium states follow the prescribed probability distribution. It applies,
technically, to the probability $P(\mu\to\nu)$ of generating a state $\nu$
from a given state $\mu$ which is called the _transition probability_ ; along
the constraint

$\sum_{\nu}{P(\mu\to\nu)}=1,$ (18)

the transition probabilities ${P(\mu\to\nu)}$ must satisfy the detailed
balance equation

$p_{\mu}\,{P(\mu\to\nu)}=p_{\nu}\,{P(\nu\to\mu)}.$ (19)

Each transition probability $P(\mu\to\nu)$ may be split into two parts as

$P(\mu\to\nu)={g(\mu\to\nu)}\;{A(\mu\to\nu)}.$ (20)

The _selection probability_ $g(\mu\to\nu)$ is a probability imposed to our
algorithm for generating a new state $\nu$ given a state $\mu$, while the
_acceptance ratio_ $A(\mu\to\nu)$ gives the odds of accepting or rejecting the
move to state $\nu$ from state $\mu$. For the Metropolis algorithm, the
selection probabilities $g(\mu\to\nu)$ for all permitted transitions are
equal. Scheme (20) along this choice reduces the detailed balance equation
(19) into a ratio equation for the acceptance ratios ${A(\mu\to\nu)}$; we have

$\frac{P(\mu\to\nu)}{P(\nu\to\mu)}=\frac{{g(\mu\to\nu)}\;{A(\mu\to\nu)}}{{g(\nu\to\mu)}\;{A(\nu\to\mu)}}=\frac{A(\mu\to\nu)}{A(\nu\to\mu)}=\frac{p_{\nu}}{p_{\mu}}.$
(21)

The last equality tells us that the odds of accepting or rejecting a move
between two states are in favour to the more likely of them. This is common
sense. Nonetheless, this still leaves open numerous possibilities. For the
Metropolis algorithm, the more likely moves are assumed certain, while the
less likely moves get their odds adjusted with respect to (21); we read

$A(\mu\to\nu)=\begin{cases}{p_{\nu}}\,{p_{\mu}}^{-1}&\text{if
}{p_{\nu}}<{p_{\mu}}\\\ 1&\text{otherwise}.\end{cases}$ (22)

For our statistical model (16), the Metropolis acceptance ratio
${A(\mu\to\nu)}$ takes the more familiar form

$A(\mu\to\nu)=\begin{cases}\mathrm{e}^{-\lambda{(S_{\nu}-S_{\mu})}}&\text{if
}{S_{\nu}-S_{\mu}}>0\\\ 1&\text{otherwise}.\end{cases}$ (23)

That is to say, if the newly selected information network $\nu$ has a total
amount of surprisal $S_{\nu}$ strictly greater than the current one $S_{\mu}$,
we accept to replace the current information network $\mu$ by the newly
selected one $\nu$ with the probability given above; otherwise, we accept with
certainty.

Figure 2: Deflection angles at junctions: the subfigures
($\mathrm{a}_{\star}$) and ($\mathrm{b}_{\star}$) show the deflection angles
$\delta_{\ast}$ for the junctions $j_{1}$ and $j_{2}$, respectively, from the
notional example in Figure 1. A deflection angle of a street at a junction is
basically the magnitude of the angular change experienced at the junction by
the tangent of the street. In practice, the street can be arbitrarily oriented
and the deflection angle becomes the magnitude of the angle between the
incoming and outgoing tangents. The transposition to pairs of street-segments
at junctions is obvious. Each subfigure corresponds to a possible incoming
street-segment. The subfigures actually organize (index) themselves according
to the cardinal direction (index) of their incoming street-segment. For each
subfigure, the incoming tangent at the junction is in red and the outgoing
tangents are in orange. Every double-arrow arc between the tangents of an
incoming street-segments $\bar{s}_{i}$ and an outgoing one $\bar{s}_{o}$
indicates a deflection angle denoted by $\delta_{i,o}$ — and has a radius
linear with the supplementary angle $\pi-\delta_{i,o}$. Realistic angular
changes are assumed to be bounded above. We have set the deflection angle
threshold to $\pi/4$. The light-blue pie areas identify the forbidden
deflection angles — and have the radius of any arc with the deflection angle
threshold as deflection angle. An incoming street-segment might so continue
its way only along any outgoing street-segment whose tangent or arc lies
within the angular sector of the missing slice — and/or does not cross the pie
area. Furthermore, realistic configurations of streets must obviously have no
street overlap. No incoming street-segment can continue its way along an
outgoing street-segment already passed through. The very basic idea behind the
state-of-the-art for building configurations of streets is a loop: commit one
choice of outgoing street-segment; move to its opposite junction; repeat.
Figure 3 along with supplementary Animation A1 (Additional file 1) illustrate
how streets can emerge from this approach. In contrast, our approach
identifies at every junction all the combinations of incoming and outgoing
street-segments and “flips” them. Figure 4 sketches why and how these
combinations are actually maximum matchings, while Figure 5 along with
supplementary Animation A2 (Additional file 2) illustrate a short sequence of
“flips”.

### Two simple ergodic single-junction dynamics

The state-of-the-art generating paradigms are not dynamics. This is primarily
because they build each information network from scratch. To be a dynamics,
they should instead create a new information network from the current one. An
analysis of their street-oriented paradigm gives us clues to design relevant
ergodic dynamics. This second achievement of our paper permits us to
concretely adapt the Metropolis algorithm to self-organized urban street
networks.

#### A street is an exclusive joined sequence of street-segments

For information networks, nodes are streets, basically an exclusive sequence
of successive street-segments that are joined at junctions according to some
paradigms. By exclusive we mean that a street-segment can only belong to a
single street. This is the perspective used in the state-of-the-art literature
(Jiang and Claramunt, 2004; Rosvall et al., 2005; Porta et al., 2006; Jiang et
al., 2008; Masucci et al., 2014).

An immediate paradigm is the “named street” paradigm (Jiang and Claramunt,
2004; Jiang et al., 2008) which simply reproduces cadastersA _cadaster_ is a
comprehensive land register maintained by either local or central authorities.
Cadasters have been used, in some parts of the world, for levying taxes,
raising armies, setting ownerships, etc.. Since for some cities a cadaster may
not exist, or simply reflect local habits and customs, some studies have
considered generic substitutes instead. The choice of the paradigm may then
ponder social and geographical phenomena. A relevant parameter has appeared to
be the _deflection angle_ between two adjacent street-segments (Jiang et al.,
2008; Molinero et al., 2017). Figure 2 illustrates the notion of deflection
angle in our context through two typical junctions. If beyond some threshold
angle any joining has to be excluded, many possibilities remain open.

Figure 3: State-of-the-art construction paradigm for configurations of
streets: the frames ($\mathrm{s}^{\ast}_{\star}$) show this paradigm steps for
constructing street $r_{c}$ on street map ($\mathrm{m}$) from the notional
example in Figure 1. Our illustration assumes that streets $r_{a}$ and $r_{b}$
were constructed previously and that the remaining streets will be constructed
afterward. The superscript and subscript of each frame label indicate the
street under construction and the step order, respectively. Each street-
segment in colour already belongs to a street: when the colour is vivid and
the line is solid, the street was committed; when the colour is pallid or the
line is vividly dashed, the street is under construction. Each street-segment
in grey is a candidate for belonging to a new street. We attribute to each
street a particular colour. The construction goes like this. Initial stage
($\mathrm{s}^{c}_{0}$): no street-segment is yet assigned to street $r_{c}$.
Seeding step ($\mathrm{s}^{c}_{1}$): pick at random one candidate street-
segment — the seed street-segment is in pallid orange and marked with an
orange bold square. Orientation step ($\mathrm{s}^{c}_{2}$): orient at random
the seed street-segment and move toward the head junction — the square mark is
now a pentagonal “home plate” indicating the orientation, the path moved along
from the mark to the head junction $j_{1}$ is now vividly dashed, the
excluding pie aligned with the incoming tangent at $j_{1}$ immediately
identifies along which outgoing street-segments the street might continue (see
Figure 2). Appending loop steps ($\mathrm{s}^{c}_{3}$)–($\mathrm{s}^{c}_{5}$):
arbitrarily continue at the head junction along any valid outgoing street-
segment (see Figure 2) while applicable — at $j_{1}$ the street might continue
toward either $i_{1}$ or $j_{3}$ (see Figure 2$\mathrm{a}_{2}$), the latter
choice was arbitrarily taken; at $j_{3}$ the street might continue toward
either $i_{3}$ or $j_{5}$, as the former choice was no more possible only the
latter could be taken; at $j_{5}$ the street can only continue toward $i_{7}$;
at $i_{7}$ the street can no more continue so that the recursion ended.
Inverting step ($\mathrm{s}^{c}_{6}$): move toward the tail junction and
formally invert orientation — the forward recursion lets now place to a
backward recursion, the pentagonal mark has flipped its orientation and has
rounded its tail to mark the epoch. Prepending loop steps
($\mathrm{s}^{c}_{7}$)–($\mathrm{s}^{c}_{8}$): arbitrarily continue at the
tail (formal head) junction along any valid outgoing street-segment (see
Figure 2) while applicable — at $j_{2}$ the street might continue toward
either $j_{4}$ or $j_{6}$ (see Figure 2$\mathrm{b}_{2}$), the former choice
was arbitrarily taken; at $j_{4}$ the street can only continue toward $i_{6}$;
at $i_{6}$ the street can no more continue so that the backward recursion
ended. Commit step ($\mathrm{s}^{c}_{9}$): commit the new achieved street and
loop forward to build the next street until applicable — the now achieved
street $r_{c}$ is in solid line, its mark is an unbold circle, and it has a
label; retrospectively, this step leads to Initial stage
($\mathrm{s}^{d}_{0}$) for the next street $r_{d}$ while the above Initial
stage ($\mathrm{s}^{c}_{0}$) appears to result from Commit step
($\mathrm{s}^{b}_{6}$) for the previously committed street $r_{b}$; the
construction of streets loops until no more street-segment is unassigned. The
arbitrary choices in Appending and Prepending loop steps are actually join
principles (see “A street is an exclusive joined sequence of street-segments”
section). Supplementary Animation A1 (Additional file 1) shows a complete
construction of the configuration of streets on street map ($\mathrm{m}$).

Three paradigms based on deflection angles have been mainly used to generate
information networks. Basically these paradigms are nonoverlapping walks
governed by a _join principle_. The _every-best-fit join principle_ (Porta et
al., 2006; Jiang et al., 2008) acts at every junction by joining its street-
segment pairs in increasing order of their deflection angles, until
applicable. The _self-best-fit join principle_ (Viana et al., 2013; Jiang et
al., 2008) and _self[-random]-fit join principle_ (Jiang et al., 2008) act
sequentially on growing streets, until applicable, by randomly seeding them
with a not-yet-selected street-segment before recursively appending, until
applicable, one of the not-yet-appended street-segments. The self join
principles differ only in the choice of the not-yet-selected street-segment to
append. Figure 3 illustrates how the inner recursion can construct an entire
street; supplementary Animation A1 (Additional file 1) shows how the full
machinery can achieve a complete configuration of streets. The self-best-fit
join principle selects the one forming the smallest deflection angle; the
self[-random]-fit join principle selects at random. By construction, these
three joint principles fall into two categories. The every-best-fit join
principle is local and almost deterministicThe every-best-fit join principle
is almost deterministic in the sense that it resolves at random the very rare
occurrences of equality between deflection angles.; the two self join
principles are global and random. The latters clearly differ nevertheless in
the degree of their randomness. Unsurprisingly, due to their walk-oriented
construction, the two self join principles have appeared, against well-founded
cadasters and transportation traffic in terms of correlation, more realistic
(Jiang et al., 2008). They thusly show that the deflection angle is a suitable
parameter for generating information networks. However, the same walk-oriented
construction renders them not easily tractable. In short, even though it
provides a suitable parameter, the state-of-the-art approach can not be used
to build an easily tractable dynamics.

#### A junction is a matching of street-segments

For information networks, edges are junctions, essentially an exclusive set of
singletons and pairs of street-segments that are isolated or paired according
to the ongoing streets. By exclusive we mean that a street-segment can only
belong either to one singleton or to one pair. Such a set is, in graph theory,
a _matching_ (Pemmaraju and Skiena, 2003). To the best of our knowledge, this
is the first work that mentions this perspective.

Figure 4: Set of maximum matchings associable to a junction: the columns
($\mathrm{a}_{\star}$), ($\mathrm{b}_{\star}$), and ($\mathrm{c}_{\star}$)
outline why and how we can associate a set of maximum matchings to any
junction through junctions $j_{1}$, $j_{2}$, and $j_{3}$, respectively, from
the notional example in Figure 1. The subfigures actually organize themselves
in a table: each column corresponds to a notional junction; each row
corresponds to a step of our outline. First step: associate to each street-
segment a node — we can place each node at the intersection of the street-
segment with a circle centred at the junction so that each graph is a circular
graph. Second step: link each node to any node along which it might continue
its way (see Figure 2) — each graph is actually a graph representation of the
pairable street-segments. Third step: enumerate all the street layouts which
could be achieved as part of a configuration of streets according to the
state-of-the-art (see Figure 3) — the construction of the street layouts
follow the scheme used in Figure 3, while the subgraphs link the so paired
street-segment-nodes with a fat red edge. Fourth step: by representing the
subgraphs in canonical form, we immediately realize that Step three actually
enumerate all the subgraphs with the maximum number of non-adjacent edges,
namely, all the maximum matchings — this completes our outline. Notice that
the subfigure labels in rows 3 and 4 enumerate the maximum matchings with
balanced ternary numbers using down-spin ($\downarrow$), nil-spin ($0$), and
up-spin ($\uparrow$) as ternary digits (Knuth, 1997). This enumeration offers
between maximum matchings of junctions joining three or four street-segments
and Ising spin states (down $\downarrow$ and up $\uparrow$) a close analogy as
junctions $j_{1}$ and $j_{2}$ exemplify well here. This analogy appears to
hold as well for our less typical junction $j_{3}$. Figure 5 uses a simpler
but more visual enumeration based on the regular polygons — extended with the
degenerate regular digon. Each corner (side) represents then a maximum
matching.

The graph theory perspective can apply on junctions as follows. First,
inspired by the dual network representation of urban street networks, we may
represent every street-segment attached to a junction by a node. Let us put
each node at the intersection of its associated street-segment with a circle
centred at the junction. Second, we may link pair of nodes whose associated
street-segments have a deflection angle smaller than the deflection angle
threshold. Figure 4 illustrates in its two first rows these two steps for
three realistic junctions. The resulting graph clearly depends on the
deflection angle threshold: when it is set to the flat angle $\pi$, the graph
is a complete graph; when it is set to the zero angle $0$, the graph is an
empty graph; otherwise the graph is an incomplete graph. We will call such a
graph a _junction graph_. In general, a junction graph has no direct
application for our purpose in the sense that any bunch of edges that share a
common node (or adjacent edges) corresponds to a set of overlapping streets.
In practice, we want a graph without any adjacent edge so that the graph
corresponds to a set of nonoverlapping streets. Such a graph is, for a given
junction, a _matching subgraph_ (or matching for short) (Pemmaraju and Skiena,
2003) of its a junction graph. In short, we are interested by the set of
matchings of the junction graphs. The number of matchings of a graph is called
the _Hosoya index_ (Hosoya, 1971). We will denote the Hosoya index of the
junction graph of a junction $j$ by $\mathscr{Z}_{j}$. Also notice that a
matching can be saturated in the sense that it cannot be expanded to another
matching by adding any edge of the underlying graph. Such a matching is called
a _maximal matching_ (Pemmaraju and Skiena, 2003). Figure 4 gives in its
fourth row the set of maximum matchings we can derive for each of its
junctions. We will denote the number of maximal matchings of the junction
graph of a junction $j$ by $\mathscr{Y}_{j}$; we have

${1}\leqslant{\mathscr{Y}_{j}}\leqslant{\mathscr{Z}_{j}}.$ (24)

Let us now describe the previous generating paradigms in terms of matchings.
The “named street” paradigm selects the matching as implicitly recorded in
cadasters. The every-best-fit join principle chooses for each junction the
maximal matching which is optimal in terms of deflection angle distribution.
The two self join principles operate at every junction on the set of matchings
by successive visits. This becomes more apparent when we interpret their
concrete implementations as nonoverlapping walks that haphazardly visit every
junction several times. Each visit either steps forward or terminates the
walk, that is, each visit selects a subset of matchings. This selection
process reveals itself in supplementary Animation A1 (Additional file 1). For
the self-best-fit join principle, the move is optimal in terms of deflection
angle; for the self[-random]-fit join principle, the move is random. Over the
visits the subset of matchings decreases until it contains only one matching.
This remaining matching is a maximal matching since every walk terminates only
when no more street-segment is attachable. Figure 4 draws in its third row the
end results of these repeated visits along their maximum matching for each of
its junctions. Actually, Figure 4 sketches, through three realistic junctions,
why and how to any junction corresponds a set of maximum matching. The so
isolated maximal matchings give the generated information network. In other
words, the self join paradigms interpret themselves now as an intricate
haphazard fashion to pick for every junction a maximal matching. Thusly, the
matching viewpoint allows us to slightly disentangle the two most pertinent
join paradigms.

#### The single-junction-switch and -flip dynamics

The previous slightly untangled description actually leads to a disembodied
form of the self join paradigms with all their underlying principles removed.
This is exactly what an ergodic dynamics is about. To the best of our
knowledge, no ergodic dynamics has been reported so far for generating
configurations of streets.

To begin with, let us deliberately ignore for a while the nonoverlapping walk
machineries. The self join paradigms reduce then to choose for every junction
a maximal matching regardless of the matchings of the other junctions. So the
elementary disembodied dynamics that occurs at junctions is to set up in an
independent way a maximal matching. The new set up will generally change the
maximal matching into another maximal one. For clarity, this dynamics does not
alter the urban street network but rather transforms the information network
into another, since the new maximal matching sets a new layout for some of the
streets that cross the junction. By now we are able to tell that this dynamics
is ergodic. An ergodic dynamics is a dynamics which from any state can reach
any other state after a finite number of iterations. It is indeed obvious that
we can get from any information network to any other by changing one by one
each of the maximal matchings by which the two information networks differ. We
coined this dynamics, following the literature (Newman and Barkema, 1999) and
as an obvious analogy to railroad switches, the _single-junction-switch_
dynamics. The restriction to consider only maximal matchings is inherited from
the join principles. This restriction is arbitrary in the sense that it is not
actually imposed by physical constraints. In fact, the reasoning held above
for the single-junction-switch dynamics evidently holds for any arbitrary
choice of subset of matchings. For completeness, we coined the dynamics that
involves all matchings the _single-junction-flip_ dynamics. Let us recap along
these lines. Assuming an entire urban street network, the single-junction-
switch dynamics is an ergodic dynamics which switches the maximal matching of
a single junction into another maximal one, while the single-junction-flip
dynamics is an ergodic dynamics which flips the matching of a single junction
into another.

Using the single-junction-switch or -flip dynamics ensures that our Metropolis
algorithm fulfils the condition of ergodicity. It remains however to specify
how we select from a given information network a new one which differs by only
one dynamics step. For the sake of simplicity, we will only consider the
single-junction-switch dynamics in the following. The choice of the Metropolis
algorithm imposes (Newman and Barkema, 1999; Landau and Binder, 2015) that the
selection probabilities $g(\mu\to\nu)$ for each possible new information
network $\nu$ after one dynamics step are all chosen equal — the selection
probabilities for all other information networks are set to zero. For an
entire urban street network, one dynamics step enables to reach each of the
$\mathscr{Y}_{j}-1$ new maximal matchings of every junction $j$. Hence the
number of possible new information networks that we can reach after one
dynamics step from a given information network is the total number of maximal
matchings

$\mathscr{N}=\sum_{j}\mathscr{Y}_{j}$ (25)

minus the number of junction $N$. Therefore we count $\mathscr{N}-N$ non-zero
selection probabilities $g(\mu\to\nu)$, and each of them takes the value

$g(\mu\to\nu)=\frac{1}{\mathscr{N}-N}.$ (26)

In practice we can realize this selection in two easy steps. First we pick at
random a junction $j$ with probability proportional to ${\mathscr{Y}_{j}-1}$.
Then we choose at random a new maximal matching among the
${\mathscr{Y}_{j}-1}$ possible new maximal matchings of junction $j$.

### Another variant of the single-spin-flip Metropolis algorithm ?

When all junctions have two maximal matchings, the single-junction-switch
dynamics is formally equivalent to the single-spin-flip dynamics on the
original Ising model. Our two above achievements actually combine to give
another variation on the single-spin-flip Metropolis algorithm theme. This
algorithm is a computational interpretation of the Ising model. A brief
comparison provides basic physical insights and a simple clue for a crossover
as scaling varies.

Figure 5: Single-junction-switch Metropolis algorithm for configurations of
streets: the frames ($\mathrm{g}_{\star}$) show how this algorithm may evolve
from the configuration of streets on street map ($\mathrm{m}^{\prime}$) to the
one on street map ($\mathrm{m}$) from the notional example in Figure 1. The
subscript of each frame label indicate the generation time. The figure reads
from top to bottom. It actually separates generated configurations of streets
from intermediate computational steps in two complementary ways: it shifts
(resp. epochs) the formers to the left column (resp. with integers) and the
latters to the right column (resp. with half-integers). The right frames
display more information. In particular each switchable junction is marked
with an extended regular polygon whose the corners (sides) enumerate its
maximum matchings (see Figure 4): when the polygon is in grey, the junction is
resting; when the polygon is in red and notably bigger, the junction is
switching. As for the state-of-the-art construction paradigm in Figure 3, we
attribute to each street a particular colour. In clear contrast, however, all
streets are here fully constructed. The streets in dashed lines are not under
construction but instead under challenge as follows. The dashing actually
indicates coexistence of old streets with new ones. Each old street keeps its
colour, its circle mark, and its label. Each new street emerges with a new
color, a wavy-circle mark, and a tilded label. The new streets result from the
new street layout at the switching junction. This change leads so to a new
configuration of streets $\nu$ that competes with the old one $\mu$. This is
the actual ongoing challenge. The Metropolis algorithm resolves such
challenges by either accepting or rejecting change $\mu\to\nu$ with an
acceptance ratio $A(\mu\to\nu)$ in an optimal way. After a sufficient number
of generations, the configurations of streets reach a prescribed statistical
equilibrium — provided the equilibrium is sustainable. Our prescribed
statistical equilibrium follows from the assumption that self-organized urban
street networks are statistically self-similar. It is a Boltzmann-like
distribution with a total amount of surprisal (information) instead of energy
and the scaling as equilibrium parameter (see formula (16)). Our odds of
accepting or rejecting new configurations of streets favour the less
surprising ones (see formulae (23) and (30)). The algorithm goes like this
(see “Informal implementation” section). Note first that only the four
junctions $j_{1}$, $j_{2}$, $j_{3}$, and $j_{8}$ are actually switchable:
junction $j_{3}$ has ${\mathscr{Y}_{3}=6}$ maximum matchings (see Figure
4$\mathrm{c}$); junctions $j_{1}$, $j_{2}$, and $j_{8}$ have
${\mathscr{Y}_{1}=\mathscr{Y}_{2}=\mathscr{Y}_{8}=2}$ maximum matchings (see
Figures 4$\mathrm{a}$ and 4$\mathrm{b}$); the remaining junctions $j_{\circ}$
have obviously ${\mathscr{Y}_{\circ}=1}$ maximum matching. So each move will
first choose randomly one junction among junctions $j_{1}$, $j_{2}$, $j_{3}$,
and $j_{8}$ with probabilities $\tfrac{1}{8}$, $\tfrac{1}{8}$, $\tfrac{5}{8}$,
and $\tfrac{1}{8}$, respectively. Each move will second pick uniformly at
random a new maximum matching. There will be ${\mathscr{Y}_{3}-1=5}$ choices
for $j_{3}$, and
${\mathscr{Y}_{1}-1}={\mathscr{Y}_{2}-1}={\mathscr{Y}_{8}-1}=1$ choice for
$j_{1}$, $j_{2}$, and $j_{8}$. Each move will third calculate its change in
amount of surprisal $\Delta{S}$ in view to compute its acceptance ratio $A$.
Here the surprisal changes at mid-steps
($\mathrm{g}_{\scaleto{\frac{1}{2}}{0.9}}$),
($\mathrm{g}_{1\scaleto{\frac{1}{2}}{0.9}}$), and
($\mathrm{g}_{2\scaleto{\frac{1}{2}}{0.9}}$) are respectively
$\Delta{\widetilde{S}}=\ln\frac{5}{9}$, $\Delta{\widetilde{S}}=0$, and
$\Delta{\widetilde{S}}=\ln\frac{6}{5}$ (see “Working assumptions” section).
Ultimately each move will either accept or reject the change with probability
$A$. The layout changes at ($\mathrm{g}_{\scaleto{\frac{1}{2}}{0.9}}$) and
($\mathrm{g}_{1\scaleto{\frac{1}{2}}{0.9}}$) are certain since they are less
or equally surprising, the one at ($\mathrm{g}_{2\scaleto{\frac{1}{2}}{0.9}}$)
is accepted with probability $\exp(-\widetilde{\lambda}\ln\frac{6}{5})$ where
$\widetilde{\lambda}$ is our effective equilibrium parameter (see formula
(30)). Our illustration actually rejects the last move. Supplementary
Animation A2 (Additional file 2) shows a longer sequence.

#### Informal implementation

As summary of our above results, let us informally implement our adaptation of
the Metropolis algorithm to urban street networks as follows.

> First, we choose randomly a junction $j$ with probability proportional to
> its number of maximal matchings $\mathscr{Y}_{j}$ minus $1$,
> ${\mathscr{Y}_{j}-1}$; its street-segments will be laid out according to
> some maximal matching $\mathsf{M}_{j}$. Second, we pick at random a new
> maximal matching $\widetilde{\mathsf{M}}_{j}$ not identical to
> $\mathsf{M}_{j}$ among the remaining ${\mathscr{Y}_{j}-1}$ available
> possibilities. Third, we calculate the change in the total amount of
> surprisal $\Delta{S}$ that would result if we were to lay out this change to
> this junction. Ultimately, with acceptance probability
>
> $A=\begin{cases}\mathrm{e}^{-\lambda{\Delta{S}}}&\text{if }{\Delta{S}}>0\\\
> 1&\text{otherwise},\end{cases}$
>
> either accept or reject the change.

Properly speaking, this informal implementation encodes the single-junction-
switch Metropolis algorithm for urban street networks. We let the reader to
elaborate the corresponding single-junction-flip Metropolis algorithm.
Meanwhile, the reader may refer to Figure 5 and supplementary Animation A2
(Additional file 2) for illustration.

#### A brief comparison with Ising models

The single-junction-switch (resp. single-junction-flip) Metropolis algorithm
for our urban street network model mimics the classical single-spin-flip
Metropolis algorithm for Ising models (Newman and Barkema, 1999; Landau and
Binder, 2015; Berlinsky and Harris, 2019; MacKay, 2003). Nonetheless our model
differs from them in three basic aspects:

  1. (i))

Our model is driven by scaling and surprisal (information) whereas Ising
models are driven by temperature and energy. The parallel scaling-information
versus temperature-energy $(\lambda,{S})\leftrightarrow(\beta,{E})$ pours into
the discipline the all maturity of thermodynamics and statistical physics.
This parallel is actually superseded by the maximum entropy formalism “in a
disembodied form with all the physics removed” (Jaynes, 2003). This formalism
provides, for instance, numerical tools to compute for any information network
measure (Newman, 2018; Porta et al., 2006) its linear response to arbitrary
small scaling changes, namely its specific-heat-capacity-like coefficient or
_susceptibility_ (Newman and Barkema, 1999; Grandy, 1987; Jaynes, 2003).

  2. (ii))

Junctions are nodes of a finite arbitrary planar graph while spins are
classically attached to sites of an “infinite” regular lattice. Finiteness
means that collective phenomena will get smoother. Arbitrariness renders our
model closer to the Ising spin-glass models for which the values of the spin-
spin interactions are no more constant but random (Newman and Barkema, 1999;
Landau and Binder, 2015; MacKay, 2003). Collective phenomena in Ising spin-
glass models are more subtle and more intricate (Newman and Barkema, 1999;
Landau and Binder, 2015).

  3. (iii))

The distribution of maximal matchings (resp. matchings) among junctions is
heterogeneous while the distribution of spins among sites is classically
homogeneous. That is, junctions have different numbers of maximal matchings
(resp. numbers of matchings (Hosoya indices)) while spins have classically the
same number of states or the same dimension. Because the number of street-
segments attached to a junction is mostly three or four, the distribution of
matching is expected to be statistically homogeneous with a bell-like
distribution. This contributes to make our model even closer to the Ising
spin-glass models.

On the other hand, it is noteworthy that the Ising models have became a toy
model to crack _phase transition_ and _crossover_ phenomena (Berlinsky and
Harris, 2019; MacKay, 2003). This raises the obvious question whether our
model may actually undergo a crossover as scaling varies:

  1. 4.

Our model experiences, as scaling increases, an ultra-small- to small-world
crossover around the scaling value of $3$. The small-world effect is in effect
a statement on geodesic (or shortest) distances between node pairs (Newman,
2018). Their mean $\ell$ behaves in small-world networks as the logarithm of
the number of nodes $N$, ${\ell\sim\ln{N}}$ (Newman, 2018). The small-world
effect becomes extreme in scale-free networks as the scaling $\lambda$ get
smaller than $3$ (Cohen and Havlin, 2003): the _mean geodesic distance_ $\ell$
behaves as ${\ell\sim\ln\ln{N}}$ when ${2<\lambda<3}$, as
${\ell\sim\ln{N}/\ln\ln{N}}$ at ${\lambda=3}$, and as ${\ell\sim\ln{N}}$ for
${3<\lambda}$. Thusly, since our generated information networks are scale-
free, our model effectively undergoes a small-world crossover as scaling
varies. Clearly its manifestation relies on the behaviour of the number of
nodes $N$. A more substantial analytical work is however beyond the scope of
the present paper. Meanwhile, notice that a geodesic distance counts in our
context how many changes of street are required for a particular journey. That
is, the mean geodesic distance reflects how rapidly on average city-dwellers
can travel. Accordingly, the crossover diagram of the mean geodesic distance
interprets itself as an efficiency diagram. This means, for instance, that our
approach provides a method to analyze the relative efficiency of an actual
configuration of streets.

## Equilibrium Metropolis simulations

What we have achieved in the previous section is adapting to unplanned or
self-organized urban street networks the Metropolis algorithm. Now, in this
section, we exercise this adaptation in a case study. As case study, we select
the urban street network of Central London (United Kingdom), which is a
classical example of self-organized urban street network (Jacobs, 1993).

### Working assumptions

For the sake of illustration, we have made two suppositions. First, we have
assumed that streets predominate junctions. Second, we have described the
mesoscopic streets as asymptotic agent systems driven by social interactions
(Dover, 2004; Benoit and Jabari, 2019a, b). According to this agent model, a
_number of vital connections_ $\upsilon$ dominates among the possible numbers
of connection between agents. So that, the number of configurations
$\Omega_{s_{\mu}}$ of street $s_{\mu}$ in configuration of streets $\mu$
becomes proportional to a power of its number of junctions $n_{s_{\mu}}$
(Benoit and Jabari, 2019a, b); we have

$\Omega_{s_{\mu}}\propto{n_{s_{\mu}}^{2\upsilon}}.$ (27)

So the total amount of surprisal $S_{\mu}$ (17) in configuration of streets
$\mu$ becomes

$S_{\mu}=2\upsilon\sum_{s_{\mu}}\ln{n_{s_{\mu}}}$ (28)

up to an irrelevant constant; the sum is over the streets $s_{\mu}$ of
configuration of streets $\mu$. Thusly our working assumptions bring out an
_effective scaling exponent_ $\widetilde{\lambda}$ along an _effective total
amount of surprisal_ $\widetilde{S}_{\mu}$; we read

$\widetilde{\lambda}=2\lambda\upsilon\qquad\text{and}\qquad\widetilde{S}_{\mu}=\sum_{s_{\mu}}\ln{n_{s_{\mu}}}.$
(29)

The corresponding effective Metropolis acceptance ratio is literally the tilde
version of formula (23); we get

$A(\mu\to\nu)=\begin{cases}\mathrm{e}^{-\widetilde{\lambda}{(\widetilde{S}_{\nu}-\widetilde{S}_{\mu})}}&\text{if
}{\widetilde{S}_{\nu}-\widetilde{S}_{\mu}}>0\\\
1&\text{otherwise}.\end{cases}$ (30)

Figure 5 along with supplementary Animation A2 (Additional file 2) show how
our Metropolis adaptation can actually generate a sequence of configurations
of streets.

Figure 6: Typical single-junction-switch Metropolis generation series for
Central London (United Kingdom): the foreground purple generation series plot,
for different effective scaling exponents
$\widetilde{\lambda}=2\lambda\upsilon$, typical simulations starting from a
self-fit output; the background light-grey generation series plot, according
to the same modus operandi, typical sequences of self-fit outputs. Each
horizontal solid line drawn along a generation series plot represents its in-
equilibrium mean value, the accompanying horizontal dashed lines indicate the
associated standard-deviation bounds. Coloured lines, Metropolis generation
series; greyed lines, sequences of self-fit outputs. The equilibria are
assumed reached after the $5\,000^{\>\mathrm{th}}$ generation. The following
annealing parameters were used to algebraically cool down to the desired
$\widetilde{\lambda}$: $\widetilde{\lambda}_{0}=1.495$, $\epsilon={10^{-3}}$
and $m=500$. (The starting cooling value $\widetilde{\lambda}_{0}$ was chosen
by hand so that the associated Metropolis equilibrium approaches on average
self-fit outputs — as illustrated in (d); the special case
$\widetilde{\lambda}=\infty$ in (h) corresponds to a full ‘simulated
annealing’ process (Press et al., 2007; Galassi et al., 2009).)

### Equilibria

#### Single-junction-switch Metropolis generation series vs. self-fit outputs

Central London offers, as shown in Figure 6, single-junction-switch Metropolis
generation series that come to equilibria. The equilibria were attained from
self-fit outputs through a basic algebraic _annealing schedule_ (Newman and
Barkema, 1999; Press et al., 2007; Galassi et al., 2009). To paraphrase:
increase (resp. decrease) the control effective scaling exponent
$\widetilde{\lambda}_{c}$ to $\widetilde{\lambda}_{c}(1+\epsilon)$ (resp.
$\widetilde{\lambda}_{c}/(1+\epsilon)$) after every $m$ accepted/rejected
single-junction-switch moves up (resp. down) to the desired equilibrium
effective scaling exponent $\widetilde{\lambda}$; the initial control
effective scaling exponent $\widetilde{\lambda}_{0}$ and the parameters
$\epsilon$ and $m$ are determined by experiment. This annealing schedule
allowed us to reach equilibria for a range of effective scaling exponent
$\widetilde{\lambda}$ values large enough to capture the features of our
system as follows.

The single-junction-switch Metropolis generation series exhibited in Figure 6
show at least four noticeable properties:

  1. i)

The sustained Metropolis equilibria (a-f) are clearly comparable to the self-
fit outputs in terms of order of magnitude of their means and fluctuations.
This property holds, as shown Figure 7, within a window grossly comprised
between $1$ and $5$. We must always bear in mind that scaling exponents of
real-world networks are typically comprised between $2$ and $3$ (Newman,
2018).

  2. ii)

The ground state, namely the sustained Metropolis equilibrium (h) attained for
${\widetilde{\lambda}=\infty}$, lays below the self-fit outputs by about
eleven times their standard-deviation. The ground state was obtained through a
‘simulated annealing’ (Press et al., 2007; Galassi et al., 2009).

  3. iii)

The sustained Metropolis equilibrium (a) shows that there also exist
equilibria that detach significantly from the self-fit outputs from above.

  4. iv)

The sustained Metropolis equilibrium (d) shows that the single-junction-switch
Metropolis algorithm can mimic quite well sequences of self-fit outputs.

These four properties lead us to claim that the single-junction-switch
Metropolis algorithm generates series that are consistent with the self-fit
outputs.

Figure 7: Effective total and average amounts of surprisal versus effective
scaling exponent for Central London (United Kingdom): green solid lines plot
the mean (top) and standard-deviation (bottom) of the effective average amount
of surprisal $\langle\widetilde{S}_{\mu}\rangle$; purple dashed lines plot the
mean (top) and standard-deviation (bottom) of the effective total amount of
surprisal $\widetilde{S}_{\mu}$; the insets show their asymptotic behaviours.
The annealing parameters are the same as in Figure 6; the equilibria were
assumed reached after the $5\,000^{\>\mathrm{th}}$ generation as in Figure 6;
the mean and standard-deviation values were computed over $250\,000$ in-
equilibrium generations and averaged over $10$ simulations. (We attribute the
noise that waves the asymptotic branches to the poor quality of our map
data.[i])

The effective total and average amounts of surprisal, $\widetilde{S}_{\mu}$
and $\langle\widetilde{S}_{\mu}\rangle$ respectively, exhibit in Figure 7 at
least two promising properties:

  1. i)

Their means and their standard-deviations vary smoothly as a function of the
effective scaling exponent $\widetilde{\lambda}$ at least for values smaller
than $4.5$. For greater effective scaling exponent $\widetilde{\lambda}$
values, our simulations get subject to noise: the effective total amounts of
surprisal $\widetilde{S}_{\mu}$ and its standard-deviation
$\operatorname{SD}(\widetilde{S}_{\mu})$ continue to vary smoothly while they
tend asymptotically to a constant; however, their average counterparts
$\langle\widetilde{S}_{\mu}\rangle$ and
$\operatorname{SD}(\langle\widetilde{S}_{\mu}\rangle)$ experience noisy
variations.We attribute the noise to the poor quality of our map data in their
small streets and in their simplification of the junctions. The variations of
$\widetilde{S}_{\mu}$ and $\operatorname{SD}(\widetilde{S}_{\mu})$ remains
relatively smooth because the Metropolis acceptance ratio (30) tends to smooth
$\widetilde{S}_{\mu}$ itself by rejecting the inappropriate states — among
them there are the inappropriate states resulting from “corrupted” data. By
contrast, the variation of $\langle\widetilde{S}_{\mu}\rangle$ and
$\operatorname{SD}(\langle\widetilde{S}_{\mu}\rangle)$ are not smoothed by the
Metropolis algorithm in any manner. Furthermore, “corrupted” layout at
junctions cannot be rejected because (i) our working assumptions do not take
into account junctions in the computation of $\widetilde{S}_{\mu}$ and because
(ii) the single-junction-switch dynamics cannot break them since it only
allows maximal layouts — this becomes evident as soon as the single-junction-
flip dynamics is used since then $\langle\widetilde{S}_{\mu}\rangle$ and
$\operatorname{SD}(\langle\widetilde{S}_{\mu}\rangle)$ vary almost smoothly
along their respective asymptotic branch.

  2. ii)

They all experience a noticeable change of behaviour within the window
comprised between $1$ and $4$. The means of $\widetilde{S}_{\mu}$ and
$\langle\widetilde{S}_{\mu}\rangle$ experience both a change of rate that
leads them to their respective asymptotic plateau. The standard-deviations
$\operatorname{SD}(\widetilde{S}_{\mu})$ reach a maximum at right of $1$
before decreasing towards an asymptotic plateau; the standard-deviations
$\operatorname{SD}(\langle\widetilde{S}_{\mu}\rangle)$ has the left profile of
a Mexican-hat — left shape of a biquadratic curve — with a minimum around $2$.

The latter property strongly suggests that the relevant physics of our system
occurs within the window comprised between $1$ and $4$, while the former
property means that Monte Carlo studies within this window are feasible.

#### The single-junction-switch vs. -flip dynamics

Single-junction-flip Metropolis generation series came also, by applying the
same annealing schedule scheme, to equilibria. Nevertheless, the single-
junction-flip Metropolis generation series contrast with the single-junction-
switch Metropolis generation series into two major ways:

  1. i)

The total amounts of surprisal at single-junction-flip equilibria within the
real-world window $2$–$3$ (Newman, 2018) appear to be greater than the total
amounts of surprisal of the self-fit outputs by about $300$ times their
standard-deviations — while the corresponding ones at single-junction-switch
equilibria are greater by at most $8$ times their standard-deviations. This
makes the single-junction-flip Metropolis algorithm clearly inconsistent with
the self-fit join principle, hence unrealistic.

  2. ii)

For large effective scaling exponent $\widetilde{\lambda}$ values, the single-
junction-flip simulations appear much less subject to noise.

In brief: restricting matchings to maximal matchings renders our system
realistic but numerically unstable for relatively large scaling exponents;
vice versa, loosing matchings renders our system unrealistic but numerically
stable for a relatively wider range of scaling exponents.

To explain this, we must keep in mind that our particular working assumptions
neglect junctions. In fact, in one hand, the single-junction-switch dynamics
provides to our working assumptions a “hard-coded” constraint on junction
layouts so that our system becomes more realistic. On the other hand, the
single-junction-flip dynamics allows the Metropolis algorithm to reject
maximal matchings in favour of non-maximal matchings so that our algorithm
becomes numerically more stable. To resolve this dilemma, we may replace the
hard constraint on junction layouts with a soft constraint. This may take, in
the total amount of surprisal $S_{\mu}$ (28), the form of additional surprisal
terms involving junctions or mixing streets and junctions. The derivation of
such terms is however outside the scope of the present paper.

### Unorthodox Watts-Strogatz phase diagram

So far we have demonstrated that Central London sustains scale-free
configurations of streets over a wide range of scalings. This means that the
selection of a realistic scale-free configuration of street involves other
criteria than just scale-freeness. An appealing explanation might hold with
the small-world crossover, which may happen as we exposed in our “A brief
comparison with Ising models” section. This hypothesis illustrates well the
new class of explorations that the method presented in the present paper
brings in the field. We keep our hypothesis for future work. Meanwhile, to
emphasize our contribution, we demonstrate the small-world crossover by
adopting the phase diagram used for Watts-Strogatz small-world models (Watts
and Strogatz, 1998; Newman, 2003, 2018).

#### Two-regime phase diagram

The Watts-Strogatz phase diagram for Central London plotted in Figure 8 shows
two crossovers which occurs simultaneously at the effective scaling value of
$3$. This phase diagram plots for the information networks of Central London
the averages of their mean geodesic distance (or _mean vertex-vertex
distance_) $\ell$ and of their mean local transitivity (or _clustering
coefficient_) $C$ as functions of the rewiring parameter (Watts and Strogatz,
1998; Newman, 2018). The rewiring parameter is here the effective scaling
exponent $\widetilde{\lambda}$. These two functions experience a qualitative
change of behaviour in the vicinity of effective scaling
${\widetilde{\lambda}=3}$, that is, they exhibit a crossover at effective
scaling ${\widetilde{\lambda}=3}$ (Gluzman and Yukalov, 1998). Our claim that
the crossovers precisely happen at effective scaling ${\widetilde{\lambda}=3}$
relies on the arguments given by Cohen and Havlin (2003). The two simultaneous
crossovers indicate two distinct phases or regimes:

  1. i)

A uniform regime takes place as effective scaling increases from $3$. As
effective scaling gets higher and higher starting from $3$, the mean geodesic
distance between node pairs $\ell$ (resp. the mean local transitivity $C$)
tends on average asymptotically towards a slightly-decreasing (resp. a
slightly-increasing) plateau. The asymptotic behaviours become obvious around
the effective scaling value of $4$. This means that in this regime the
involving phenomena are saturating.

  2. ii)

An emergent/reduction regime occurs as effective scaling decreases from $3$.
As effective scaling gets lower and lower starting from $3$, the mean geodesic
distance between node pairs $\ell$ (resp. the mean local transitivity $C$)
increases (resp. decreases) on average to reach a linear behaviour around the
effective scaling value of $3/2$. The decreasing on average of the mean
geodesic distance between node pairs $\ell$ as scaling increases means that
scaling is inducing a smaller world (Newman, 2018). The increasing on average
of the mean local transitivity $C$ as scaling increases means that scaling is
inducing a denser world or a world with less “structural holes” (Newman,
2018). In our context, a smaller world means journeys with lesser changes of
streets (see end of point 4 in “A brief comparison with Ising models”
section); a denser world means more local alternative routes.

We may regard the two linear behaviours for small and large scalings as
degenerate or extreme. In this sense the relevant part of the phase diagram
yields between the effective scaling values of $3/2$ and $4$. This is
consistent with our previous expectation in “Equilibria” section that the
relevant physics of our system may occur within the window $1$–$4$.

Figure 8: Mean geodesic distance between nodes and mean local transitivity
versus effective scaling exponent for the information networks of Central
London (United Kingdom): yellow solid line plots the mean of the mean geodesic
distance between node pairs $\ell$; turquoise dashed line plots the mean of
the mean local transitivity $C$; the vertical dotted line represents the
effective scaling exponent $\widetilde{\lambda}_{0}$ for which the associated
Metropolis equilibrium approaches on average self-fit outputs — as illustrated
in Figure 6d; the inset shows their asymptotic behaviours; the main figure and
the inset have the same aspect ratio. The experimental protocol was the same
as in Figure 7. (We attribute the noise to the same reasons as in Figure 7.)

#### A brief comparison with the classical Watts-Strogatz phase diagram

The Watts-Strogatz phase diagram for Central London confirms that our urban
street network model underlies the small-world effect. Our expectation was
sketched in point 4 of our “A brief comparison with Ising models” section.
Nonetheless the obtained Watts-Strogatz phase diagram differs from the
classical Watts-Strogatz phase diagram Newman, 2003, Fig. 6.2; Watts and
Strogatz, 1998, Fig. 2 in three essential characteristics:

  1. i)

A smaller world means a denser world, not a less dense one. This is because on
average the mean local transitivity $C$ increases instead of decreasing.

  2. ii)

The two crossovers coincide. In other words, no emergent/reduction regime
overlaps with an uniform regime and vice versa.

  3. iii)

The small-world effect predominates. The overall variation of the average of
the mean local transitivity $C$ is of order $0.04$, so we may regard the local
transitivity evolution as insignificant. Meanwhile the average of the mean
geodesic distance between node pairs $\ell$ gains overall $2.5$ nodes and
$0.9$ nodes within the relevant window from $3/2$ to $4$, that is, the small-
world effect is actually the substantial phenomenon.

Therefore, contrary to Watts-Strogatz small-world networks (Watts and
Strogatz, 1998; Newman, 2003, 2018), the information networks of Central
London experience no balance between local transitivity and the small-world
effect. Actually, among both, only the small-world effect is relevant as
scaling varies.

#### The self-fit configurations of streets are inefficient

Generation series (d) in Figure 6 shows that, for Central London, self-fit
outputs are hardly distinguishable from Metropolis in-equilibrium generations
at effective scaling $\widetilde{\lambda}_{0}=1.495$. This value can be
regarded as a measurement of the effective scaling at which Central London
sustains self-fit configurations of streets. This measurement is represented
on the Watts-Strogatz phase diagram for Central London in Figure 8 by the
vertical dotted line. The phase diagram immediately tells us on self-fit
information networks for Central London three noteworthy facts:

  1. i)

Their worlds are on average of a magnitude one node larger. As natural
reference, we take here the high-scaling asymptotic configurations of streets.

  2. ii)

They occur around the end of the low-scaling linear behaviour. That is, they
occur around the low-scaling boundary of the relevant window $3/2$–$4$.

  3. iii)

There is room for information networks with significantly smaller worlds. A
quick check shows that information network worlds at effective scaling $2.50$
(centre of realistic window $2$–$3$) and $2.75$ (centre of the relevant window
$3/2$–$4$) are on average, respectively, $0.6$ and $0.7$ nodes smaller than
the self-fit worlds. These offset drops are, respectively, of the order of
$60\%$ and $70\%$. Namely, they are substantial.

To summarize, the Watts-Strogatz phase diagram describes self-fit information
networks for Central London as being on average relatively large worlds.

However, Central London dwellers may rather want to know whether their self-
fit configurations of streets are efficient. Efficiency means here for city-
dwellers that they can complete their journeys as fast as possible. This can
be partially achieved by decreasing as much as possible the number of street
changes required per journey. This means to develop information network whose
worlds are as small as possible. This corresponds on the Watts-Strogatz phase
diagram to information networks having on average relatively small worlds. In
effect, this involves the information networks that actually experience the
crossover. As we have seen, quite the opposite actually happens to the self-
fit information networks of Central London: they take place where the small-
scaling linear behaviour ceases and they underlie on average relatively large
worlds. In brief, the self-fit configurations of streets for Central London
are inefficient.

## Conclusions and future works

Unplanned or self-organized urban street networks undergo a scale-free
coherence that we interpret in terms of a fluctuating system. This paper
sketches how the Metropolis algorithm, which embodies well the idea of
fluctuating systems (Newman and Barkema, 1999; Landau and Binder, 2015), can
apply to self-organized urban street networks once our interpretation is
embraced. The Metropolis algorithm is a classical entry-point for more
elaborate Monte Carlo methods. These methods are the natural numerical
companions for theoretical studies on fluctuating systems, and vice versa. Our
theoretical framework is the maximum entropy formalism (MaxEnt) (Grandy, 1987;
Jaynes, 2003; Lawrence, 2019).

Our prior hypothesis (Grandy, 1987; Jaynes, 2003) is scale-freeness (Stanley,
1971). Assuming this property as the result of an underlying self-similarity
symmetry (Mandelbrot, 1982; Batty, 2008) paves the way to a symmetry-
conservation correspondence as used in physics (Gross, 1996; Romero-Maltrana,
2015). This physical idea effortlessly adapts itself to MaxEnt. This allows
us, as required for implementing any Monte Carlo method, to set up our
prescribed statistical equilibrium. The self-similarity symmetry demands the
conservation on average of the logarithm of an extensive quantity which, by
virtue of MaxEnt, most plausibly underlies a discrete Pareto distribution
(Clauset et al., 2009). The scaling exponent is our equilibrium parameter.
Meanwhile, the best we can tell on any information network is that it is a
mesoscopic system whose objects, nodes (streets) and edges (junctions), have
equiprobable configurations. So, the best we can assume about our extensive
quantity is that it is a number of equiprobable configurations. The conserved
quantity becomes then an average of Boltzmann entropies. However we may rather
interpret this information measure as an amount of surprisal (Tribus, 1961;
MacKay, 2003; Applebaum, 2008; Stone, 2015; Lawrence, 2019) that actually
quantifies the comprehension of the city-dwellers for their own urban street
network (Benoit and Jabari, 2019a, b). Once our prescribed statistical
equilibrium is fully set up, we can readily implement our Metropolis
acceptance ratio.

As concerns the ergodic dynamics, its counterpart, the nonoverlapping walk
approaches found in the literature (Porta et al., 2006; Jiang et al., 2008;
Viana et al., 2013) appear inappropriate but nonetheless inspirational. We
imagine information networks not in terms of haphazard nonoverlapping walks
along street-segments, but in term of random street layout at junctions. Our
approach readily leads to dynamics that mimic the classical single-spin-flip
dynamics in Ising models (Newman and Barkema, 1999; Landau and Binder, 2015;
Berlinsky and Harris, 2019). At every junction, each pair of street-segments
that can hold a street is a link of a graph where street-segments map to
nodes, so that each matching (Pemmaraju and Skiena, 2003) of this graph
represents a possible layout. As the single-spin-flip dynamics changes the
state of a spin into another possible state, our dynamics changes the matching
(layout) of a junction into another possible matching (layout). We named
single-junction-flip the dynamics that involves any matchings, and single-
junction-switch the dynamics that involves only maximal matchings (Pemmaraju
and Skiena, 2003). If our approach implicitly implies that self-organized
urban street networks might sustain scaling coherence over a wide range of
scalings, finding dynamics reminiscent of Ising models suggests first and
foremost that they might undergo a crossover as scaling varies. Since large
scale-free networks exhibit ultra-small- and small-world behaviours for
scaling values respectively smaller and greater that $3$ (Cohen and Havlin,
2003), self-organized urban street networks might actually experience as
scaling increases a small-world crossover around the scaling value of $3$.

We choose as case study the recognized self-organized urban street network of
Central London (United Kingdom) (Jacobs, 1993). Simulations based on
predominant streets and an asymptotic agent model driven by social
interactions (Dover, 2004; Benoit and Jabari, 2019a, b) show that the single-
junction-switch Metropolis algorithm generates equilibria that are consistent
with the aforementioned nonoverlapping walk approaches. The simulations remain
consistent over a range of scaling exponents large enough to contain the
realistic window from $2$ to $3$ (Newman, 2018) and to capture changes of
behaviour in their total and average amounts of surprisal. Thusly, the single-
junction-switch Metropolis algorithm allows simulational investigations. The
single-junction-flip dynamics also leads to equilibria, but with unrealistic
amounts of surprisal. We explain this, given that our model neglects junctions
while the single-junction-switch dynamics coerces junctions to have maximal
layouts, by a lack of constraints on junctions. Along this explanation, the
single-junction-flip dynamics may allow to investigate the role played by
junctions. In brief, our simulations on Central London show that our
adaptation of the Metropolis algorithm for generating self-organized
information networks is applicable and relevant.

To illustrate our innovative methodology, we plot the Watts-Strogatz phase
diagram with scaling as rewiring parameter. The phase diagram exhibits an
emergent/reduction regime followed by an uniform regime as scaling increases.
That is, the small-world and the local transitivity crossovers occur
simultaneously. However only the former is significant in magnitude. The
crossovers happen approximately around the scaling value of $3$. More
noticeably, the crossovers curve within the realistic window from $2$ to $3$.
Thusly, as expected, our phase diagram demonstrates a small-world crossover
around the scaling value of $3$. Our phase diagram also allows us to discuss
the pertinence of the self-fit outputs. The self-fit outputs take place on
average nearly the scaling value of $3/2$, namely, significantly before the
realistic window $2$–$3$. They actually occur on average at the ending of the
linear scaling behaviour observed at low scalings — which we may consider as
degenerate. Concretely this means that self-fit outputs generate on average
information networks that underlie relatively large worlds, namely, that are
inefficient. If the implicit belief that self-organized urban street networks
have reached an optimal balance over time holds, representative information
networks may rather occur within the realistic window $2$–$3$ where their
worlds are on average relatively small, namely, efficient — assuming that the
small-world effect gets counterbalanced as its effect curves. Thusly, our
illustrative Watts-Strogatz phase diagram challenges the state-of-the-art on
generating information networks, while it indicates that self-organized
information networks can undergo as scaling increases a small-world crossover
curving within the realistic window $2$–$3$. In other words, our illustrative
numerical “experiment” on Central London demonstrates that our adaptation of
the Metropolis algorithm for generating self-organized information networks is
indeed pertinent to gain new insights.

From a fundamental point of view, future works must focus on two points.
First, we must recognize the deep origin underlying the extensive quantity
associated to the scaling exponent in order to specify its very nature.
Second, we must find an uncoercive way to involve junctions in order to
investigate their role. From a simulational point of view, we must investigate
the undergoing small-world crossover by considering other network phenomena
(Newman, 2018) and a large panel of recognized self-organized urban street
networks (Jacobs, 1993; Crucitti et al., 2006). We anticipate to observe
network phenomena (Newman, 2018) that counterbalance the small-world effect
within or around the realistic window $2$–$3$ (Newman, 2018). From an
observational point of view, our fluctuating approach clearly challenges the
current method to determine the scaling exponent of an urban street network
which is based on a single arbitrary output (Porta et al., 2006; Jiang et al.,
2008). In view to confront our simulational data against observational data,
we must derive methods able to “take” the scaling exponent and to measure
network measures (Newman, 2018) along with their susceptibilities (Newman and
Barkema, 1999; Grandy, 1987; Jaynes, 2003). From a practical point of view, we
envision that our Metropolis adaptation may initiate, alongside Monte Carlo
models getting more elaborate but also more realistic, a ‘scaling-dynamics’
based description of our urban street networks and, by extension, of our
cities. Such a descriptive framework may provide fruitful analogies with
thermodynamics and precious insights on unplanned evolution for city
scientists, city designers, and decision-makers to anticipate the evolution of
our cities.

*[OEMSSOUSN]

## Supplementary information

Supplementary information accompanies this paper at
https://doi.org/10.5281/zenodo.4439354. Additional file 1: State-of-the-art
construction paradigm for configurations of streets (Animation
A1)[mimetype=application/pdf,desc=Animation A1]oemssousn-animation-A01.pdf
Additional file 2: Single-junction-switch Metropolis algorithm for
configurations of streets (Animation
A2)[mimetype=application/pdf,desc=Animation A2]oemssousn-animation-A02.pdf

## Abbreviations

MaxEnt: Maximum Entropy formalism (or principle); SE: Scaling Equilibrium; TE:
Thermal Equilibrium.

## Availability of data and materials

The map of the urban street network of Central London was extracted from the
Open Street Map (OSM) comprehensive archive (OpenStreetMap, 2004–2020) and
simplified with OSMnx ${\mathrm{v}0.11.4}$ (Boeing, 2017). The network
measures were computed with the igraph C library ${\mathrm{v}0.8.2}$ (Csárdi
and Nepusz, 2006; Csárdi et al., 2020). The software used to perform the
simulations is available, along with the map and generation series samples, at
https://doi.org/10.5281/zenodo.3746140. The datasets generated and analysed
during the current study are available from the corresponding author on
reasonable request.

## Author’s contributions

JGMB conceived and designed the study, collected and treated the map data,
designed and programmed the simulation tools, performed and treated the
simulations, and wrote the manuscript. SEGJ helped to shape the manuscript.
Both authors read and approved the final manuscript.

## Acknowledgements

This work was supported by the NYUAD Center for Interacting Urban Networks
(CITIES), funded by Tamkeen under the NYUAD Research Institute Award CG001 and
by the Swiss Re Institute under the Quantum Cities™ initiative.

## Competing interests

The authors declare that they have no competing interests.

## References

  * Aczél (1966) Aczél J (1966) Lectures on Functional Equations and their Applications, Mathematics in Science and Engineering, vol 19. Academic Press, New York, https://doi.org/10.1016/S0076-5392(09)60202-2
  * Applebaum (2008) Applebaum D (2008) Probability and Information: An Integrated Approach, 2nd edn. Cambridge University Press, Cambridge, https://doi.org/10.1017/CBO9780511755262
  * Batty (2008) Batty M (2008) The size, scale, and shape of cities. Science 319(5864):769–771, https://doi.org/10.1126/science.1151419
  * Benoit and Jabari (2019a) Benoit J, Jabari S (2019a) On the perturbation of self-organized urban street networks. Appl Netw Sci 4:49, https://doi.org/10.1007/s41109-019-0153-0
  * Benoit and Jabari (2019b) Benoit J, Jabari S (2019b) Structure entropy, self-organization and power laws in urban street networks, URL https://arxiv.org/abs/1902.07663
  * Berlinsky and Harris (2019) Berlinsky AJ, Harris AB (2019) Statistical Mechanics. Graduate Texts in Physics, Springer-Verlag, Cham, https://doi.org/10.1007/978-3-030-28187-8
  * Boeing (2017) Boeing G (2017) OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Comput Environ Urban Syst 65:126–139, https://doi.org/10.1016/j.compenvurbsys.2017.05.004, URL https://github.com/gboeing/osmnx
  * Clauset et al. (2009) Clauset A, Shalizi CR, Newman MEJ (2009) Power-law distributions in empirical data. SIAM Rev 51(4):661–703, https://doi.org/10.1137/070710111
  * Cohen and Havlin (2003) Cohen R, Havlin S (2003) Scale-free networks are ultrasmall. Phys Rev Lett 90(5):058701, https://doi.org/10.1103/PhysRevLett.90.058701
  * Crucitti et al. (2006) Crucitti P, Latora V, Porta S (2006) Centrality measures in spatial networks of urban streets. Phys Rev E 73(3):036125, https://doi.org/10.1103/PhysRevE.73.036125
  * Csárdi and Nepusz (2006) Csárdi G, Nepusz T (2006) The igraph software package for complex network research. InterJournal Complex Systems 1695(5):1–9
  * Csárdi et al. (2020) Csárdi G, Nepusz T, Horvát S, Traag VA, Zanini F (2020) igraph. https://doi.org/10.5281/zenodo.3774399
  * Dover (2004) Dover Y (2004) A short account of a connection of power laws to the information entropy. Physica A 334(3-4):591–599, https://doi.org/10.1016/j.physa.2003.09.029
  * Galassi et al. (2009) Galassi M, Davies J, Theiler J, Gough B, Jungman G, Alken P, Booth M, Rossi F (2009) GNU Scientific Library Reference Manual, 3rd edn. Network Theory Limited, URL https://www.worldcat.org/isbn/9780954612078
  * García-Pérez et al. (2018) García-Pérez G, Boguñá M, Serrano MÁ (2018) Multiscale unfolding of real networks by geometric renormalization. Nat Phys 14(6):583–589, https://doi.org/10.1038/s41567-018-0072-5
  * Gluzman and Yukalov (1998) Gluzman S, Yukalov VI (1998) Unified approach to crossover phenomena. Phys Rev E 58(4):4197–4209, https://doi.org/10.1103/PhysRevE.58.4197
  * Grandy (1987) Grandy WT Jr (1987) Foundations of Statistical Mechanics, Fundamental Theories of Physics, vol 19. Springer-Verlag, Dordrecht, https://doi.org/10.1007/978-94-009-3867-0
  * Gross (1996) Gross DJ (1996) The role of symmetry in fundamental physics. Proc Natl Acad Sci USA 93(25):14256–14259, https://doi.org/10.1073/pnas.93.25.14256
  * Hosoya (1971) Hosoya H (1971) Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons. Bull Chem Soc Jpn 44(9):2332–2339, https://doi.org/10.1246/bcsj.44.2332
  * Jacobs (1993) Jacobs AB (1993) Great Streets. The MIT Press, Cambridge
  * Jaynes (1957) Jaynes ET (1957) Information theory and statistical mechanics. Phys Rev 106(4):620–630, https://doi.org/10.1103/PhysRev.106.620
  * Jaynes (2003) Jaynes ET (2003) Probability Theory: The Logic of Science. Cambridge University Press, Cambridge, https://doi.org/10.1017/CBO9780511790423
  * Jiang and Claramunt (2004) Jiang B, Claramunt C (2004) Topological analysis of urban street networks. Environ Plan B 31(1):151–162, https://doi.org/10.1068/b306
  * Jiang et al. (2008) Jiang B, Zhao S, Yin J (2008) Self-organized natural roads for predicting traffic flow: A sensitivity study. J Stat Mech Theor Exp 2008(7):P07008, https://doi.org/10.1088/1742-5468/2008/07/P07008
  * Kalapala et al. (2006) Kalapala V, Sanwalani V, Clauset A, Moore C (2006) Scale invariance in road networks. Phys Rev E 73(2):026130, https://doi.org/10.1103/PhysRevE.73.026130
  * Knuth (1997) Knuth DE (1997) Seminumerical Algorithms, The Art of Computer Programming, vol 2, 3rd edn. Addison-Wesley, Reading
  * Landau and Binder (2015) Landau DP, Binder K (2015) A Guide to Monte Carlo Simulations in Statistical Physics, 4th edn. Cambridge University Press, Cambridge, https://doi.org/10.1017/CBO9781139696463
  * Lawrence (2019) Lawrence A (2019) Probability in Physics. Undergraduate Lecture Notes in Physics, Springer-Verlag, Cham, https://doi.org/10.1007/978-3-030-04544-9
  * MacKay (2003) MacKay DJC (2003) Information Theory, Inference, and Learning Algorithms. Cambridge University Press, Cambridge, URL https://dl.acm.org/doi/book/10.5555/971143
  * Mandelbrot (1982) Mandelbrot BB (1982) The Fractal Geometry of Nature. W. H. Freeman and Company, New York
  * Masucci et al. (2014) Masucci AP, Stanilov K, Batty M (2014) Exploring the evolution of London’s street network in the information space: a dual approach. Phys Rev E 89(1):012805, https://doi.org/10.1103/PhysRevE.89.012805
  * Metropolis et al. (1953) Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087–1092, https://doi.org/10.1063/1.1699114
  * Molinero et al. (2017) Molinero C, Murcio R, Arcaut E (2017) The angular nature of road networks. Sci Rep 7(1):4312, https://doi.org/10.1038/s41598-017-04477-z
  * Newman (2003) Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45(2):167–256, https://doi.org/10.1137/S003614450342480
  * Newman (2018) Newman MEJ (2018) Networks: an Introduction, 2nd edn. Oxford University Press, Oxford, https://doi.org/10.1093/oso/9780198805090.001.0001
  * Newman and Barkema (1999) Newman MEJ, Barkema GT (1999) Monte Carlo Methods in Statistical Physics. Oxford University Press, Oxford
  * OpenStreetMap (2004–2020) OpenStreetMap (2004–2020) OpenStreetMap Project. URL https://www.openstreetmap.org
  * Pemmaraju and Skiena (2003) Pemmaraju S, Skiena S (2003) Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press, Cambrige, https://doi.org/10.1017/CBO9781139164849
  * Porta et al. (2006) Porta S, Crucitti P, Latora V (2006) The network analysis of urban streets: A dual approach. Physica A 369(2):853–866, https://doi.org/10.1016/j.physa.2005.12.063
  * Press et al. (2007) Press WH, Teukolsky SA, Vetterling WT, Flannery BP (2007) Numerical Recipes: The Art of Scientific Computing, 3rd edn. Cambridge University Press, Cambridge
  * Romero-Maltrana (2015) Romero-Maltrana D (2015) Symmetries as by-products of conserved quantities. Stud Hist Philos Sci B 52:358–368, https://doi.org/10.1016/j.shpsb.2015.10.006
  * Rosvall et al. (2005) Rosvall M, Trusina A, Minnhagen P, Sneppen K (2005) Networks and cities: An information perspective. Phys Rev Lett 94(2):028701, https://doi.org/10.1103/PhysRevLett.94.028701
  * Rybski et al. (2019) Rybski D, Arcaute E, Batty M (2019) Urban scaling laws. Environ Plan B 46(9):1605–1610, https://doi.org/10.1177/2399808319886125
  * Stanley (1971) Stanley HE (1971) Introduction to Phase Transitions and Critical Phenomena, International Series of Monographs on Physics, vol 46. Oxford University Press, London
  * Stone (2015) Stone JV (2015) Information Theory: A Tutorial Introduction. Sebtel Press, Sheffield, https://doi.org/10.13140/2.1.1633.8240
  * Tribus (1961) Tribus M (1961) Thermostatics and Thermodynamics. University Series in Basic Engineering, Van Nostrand, Princeton, URL https://hdl.handle.net/2027/mdp.39015001333361
  * Viana et al. (2013) Viana MP, Strano E, Bordin P, Barthélemy M (2013) The simplicity of planar networks. Sci Rep 3:3495, https://doi.org/10.1038/srep03495
  * Watts and Strogatz (1998) Watts DJ, Strogatz SH (1998) Collective dynamics of ‘small-world’ netwoks. Nature 393(6684):440–442, https://doi.org/10.1038/30918