# A note on solving the envy-free perfect matching problem with qualities of
items

Marcos Salvatierra
Normal Superior School
Amazonas State University

###### Abstract

In the envy-free perfect matching problem, $n$ items with unit supply are
available to be sold to $n$ buyers with unit demand. The objective is to find
allocation and prices such that both seller’s revenue and buyers’ surpluses
are maximized – given the buyers’ valuations for the items – and all items
must be sold. A previous work has shown that this problem can be solved in
cubic time, using maximum weight perfect matchings to find optimal envy-free
allocations and shortest paths to find optimal envy-free prices. In this work,
I consider that buyers have fixed budgets, the items have quality measures and
so the valuations are defined by multiplying these two quantities. Under this
approach, I prove that the valuation matrix have the inverse Monge property,
thus simplifying the search for optimal envy-free allocations and,
consequently, for optimal envy-free prices through a strategy based on dynamic
programming. As result, I propose an algorithm that finds optimal solutions in
quadratic time.

_Keywords_ combinatorial optimization $\cdot$ envy-free pricing $\cdot$
polynomial-time algorithm $\cdot$ dynamic programming

##  1 Introduction

Suppose a seller wants to sell $n$ similar items – for example, cars – and $n$
buyers are interested in buying one car each. The cars have different quality
attributes such brand, numbers of doors, metallic paint, steering assistance,
etc. Moreover, each buyer has a budget available to purchase a car. In this
way, the seller will estimate the valuation that each buyer will have for each
car, multiplying the buyer’s budget by the quality measure of the car.
Furthermore, each buyer wants to be happy with the price of the car sold to
him/her, in the sense that the price is less than or equal to his/her
valuation for that car, and furthermore, the car sold to him/her is the one
that gives him/her the greatest surplus, i.e., the difference between the
valuation for the car and the price of the car sold to him/her is greater than
or equal to any other difference between the valuation and the price of
another car.

So, formally, we have a set of $n$ items with unit supply, a set of $n$ buyers
with unit demand, each buyer $i$ has a budget $v_{i}$, each item $j$ has a
quality measure $q_{j}$, and then the valuation of buyer $i$ for item $j$ is
given by $v_{i,j}=v_{i}q_{j}$. The valuation matrix is defined by
$V=(v_{i,j})\in I\\!\\!R_{>0}^{n\times n}$. The seller needs to decide which
item to sell to which buyer. In terms of decision variables, $x_{i,j}=1$ if
buyer $i$ buys item $j$ and $x_{i,j}=0$ otherwise. In addition, the prices set
should maximize both the seller’s revenue and the buyers’ surpluses, i.e.,
should maximize $\sum_{j=1}^{n}p_{j}$ and should satisfy
$v_{i,j}x_{i,j}-p_{j}\geq v_{i,k}x_{i,j}-p_{k}$ for all $k\neq j$, if buyer
$i$ buys item $j$, with $v_{i,j}x_{i,j}\geq p_{j}$. Finally, the seller needs
to sell all items, i.e., $\sum_{j=1}^{n}x_{i,j}=1$ for all $i=1,\ldots,n$.

In this scenario, we say that the seller needs to find an optimal envy-free
allocation for the buyers and optimal envy-free prices for the items. This is
a special case of the envy-free perfect matching problem, which was studied by
Arbib et al. (2019). This last problem, in turn, is a particular case of the
unit-demand envy-free pricing problem, proposed by Guruswami et al. (2005).
Other particular cases of the unit-demand envy-free pricing problem that can
be solved in polynomial-time were also studied by Günlük (2008), Chen et al.
(2011) and Salvatierra et al. (2021), for example.

Having made these considerations, the main objective of this work is to
propose an algorithmic strategy using a dynamic programming approach that
finds optimal envy-free allocations and optimal envy-free prices in quadratic
time for this particular case, thus reducing the time complexity proved by
Arbib et al. (2019) for the more general envy-free perfect matching problem.

##  2 Mathematical properties

First, let’s analyze the properties of the valuation matrix. Without loss of
generality, for the remainder of this section we will assume that $v_{i}\geq
v_{j}$ and $q_{i}\geq q_{j}$ if $i<j$. In this way, we have $v_{i,j}\geq
v_{i,k}$ if $j<k$ and $v_{i,j}\geq v_{r,j}$ if $i<r$. So we have, for $i<j$,

$v_{i}(q_{i}-q_{j})\geq v_{j}(q_{i}-q_{j})\Rightarrow
v_{i}q_{i}-v_{i}q_{j}\geq v_{j}q_{i}-v_{j}q_{j}\Rightarrow
v_{i}q_{i}+v_{j}q_{j}\geq v_{j}q_{i}+v_{i}q_{j}.$

Therefore, $v_{i,i}+v_{j,j}\geq v_{j,i}+v_{i,j}$. This property is precisely
the so called inverse Monge property. Burkard et al. (1996) showed that such
matrices has the maximum trace in the main diagonal, i.e., the identity matrix
is the permutation that maximizes $tr(\Pi^{T}V)$, where $\Pi$ is a permutation
matrix, and hence the optimal envy-free allocation for our problem is
$x_{i,j}=1$ if $i=j$ and $x_{i,j}=0$, otherwise. From the point of view of
graph theory, the identity matrix defines a maximum weight perfect matching in
the bipartite graph whose costs are in matrix $V$, and from an economic
perspective, this allocation maximizes social welfare, i.e., maximizes
$\sum_{i=1}^{n}\sum_{j=1}^{n}x_{i,j}v_{i,j}$.

Once the optimal envy-free allocation is found, it remains to find the optimal
envy-free prices. It can be clearly noted that the buyer with the lowest
valuation for an item will buy this item for this price. I will formally prove
this fact in the following proposition:

######  Proposition 1.

The optimal envy-free price of item $n$ is $p_{n}=v_{n,n}$.

###### Proof.

Indeed, if $p_{n}<v_{n,n}$, then the total revenue earned from selling the
items will be decreased by $v_{n,n}-p_{n}$, instead of item $n$ being sold at
the price $v_{n,n}$. On the other hand, if $p_{n}>v_{n,n}$, then the surplus
of buyer $n$ will be negative, and the item will not be allocated to him. ∎

Now that we have the lowest optimal envy-free price set, a natural way to find
the remaining optimal envy-free prices is to search upwards. Let’s think
intuitively: in a $2\times 2$ valuation matrix, we already know that item 2 is
allocated to buyer 2, and that the optimal envy-free price is $v_{2,2}$. Then,
we must calculate a price for buyer 1 based on $v_{1,1}$ that maximizes his
surplus. Thus, we must calculate surplus of buyer 1 if he were to buy item 2,
that is, we must calculate $v_{1,2}-v_{2,2}$. Since $v_{1,2}-v_{2,2}\geq 0$,
this value should be the maximum surplus of buyer 1, so the optimal envy-free
price of item 1 will be $p_{1}=v_{1,1}-(v_{1,2}-v_{2,2})$. Continuing with
this reasoning, the next optimal envy-free prices will be calculated by
observing the surpluses of the next buyers with the optimal envy-free prices
already found.

This intuitive way of finding optimal envy-free prices will be generalized in
the following lemma:

######  Lemma 1.

If the $k>1$ lowest optimal envy-free prices have already been found, the next
optimal envy-free price $p_{n-k}$, in ascending order, is found as follows:

$p_{n-k}=v_{n-k,n-k}-\max_{i=(n-k+1),\ldots,n}\\{v_{n-k,i}-p_{i}\\}$

###### Proof.

Indeed, the surpluses of buyer $n-k$ are: rCl v_n-k, n-k+1& \- p_n-k+1
v_n-k, n-k+2 - p_n-k+2
⋮
v_n-k, n - p_n

Thus, the maximum of these values must be subtracted from $v_{n-k,n-k}$ for
the envy-free condition to hold. Furthermore, if any other value greater than
this maximum is subtracted from $v_{n-k,n-k}$, the resulting price will
decrease the seller’s revenue. ∎

##  3 Algorithm for the problem

The mathematical properties of the problem, explored in the previous section,
allows me to present the algorithm below that finds an optimal envy-free
allocation and optimal envy-free prices, given as input: $n$ (the number of
items and buyers), $v_{i}$ for all $i=1,\ldots,n$ (the buyers’ valuations) and
$q_{j}$ for all $j=1,\ldots,n$ (the items qualities).

  1. 1.

Do a permutation $\pi:\\{1,2,\ldots,n\\}\rightarrow\\{1,2,\ldots,n\\}$ such
that $v_{\pi^{-1}(1)}\geq v_{\pi^{-1}(2)}\geq\ldots\geq v_{\pi^{-1}(n)}$.

  2. 2.

Do a permutation $\sigma:\\{1,2,\ldots,n\\}\rightarrow\\{1,2,\ldots,n\\}$ such
that $q_{\sigma^{-1}(1)}\geq q_{\sigma^{-1}(2)}\geq\ldots\geq
q_{\sigma^{-1}(n)}$.

  3. 3.

Construct the valuation matrix $V=(v_{i,j})$ such that
$v_{i,j}=v_{\pi^{-1}(i)}q_{\sigma^{-1}(j)}$.

  4. 4.

Allocate item $\pi^{-1}(i)$ to buyer $\pi^{-1}(i)$ for all $i=1,2,\ldots,n$.

  5. 5.

Set price $p_{\pi^{-1}(n)}=v_{n,n}$.

  6. 6.

Use Lemma 1 to find the remaining optimal envy-free prices.

After exhibiting the algorithm designed to solve the problem in question, I
will present the main result of this work.

######  Theorem 1.

The envy-free perfect matching problem with qualities of items can be solved
in $O(n^{2})$ time.

###### Proof.

Steps 1 and 2 can be performed in $O(n^{2})$ time by any sorting algorithm.
Step 3 clearly can be performed in $O(n^{2})$ time, since is a construction of
a $n$-by-$n$ matrix. Step 4 performs $O(n)$ time operations and Step 5
performs a single $O(1)$ time operation. Finally, Step 6 performs $n-1$
operations of searching maximum values and simple arithmetic computations, so
in $O(n^{2})$ time. Therefore, the overall time complexity for finding optimal
solutions for the envy-free perfect matching problem with qualities of items
is $O(n^{2})$. ∎

##  4 Conclusions

In this work, I addressed the envy-free perfect matching problem by
incorporating an element into it: the items have quality measures. To take
these aspects into account is not an artificial consideration, but it can be
found in concrete situations, and even in the literature we can find works
that explore these aspects about the items, such as the study by Chen et al.
(2016).

In this way, I showed that the valuation matrix has the inverse Monge
property, thus simplifying the search for optimal envy-free allocations and
optimal envy-free prices. Furthermore, we showed that this property of the
valuation matrix provides an optimal substructure for the problem, enabling
the development of a dynamic programming strategy that finds optimal solutions
to the problem in quadratic time.

Although many particular cases of the unit-demand envy-free pricing problem
can be optimally solved in polynomial-time, an interesting research question
is to develop fast heuristics and/or approximation algorithms aiming at
experimental treatments of the problem when dealing with instances of large
magnitude, such as the proposals by Shioda et al. (2011) and Myklebust et al.
(2016), for example.

This research did not receive any specific grant from funding agencies in the
public, commercial, or not-for-profit sectors.

## References

  * Arbib et al. [2019] C. Arbib, O.E. Karaşan, and M.Ç. Pinar.  On envy-free perfect matching.  _Discrete Applied Mathematics_ , 261:22 – 27, 2019.  ISSN 0166-218X.  doi:https://doi.org/10.1016/j.dam.2018.03.034.  GO X Meeting, Rigi Kaltbad (CH), July 10–14, 2016.
  * Guruswami et al. [2005] Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry.  On profit-maximizing envy-free pricing.  In _Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’05, pages 1164–1173, Philadelphia, PA, USA, 2005\. Society for Industrial and Applied Mathematics.  ISBN 0-89871-585-7.  URL http://dl.acm.org/citation.cfm?id=1070432.1070598.
  * Günlük [2008] Oktay Günlük.  A pricing problem under monge property.  _Discrete Optimization_ , 5(2):328–336, 2008\.
  * Chen et al. [2011] Ning Chen, Arpita Ghosh, and Sergei Vassilvitskii.  Optimal envy-free pricing with metric substitutability.  _SIAM Journal on Computing_ , 40(3):623–645, 2011\.
  * Salvatierra et al. [2021] Marcos M. Salvatierra, Mario Salvatierra, and Juan G. Colonna.  Short communication: Optimally solving the unit-demand envy-free pricing problem with metric substitutability in cubic time.  _Algorithms_ , 14(10), 2021.  ISSN 1999-4893.  doi:10.3390/a14100279.  URL https://www.mdpi.com/1999-4893/14/10/279.
  * Burkard et al. [1996] Rainer E Burkard, Bettina Klinz, and Rüdiger Rudolf.  Perspectives of monge properties in optimization.  _Discrete Applied Mathematics_ , 70(2):95–161, 1996.
  * Chen et al. [2016] Ning Chen, Xiaotie Deng, Paul W. Goldberg, and Jinshan Zhang.  On revenue maximization with sharp multi-unit demands.  _J. Comb. Optim._ , 31(3):1174–1205, April 2016\.  ISSN 1382-6905.  doi:10.1007/s10878-014-9817-y.
  * Shioda et al. [2011] Romy Shioda, Levent Tunçel, and Tor G. J. Myklebust.  Maximum utility product pricing models and algorithms based on reservation price.  _Comp. Opt. and Appl._ , 48(2):157–198, 2011\.  doi:10.1007/s10589-009-9254-5.
  * Myklebust et al. [2016] Tor G. J. Myklebust, M. A. Sharpe, and Levent Tunçel.  Efficient heuristic algorithms for maximum utility product pricing problems.  _Computers & OR_, 69:25–39, 2016.  doi:10.1016/j.cor.2015.11.013.


# Transport collapse in dynamically evolving networks

Geoffroy Berthelotmissing Institut National du Sport, de l’Expertise et de la
Performance (INSEP), 75012 Paris, France  Research Laboratory for
Interdisciplinary Studies (RELAIS), 75012 Paris, France  Liubov
Tupikinamissing The Center for Research and Interdisciplinarity, Paris, France
75004  Bell Labs Nokia, France  Min-Yeong Kangmissing Medipixel, Inc., 04037
Seoul, South Korea  Jérôme Dedecker  Université de Paris, France  Denis
Grebenkovmissing Laboratoire de Physique de la Matière Condensée (UMR 7643),
CNRS – Ecole Polytechnique, IP Paris, 91128 Palaiseau, France

###### Abstract

Transport in complex networks can describe a variety of natural and human-
engineered processes including biological, societal and technological ones.
However, how the properties of the source and drain nodes can affect transport
subject to random failures, attacks or maintenance optimization in the network
remain unknown. In this paper, the effects of both the distance between the
source and drain nodes and of the degree of the source node on the time of
transport collapse are studied in scale-free and lattice-based transport
networks. These effects are numerically evaluated for two strategies, which
employ either transport-based or random link removal. Scale-free networks with
small distances are found to result in larger times of collapse. In lattice-
based networks, both the dimension and boundary conditions are shown to have a
major effect on the time of collapse. We also show that adding a direct link
between the source and the drain increases the robustness of scale-free
networks when subject to random link removals. Interestingly, the distribution
of the times of collapse is then similar to the one of lattice-based networks.

Keywords— transport in complex systems, resistor grid, scale-free network

##  1 Introduction

Transport in complex (or scale-free) networks is relevant for various natural
and artificial systems [1, 2, 3, 4]. These networks have a degree distribution
that follows a power law $P(k)\sim k^{-\gamma}$ (or truncated power law) [5,
6], where $k$ is the node degree and $\gamma$ is an exponent. One often
considers resistor networks, in which the transport is modeled as a current
(or flux) generated by a source and transiting throughout the links to a
drain. Nodes are assigned with electric potentials, while each link has a
current (or flux). When applying a difference of potential between the source
and drain nodes, the transport self-organizes into a peculiar arborescent
configuration, with a tree-like structure emerging from the source and another
one converging to the drain [7]. These two trees merge into a large cluster
with evenly distributed potentials, the so-called Quasi-Equipotential Cluster
(QEC) [7, 8]. The QEC concentrates low fluxes, while high fluxes are instead
concentrated in the links originating from the source and terminating at the
drain [7].

Natural and artificial systems forming such networks can be altered with time,
and often exhibit properties related to the percolation phenomena, where links
are lost or destroyed with time. For instance, protein bonds may be lost with
time in proteins networks, while proteins, the nodes of the network, remain
present [9]. Other examples include the lung airway tree [10], braided streams
[11, 12], social networks [13] and transportation networks for passengers [14,
15, 16, 17]. Previous studies shown that scale-free networks are fragile and
prone to collapse. This was demonstrated theoretically [18] and for multiple
dynamical real-world systems, such as (species) evolution and ecosystems [19,
20], the financial sector [21] and social networks [22]. The stability of such
systems can be jeopardized with the removal of just one element, possibly
leading to collapse [23, 24, 25, 26, 27]. One well-known topological feature
that improves the robustness of the network is the existence of cycles, i.e.
directed closed paths whose only repeated vertices are the first and the last.
They were shown to provide stability to systems such as biochemical networks
for instance [28, 29].

We previously studied three different strategies of a resistor network
evolution by progressive removal of the weakest, random or strongest link at
each time step $t$. These strategies can model respectively intentional
attacks on the network, its random failures, and progressive network
optimizations when the weakest and thus least useful links are removed (the
pseudo-Darwinian strategy). In all three cases, transport eventually collapses
at a time $t_{c}$, which depends on the chosen evolution strategy and a set of
network parameters. In particular, it was shown that low $\gamma$ values yield
high $t_{c}$ values [30]. In fact, low $\gamma$ results in an increased
proportion of hubs (nodes with a high degree), which in turn increases
redundancy, i.e. the number of paths between each pair of nodes in the network
[31]. This is a key element to improve network robustness and therefore to
delay the time of collapse $t_{c}$. Based on our former simulations, the
evolution strategy which produced the smallest $t_{c}$ values corresponded to
the removal of the strongest links, i.e. the links which hold the largest
fluxes. These links are directly connected to the source and drain nodes and
removing such links results in a rapid disconnection of the source or the
drain from the rest of the network and thus the transport collapse. On the
opposite, largest values of $t_{c}$ were obtained using the pseudo-Darwinian
strategy when removing links with the lowest fluxes. As stated above, such
links are located in the QEC and thus contribute less to the transportation
system [30]. Finally, values of $t_{c}$ for the random evolution usually take
place between the two above strategies. As a consequence, the evolution
strategies with the removal of the weakest and the strongest links can serve
to identify lower and upper bounds for $t_{c}$ values respectively. However,
beside the parameter $\gamma$, the other topological properties affecting
$t_{c}$ remain unclear.

In this paper, we investigate how the degree of the source and the distance
(in terms of nodes) between the source and drain nodes can affect $t_{c}$.
These two properties are studied in the context of percolation, in order to
understand what role they may play in delaying $t_{c}$. We also investigate
resistor grids with regular, lattice-based geometry, which are widely employed
as models for many problems in science and engineering [32, 33]. Our interest
in including these networks lies in their homogeneous topology, which can
serve as a reference for comparing the effects of the studied properties
(distance and degree). We only investigate finite $D$-dimensional lattice-
based networks, which can be constructed [34] and used in stealth [35],
sensors in robotics [36] or for energy dissipation in road or railroad
vehicles [37, 38] for instance. We also aim at studying how the dimensionality
can increase the robustness of such networks which can, in turn, help in
increasing circuit boards reliability.

##  2 Methods

In this section, we describe the construction and parameters of the networks,
which can be either scale-free networks (section 2.1) or lattice-based
networks (section 2.3). Each network (or graph [39]) is undirected and
contains a total of $N_{0}$ nodes and $L_{0}$ links. The transport in these
networks is modeled using two main elements (section 2.1). First, two nodes
are selected: one for the source and the other for the drain, such that the
transport starts from the source node and ends at the drain node. The
selection of the source and drain nodes can either be random or deterministic,
depending on the effect we aim to assess (see section 2.1 for a random
selection and section 3.1 for a specific selection of the source and drain
pair). Second, the transport mechanism is described by the Kirchhoff’s
equations, i.e. the sum of currents entering any node is equal to the sum of
currents leaving it. This basic rule ensures the conservation of charge in
electric circuits or the conservation of mass in transport systems. An
application of the electrical potential differences (voltage) between the
source and the drain nodes results in a direction of the current from the
source to the drain. In other words, the flux self-organizes from the source
to the drain [7]. This setup can serve as an analogy to transport for several
real world phenomena (see references in the introduction). We then detail two
strategies of network evolution, in which we progressively remove links at
each time steps depending on the chosen strategy (section 2.2). The evolution
stops when either the transport is no more possible between the source and
drain, or when a portion of the network is separated from the rest. These
conditions define the time of collapse, which depends on the initial network,
the choice of the source and drain, and the network evolution. If at least one
of these elements is random (e.g., the random evolution strategy), the time of
collapse is a random variable, and we are interested in characterizing its
probability density via numerical simulations.

###  2.1 Network structure and transport

We construct a random scale-free network with $N_{0}$ nodes using the
uncorrelated configuration model with a given degree exponent $\gamma$ [40]
(Fig. 1). In each realization of the network with a prescribed exponent
$\gamma$, we select a pair of source and drain nodes, at which the potential
is fixed to be 1 and 0, respectively. In some cases, this selection is
performed randomly (uniformly) among all pairs of nodes. In other cases, we
run simulations for all pairs of nodes. The rule of the selection will be
specified for each study. As a permutation of the source and the drain in any
pair does not change the (absolute values of) fluxes and potentials (see
below), such two choices lead to the same evolution and result in the same
time of collapse. For this reason, one can reduce the total number of pairs of
distinguishable nodes, $N_{0}(N_{0}-1)$, to the twice smaller number of pairs
of indistinguishable nodes, $N_{0}(N_{0}-1)/2$. The flux through the network
satisfies conservation of mass [41]: at every node $i$ we impose
$\sum_{j}q_{i,j}=0$, where $q_{ij}$ is the flux through the link connecting
nodes $i$ and $j$. These fluxes are calculated as:

$q_{i,j}=-\left(P_{i}-P_{j}\right)$ (1)

where $P_{i}$ and $P_{j}$ are the potentials at the nodes $i$ and $j$
respectively, and we set the unit resistance for all links. Note that we have
studied similar networks with distance-dependent resistances and showed their
marginal effect on the transport [7, 30]. In such a setup, the system of
linear Kirchhoff’s equations [42] describing the transport in a network is:

$-\mathbf{L}^{\prime}\mathbf{P}^{\prime\top}=0$ (2)

with $\top$ denoting transposition, $\mathbf{L}^{\prime}$ the Laplacian matrix
of $N_{0}\times N_{0}$ elements and $\mathbf{P}^{\prime\top}$ the $N_{0}\times
1$ column vector of known (fixed) and unknown potentials. Each element of
$\mathbf{L}$ is defined as:

$\mathbf{L}_{i,j}=\begin{cases}k_{i}&\text{if $i=j$}\\\ -1&\text{if node
$i\neq j$, and $i$ is adjacent to node $j$}\\\ 0&\text{otherwise}\end{cases}$
(3)

After removing the source and drain nodes, at which the potentials are fixed,
the above system can be rewritten in the following form:

$\mathbf{L}\mathbf{P}^{\top}=\mathbf{S}^{\top}$ (4)

where $\mathbf{P}^{\top}$ is the vector of $N_{0}-2$ unknown potentials,
$\mathbf{L}$ is the Laplacian matrix of $(N_{0}-2)\times(N_{0}-2)$ elements
obtained from $\mathbf{L}^{\prime}$ after removal of two lines and two columns
corresponding to the source and drain nodes, and $\mathbf{S}^{\top}$ is a
$(N_{0}-2)\times 1$ column vector, in which each element corresponds to the
total flux exiting each node $i$:

$\mathbf{S}=\begin{cases}1&\text{if node $i$ is adjacent to the source
node}\\\ 0&\text{otherwise}\end{cases}$ (5)

The system described in eq. (4) is solved for $\mathbf{P}$ numerically using a
custom routine in Matlab. The distributions of potentials on nodes and fluxes
in links are then obtained. In particular, we compute the total flux $Q$, that
is the sum of fluxes exiting from the source node.

Let us come back to the above statement that the exchange of roles between the
source and the drain does not change the total flux. This statement follows
directly from the linearity of the Kirchhoff’s equations and zero flux
condition at each node. In fact, if $\mathbf{P}^{\prime}$ is a solution of Eq.
(2), then $\mathbf{P}^{\prime\prime}=\mathbf{I}-\mathbf{P}^{\prime}$ is also a
solution because $\mathbf{L}^{\prime}\mathbf{I}=0$, where
$\mathbf{I}=(1,1,\ldots,1)^{\top}$. But the removal of the source and drain
nodes from $\mathbf{P}^{\prime\prime}$ is equivalent to permuting the source
and the drain in the corresponding vector $\mathbf{S}$ in Eq. (4). In other
words, one can first shift the potential by $-1$ (i.e., the source has the
potential $0$ instead of $1$ and the drain has potential $-1$ instead of $0$)
and then multiply them by $-1$. This is of course consistent with the fact
that an electric potential in physics is defined up to a constant. This
property can have practical implications for real life networks that can also
be described by resistor grids, such as supply chain networks, water
distribution systems, road/air transportation networks, electric power
networks and social networks for instance [43, 44, 45, 46, 47].

Figure 1: Examples of network realizations. Scale-free networks with
$\gamma=\\{2,3,4\\}$ and $N_{0}=100$ are illustrated in panels (a) - (c). Grid
networks with reflecting boundary conditions and dimensions $D=\\{2,3\\}$ and
sizes $N_{0}=\\{100,64\\}$ are presented in panels (d), (e).

###  2.2 Network evolution

The constructed network evolves at discrete steps according to a pre-selected
strategy. At each evolution step, we solve the system of Kirchhoff’s equations
(4) and remove either the weakest link (pseudo-Darwinian strategy) or a random
link (random strategy) [30]. After a link removal, we also remove “dead-end”
nodes (i.e., nodes whose degree equals $1$), thus requiring any existing node
after an evolutionary step to have at least degree $2$. Each evolution step is
associated with “time” $t$, and $t_{0}=0$ being the initial time, when the
evolution starts. We denote by $Q_{0}$ and $L_{0}$ the total flux and the
number of links respectively at $t_{0}$.

We aim at estimating the time of collapse $t_{c}$ of the network. The
evolution ends when at least one of the following conditions is met: (i) no
path exists between the source and the drain (i.e. the source and drain are
disconnected), (ii) the source or the drain is removed from the network, (iii)
a portion of the network – a subgraph containing more than one node – is
disconnected from the rest of the network. This last condition is implemented
to reflect natural systems such as energy, transportation or biological
networks, where it is not desirable to remove a portion of nodes from the rest
of the network. The end of the simulation defines $t_{c}$, corresponding to a
situation where the transport can no longer be maintained through the whole
network.

We generally obtain a distribution of $t_{c}$ by running many simulations for
a given set of network parameters. The total number of simulations is given as
$n_{\rm r}\cdot n_{\rm p}\cdot n_{\rm s}$, where $n_{\rm r}$ is the number of
random realizations of the network, $n_{\rm p}$ is the number of choices of
the source-drain pair (either $n_{\rm p}=1$ for a single random choice or
$n_{\rm p}=N_{0}(N_{0}-1)/2$) for a systematic analysis of all pairs, and
$n_{\rm s}$ is the number of random evolutions (note that $n_{\rm s}=1$ for
the pseudo-Darwinian strategy, which is deterministic).

###  2.3 Comparison with lattice-based networks

For comparison, we also investigate the transport in lattice-based networks of
dimension $D=\\{2,3,4\\}$. Such a network consists of integer points on
$\\{1,\ldots,N\\}^{D}$, each of them being connected to its nearest neighbors
(Fig. 1). We consider two boundary conditions: periodic boundary condition
(when each node degree $k$ is equal to $2D$) and reflecting (also known as
“open”) boundary condition (with $k\in[D,2D]$). We aim here to reveal the role
of topological properties of the network, which are different between lattice-
based and scale-free networks. In particular, we assess whether lattice-based
networks are more robust than scale-free ones for both evolution strategies.
Another point of interest is to assess the effect of dimensionality and of the
type of boundary conditions on $t_{c}$. To reduce finite-size effects, we
normalize each $t_{c}$ by $L_{0}$.

##  3 Results

###  3.1 Effect of the distance between source and drain

Figure 2: Effect of distance $\Delta$ between the source and the drain on the
distribution of the time of collapse $t_{c}$ for scale-free networks of size
$N_{0}=100$. (a) $t_{c}$ as a function of $\Delta$ for a single network
realization ($n_{\rm r}=1$) for each of three values of $\gamma=\\{2,3,4\\}$
and the pseudo-Darwinian strategy ($n_{\rm s}=1$). (b) The probability density
of $t_{c}$ for $n_{\text{r}}=1000$ realizations, $\gamma=2$ and the random
strategy ($n_{\rm s}=1$). (c \- e) The probability density of $t_{c}$ for one
realization ($n_{\text{r}}=1$) and $n_{\rm s}=1000$ simulations for the random
strategy with different values of $\gamma$: $\gamma=2$ (c), $\gamma=3$ (d),
and $\gamma=4$ (e). Probability densities in panels (b \- e) are smoothed
using an Epanechnikov kernel.

We start by studying the effect of the distance $\Delta$ (measured in nodes)
between the source and the drain on the time of collapse $t_{c}$ of a scale-
free network for a given $\gamma$ value. Note that $\Delta=0$ means that there
is a direct link between the source and the drain. Figure 2 summarizes our
results for a scale-free network of size $N_{0}=100$.

First, we produce a single (random) realization of the scale-free network
($n_{\text{r}}=1$) and consider all possible pairs of source and drain nodes.
For each pair, we run a pseudo-Darwinian strategy and compute the time of
collapse $t_{c}$. This simulation yields $n_{\rm p}=N_{0}(N_{0}-1)/2=4950$
values of $t_{c}$, which are grouped according to the distance $\Delta$ (see
panel (a)). As the pseudo-Darwinian strategy is deterministic, different
values of $t_{c}$ can be interpreted, to some extent, as the result of a
“random choice” of the source and drain nodes. For $\gamma=\\{2,3\\}$, the
values of $t_{c}$ for each $\Delta$ are almost identical, with a minor
variation. In other words, the time of collapse is mainly determined by the
distance $\Delta$ between the source and the drain and is almost independent
of their particular location in the network. Due to a finite-size effect
($N_{0}=100$), the maximal value of $\Delta$ is limited to $6$ for $\gamma=2$
and to $8$ for $\gamma=3$. The behavior is different for $\gamma=4$. One sees
a much bigger variation of $t_{c}$ for each value of $\Delta$, meaning that
the distance $\Delta$ alone does not determine the time of collapse, and the
location of the source and drain nodes does matter here. This qualitative
difference originates from the structure of the scale-free network, which has
a larger proportion of “hubs” for smaller $\gamma$.

The above results were obtained for a particular random realization of the
network. To study the effect of stochasticity (i.e. node degree and wiring),
we generated $n_{\text{r}}=1000$ random realizations of the scale-free network
with $N_{0}=100$ and $\gamma=2$. For each realization, we consider all
possible pairs of the source and drain nodes and for each assignment, we
perform the pseudo-Darwinian evolution to determine the time of collapse. In
this way, we obtain $n_{\text{r}}N_{0}(N_{0}-1)/2$ values of $t_{c}$. We split
them into groups according to the distance $\Delta$ and then plot a
probability density of $t_{c}$ (a rescaled empirical histogram) for each group
on panel (b). One sees that these histograms are still relatively narrow (with
the standard deviation $\sim 10$ being much smaller than the mean) but exhibit
a larger variation than for a single realization of the network. It is
expected that randomness of the network structure broads the distribution of
the time of collapse. As $\Delta$ increases, the maximum of the probability
density shifts to the left (to smaller $t_{c}$) suggesting that the network
becomes less robust. In other words, large $\Delta$ is generally associated
with small $t_{c}$.

It is instructive to check whether this statement remains valid for the random
strategy. For this purpose, we generated a single realization of the network
and performed $n_{\rm s}=1000$ random evolutions of this network until its
collapse. As previously, we consider all pairs of the source and drain nodes.
In this way, we generated $1000N_{0}(N_{0}-1)/2$ values of $t_{c}$ that were
split into groups according to the distance $\Delta$. The probability
densities of $t_{c}$ for each group are shown on panels (c), (d), and (e) for
$\gamma=2,3,4$, respectively. One observes a similar trend that the maximum of
the distribution is shifted to the left as $\Delta$ increases. In turn, these
distributions are more skewed than that of panel (b) for the pseudo-Darwinian
strategy.

###  3.2 Effect of artificial connection

Since the distance $\Delta$ strongly affects the time of collapse, one may
wonder how an addition of a direct link between the source and the drain can
change $t_{c}$ for two strategies. The direct link resets the distance
$\Delta$ of an already existing network to $0$. For this purpose, we fix
$N_{0}=100$ amd $\gamma=2$, impose $\Delta\geq 4$ and compare two empirical
distributions of $t_{c}$, without and with an artificial connection. To
fulfill the condition $\Delta\geq 4$, we randomly select a pair of nodes and
check whether their distance is greater or equal to $4$; if yes, these nodes
are assigned to be the source and the drain; otherwise, a new pair is
selected, and so on, until the condition is satisfied. Figure 3 summarizes the
results for two strategies in three settings.

Figure 3: Effect of adding a direct link between the source and the drain for
a scale-free network with $N_{0}=100$, $\gamma=2$ and a single choice of the
source-drain pair ($n_{\rm p}=1$) under the constraint $\Delta\geq 4$. In
panel (a), the probability density of $t_{c}$ is shown for the random strategy
and a single realization ($n_{\text{r}}=1$). A total of $n_{\rm s}=2\times
10^{4}$ evolutions are performed for each of the two constructions (with and
without the direct link). Similarly in (b), the probability density of $t_{c}$
is given for the same strategy, but using $n_{\text{r}}=10^{3}$ realizations
and $n_{\rm s}=10^{4}$ simulations for each realization. In panel (c), the
distribution for $t_{c}$ is given for the pseudo-Darwinian strategy, using one
evolution per realization ($n_{\rm s}=1$) and $n_{r}=10^{3}$ realizations of
the network for each of the two constructions. Probability densities are
smoothed using an Epanechnikov kernel.

(i) We start with a single random realization of a scale-free network ($n_{\rm
r}=1$), which is independently evolved $n_{\rm s}=2\times 10^{4}$ times by
random strategy to get an empirical distribution of $t_{c}$. Then, a link
between the source and the drain is added to the initially constructed
network, such that $\Delta$ now equals 0, and $2\times 10^{4}$ evolutions are
performed again to get another distribution of $t_{c}$. Panel (a) compares two
empirical distributions. One sees that adding a single link between the source
and drain nodes delays the time of collapse. Moreover, it produces an
important change in the distribution of $t_{c}$, switching the mode of the
distribution from low to high values. Interestingly, the modified distribution
looks similar to the distribution for lattice-based networks (Fig. 5), whose
properties are controlled by dimensionality $D$ and boundary conditions (see
below).

(ii) To study the effect of stochasticity, we then constructed $n_{r}=10^{3}$
realizations of the scale-free network, and each of these networks is evolved
$n_{\rm s}=10^{4}$ times by the random strategy to get the distribution of
$t_{c}$. Another distribution is obtained after connecting the source and the
drain for each initial network and evolving it $10^{4}$ times again. Panel (b)
compares two distributions, which are similar to those shown in panel (a). We
conclude that stochasticity of the network does not matter here.

(iii) Finally, we perform simulations similar to (ii), but the random strategy
is replaced by the pseudo-Darwinian strategy. One can see on panel (c) that
two distributions of $t_{c}$ are almost identical, i.e., the effect of an
artificial connection is minor here. In fact, the inclusion of the direct link
just requires one supplementary step to disconnect the source and the drain,
thus replacing $t_{c}$ by $t_{c}+1$. This is not surprising because the direct
link supports the strongest current and is thus removed at the very end of the
pseudo-Darwinian evolution.

###  3.3 Effect of the degree of the source

Figure 4: Effect of the degree $k_{S}$ of the source on the distribution of
$t_{c}$ for scale-free networks with size $N_{0}=100$. Panel (a): $t_{c}$ as a
function of $k_{S}$ for the pseudo-Darwinian strategy applied to a single
random realization of the network ($n_{\rm r}=1$) for each value of $\gamma$.
Panel (b): the probability density of $t_{c}$ for the pseudo-Darwinian
strategy applied to $n_{\text{r}}=1000$ random realizations of the scale-free
network with $\gamma=2$. Panels (c \- e): the probability density of $t_{c}$
for $n_{\rm s}=1000$ random strategy evolutions of a single random realization
($n_{\text{r}}=1$) of the network with different values of $\gamma$:
$\gamma=2$ (c), $\gamma=3$ (d), and $\gamma=4$ (e). Probability densities in
panels (b \- e) are smoothed using an Epanechnikov kernel.

The degree $k_{S}$ of the source node is another quantity that may affect the
distribution of $t_{c}$. To investigate its role, we undertook a similar
procedure as in Sec. 3.1, namely, we first considered the pseudo-Darwinian
strategy for a single realization of the scale-free network, then investigated
the effect of stochasticity, and finally compared to the evolution by random
strategy (Fig. 4). Panels (a) and (b) show that the distribution of $t_{c}$ is
almost independent of the degree of the source when using the pseudo-Darwinian
strategy. On the opposite, the random strategy results in an increase of
$t_{c}$ when $k_{S}$ is greater than 2, see Fig. 4 (c)-(e). The same results
are obtained for the degree of the drain (not shown).

###  3.4 Comparison with lattice-based networks

Figure 5: Effect of the distance $\Delta$ between the source and the drain on
the time of collapse $t_{c}$ for lattice-based networks of various dimensions
$D=\\{2,3,4\\}$ that evolve via the random strategy. The shown probability
densities of $t_{c}$ are obtained from $n_{\rm s}=1000$ random evolutions for
both open boundary conditions (dotted lines) and periodic ones (solid lines).
Probability densities are smoothed using an Epanechnikov kernel.

Let us now analyze how the topological structure of the network may affect the
time of collapse. For this purpose, we compare the previous results for scale-
free networks to those obtained for lattice-based networks. We fix the lattice
dimension $D$, its size $N_{0}=N^{D}$, and the type of boundary conditions
(periodic or open). For each pair of the source and the drain (i.e., $n_{\rm
p}=N_{0}(N_{0}-1)/2$), we run $n_{\rm s}=1000$ evolutions by the random
strategy to obtain the distribution of $t_{c}$ (Fig. 5). Contrarily to the
case of scale-free networks (see Fig. 2), there is only a little effect of
$\Delta$ on the distribution of $t_{c}$ in all considered lattice-based
networks. This effect is stronger for large $\Delta$ but this result may
originate from finite-size effects (a limited number of configurations with
large $\Delta$). Such networks have a homogeneous structure that can serve as
a benchmark for comparison to other networks with a different topology. We
also observe that the mode value of $t_{c}/L_{0}$ is affected by both the
dimension and the boundary condition: (i) the higher dimension generally
yields larger $t_{c}$; (ii) periodic boundary condition yield larger $t_{c}$,
i.e., more robust networks.

In the case of deterministic the pseudo-Darwinian strategy, the only step that
might allow for variability of $t_{c}$ is the choice of the source and drain
nodes. Table 1 shows that this choice has almost no effect onto the time of
collapse. For example, for the lattice-based network with $D=2$, $N_{0}=36$
and open boundary condition, there are only two values of $t_{c}/L_{0}$:
$0.400$ (obtained for 4 source-drain pairs) and $0.417$ (obtained for the
remaining 626 source-drain pairs, among $N_{0}(N_{0}-1)/2=630$ possible
pairs). As in addition these two values are very close, we conclude that the
time of collapse does not depend on the choice of the source and the drain,
nor on their distance. This is in sharp contrast to the case of scale-free
networks. In turn, $t_{c}$ depends on the dimension, the network size, and the
type of boundary conditions.

$D$ | $N_{0}$ | $N_{0}(N_{0}-1)/2$ | Type of condition | $t_{c}/L_{0}$ | frequency
---|---|---|---|---|---
2 | 36 | 630 | open | 0.400 | 4
0.417 | 626
periodic | 0.500 | 5
0.514 | 625
3 | 125 | 7750 | open | 0.583 | 57
0.587 | 7693
periodic | 0.667 | 317
0.669 | 7433
4 | 81 | 3240 | open | 0.625 | 8
0.630 | 3232
periodic | 0.750 | 21
0.753 | 3219
Table 1:  Effect of dimension and periodic-vs-open boundary conditions of
lattice-based networks on $t_{c}/L_{0}$ when using the pseudo-Darwinian
strategy. There are two values for each dimension and type of boundary
condition, depending on the location of the source and drain nodes. The
frequency of the corresponding $t_{c}/L_{0}$ is also given.

##  4 Discussion

In this paper, we studied two evolution strategies that alter the network
iteratively [30]. The pseudo-Darwinian strategy, which is deterministic and
controlled by fluxes, results in targeted, transport-based evolution; in
particular, it can represent the process of transport network optimization, in
which least used elements are progressively removed. In turn, the random
strategy is a stochastic procedure that acts independently of the fluxes and
results in random, topologically-based evolution; it can model spontaneous
failures and progressive degradation due to, e.g., aging of the network
elements. However, the evolution is driven by two transport-based mechanisms
that are independent of the chosen strategy. First, the evolution is stopped
(at the time of collapse $t_{c}$) when transport is no longer possible in the
whole network, either because the source or the drain was removed, or because
a portion of the network became disconnected (isolated). Second, when a link
is removed from a node with degree $k=2$, the node becomes a “dead-end”
($k=1$) and no longer contributes to the transport in the rest of the network;
it is then also removed. These two mechanisms imply that, independently of the
chosen strategy, the outcomes remain transport-based.

In both strategies, we observed that $t_{c}$ is higher when the distance
$\Delta$ is small, such as the network is more resilient to transport-based
and topological-based evolutions when the source and the drain are close to
each other. This is valid only for scale-free networks, as $\Delta$ has little
effect in lattice-based networks (Fig. 5). In scale-free networks, this
topological effect was further demonstrated when adding a direct link between
the source and the drain (Fig. 3), i.e., by creating one shortest path of
length zero (1 link). Such an operation is equivalent to shunts in electronics
where small devices are used for creating alternatives paths for electric
currents [48]. In biological mass-transfer networks, such as lung airways and
blood vessels, these alternative direct paths arise naturally [49, 50] or can
be added deliberately to compensate insufficient flux due to large resistance
in the system [51]. In our simulations, this shunt greatly changed the
distribution of $t_{c}$ for the random strategy (Fig. 3 (a) and (b)). On the
opposite, this artificial modification had little to no effect when using the
pseudo-Darwinian strategy (Fig. 3 (c)). This difference is interesting because
a small distance $\Delta$ tends to produce a larger $t_{c}$ for both
strategies (Fig. 2), but the posterior topological modification (which results
in $\Delta=0$) is only beneficial when using the random strategy (Fig. 3). It
suggests that $\Delta$ is an indicator of robustness rather than the cause
when it comes to transport-based collapses. Thus, the increased robustness not
only depends on one-link connection between the source and drain nodes, but
rather originates from the construction itself, implying a peculiar
organization of links with small $\Delta$. Another interesting result of this
artificial modification is that the collapse of transport is similar in scale-
free and lattice-based networks (Fig. 3 and 5).

A similar observation can be made about the degree $k_{S}$ of the source node:
while $k_{S}$ has an effect on $t_{c}$ when using the random strategy (Fig. 4
(c)-(e)), it plays very little (or no) role when using the pseudo-Darwinian
strategy (Fig. 4 (b)). This further highlights the fact that the two
strategies differ in their behavior. As such, the degree of the source (or of
the drain) cannot serve as a common indicator of robustness for both
strategies. On the contrary, the distance $\Delta$ is more appropriate.

Several former studies showed that network integrity depends on a particular
topology when subject to targeted or random attacks [18, 52]. In particular,
Holme et al. showed that Erdős-Rényi random networks are the most robust while
scale-free networks are the most vulnerable to attacks on links or nodes [18].
In the present work, we compared the time of collapse of scale-free and
lattice-based networks. In lattice-based networks, $t_{c}$ is related to the
type of boundary conditions and the dimensionality $D$, with periodic boundary
conditions and higher values of $D$ providing higher $t_{c}$ (Fig. 5). The
topology of lattice-based networks is similar to the one of hypercubic graphs
$Q_{n}$, but with an increased number of nodes per edge. We stress that
$Q_{n}$ are commonly used and appreciated in data sciences for both their
versatile topology and efficiency in distributing numerical data between nodes
in interconnection networks [53, 54, 55]. They are efficient structures for
transport, which are also resilient to attacks [56, 55]. This is in line with
our results, which suggest that lattice-based networks of higher dimensions
can lead to efficient transport and possibly higher resistance to topological
attacks (Fig. 5). This may also apply to scale-free networks, as suggested by
Wu et al., who studied the correlation between dimension and robustness of
scale-free networks [57]. However, Wu et al. did not directly investigate link
percolation in an evolutionary framework but rather relied on typical
robustness metrics such as network efficiency and average edge betweenness,
which can be incomplete in regards to our methodological framework. Yet, it
remains to be seen if the dimension and fractal dimension can correlate with
the time of collapse $t_{c}$. This problem will be investigated in a
subsequent work.

Multiple former studies also demonstrated the usefulness of centrality
measures for assessing node importance in terms of topology only [58, 59, 60].
However, these studies were focused on the progressive removal of links or
nodes under various strategies but without taking into account transport,
which is critically relevant for various physical, natural and artificial
systems. In particular, these studied did not take into account the two
transport-based mechanisms discussed above. We demonstrate that introducing a
single link between the source and the drain can increase the robustness of
the network (Fig. 3). This artificial modification results in an increase of
the (node-) betweenness centrality (BC) of both the source and drain nodes.
The BC is a practical computational metric for measuring network robustness
subject to attacks [61]. This metric essentially indicates the number of
shortest paths going through a node. The BC also explains why dimensionality
and periodic conditions are important for robustness in lattice-based networks
as the BC depends on both. However, in our setup, it is difficult to provide a
straight-forward interpretation of what BC really is. From a topological point
of view, we study the evolution of a single network that remains to be a
connected undirected graph at each time step. As such, one can typically
consider the shortest paths that go through the source and drain nodes and
simply ignore the transport information (flow). From the transport point of
view, however, the network self-organizes and becomes a directed graph, with a
flow originating from the source and ending at the drain [7]. One can then
take into account this flow and use it as the direction for the links, and
accordingly compute the BC in this directed graph. However, this would result
in the source and drain nodes having their BC values equal to 0, as the
current originates from the source and ends up to the drain, resulting in
these two nodes having no paths going through. These are distinct “end-nodes”
of major importance in terms of the transport that cannot be ignored. Thus,
typical metrics such as the BC or closeness centrality should be further
updated with the transport information in order to better measure node
importance in such a setup. For instance, one can potentially exploit new
metrics such as the current flow betweenness centrality [62, 63, 64], which is
based on random walks and employs the established connections between electric
current flows and random walks [65].

In summary, this work contributes to the understanding of transport in scale-
free or lattice networks, and more generally, to dynamical real-world systems
that can experience the progressive removal of links. This includes both
natural and artificial networks, or networked systems: species evolution [66,
19, 20], biological systems [67], such as the protein-interaction network [68,
69], metabolic network [70], and cellular network [71], economic systems [72],
the financial sector [21, 73], social networks [22], such as the author-
collaboration network in social systems [74, 71], communication systems such
as the Internet [75, 71, 67], World Wide Web [76, 71, 67], power-grid and
industrial networks [71, 67], and transportation networks [77, 78].
Dorogovtsev et al. and Albert et al. review numerous other additional examples
of empirical scale-free networks in [67] and [71]. Despite the physics-
inspired character of the considered transport model, our work revealed
several features that may find applications in real-world networks. First, the
source-drain distance $\Delta$ is a simple yet useful indicator for network
robustness when environmental changes randomly alter the links. Second, the
inclusion of one additional link can further improve robustness, thus delaying
the collapse. This work was focused on the collapse of transport, which is
understood in terms of fluxes from the source to the drain. This a simple
setup which focuses exclusively on a single pair of the source and drain
nodes. We also included the condition (iii) which stops the simulations when
the main network is divided into two or multiple subgraphs (see Methods
section 2.2). One source and drain and this breaking condition are reasonable
for some applications and not relevant for others. For instance, in the
transportation field, there can be multiple origins (sources) and destinations
(drains) in one network. When an origin gets disconnected from the main
network, transport remains possible, thanks to other origins. In a future
work, we plan to extend this study and investigate the time of collapse in
more general settings by removing condition (iii) and including multiple
sources and drains [79, 80].

## Conflict of interest declaration

We declare we have no competing interests.

## Funding

The author(s) received no financial support for the research, authorship,
and/or publication of this article.

## Acknowledgments

This article is dedicated to the work and commitment of Bernard Sapoval
(1937–2020). D.S.G. acknowledges the Alexander von Humboldt Foundation for
support within a Bessel Prize award.

## References

  * [1] Serov A, Salafia C, Filoche M, Grebenkov D.  Analytical theory of oxygen transport in the human placenta.  Journal of theoretical biology. 2015;368:133-44.  Available from: https://doi.org/10.1016/j.jtbi.2014.12.016.
  * [2] Grebenkov DS, Filoche M, Sapoval B, Felici M.  Diffusion-reaction in branched structures: theory and application to the lung acinus.  Physical review letters. 2005;94(5):050602.  Available from: https://doi.org/10.1103/PhysRevLett.94.050602.
  * [3] Newman ME, Girvan M.  Finding and evaluating community structure in networks.  Physical review E. 2004;69(2):026113.  Available from: https://doi.org/10.1103/PhysRevE.69.026113.
  * [4] Lambiotte R, Sinatra R, Delvenne JC, Evans TS, Barahona M, Latora V.  Flow graphs: Interweaving dynamics and structure.  Physical Review E. 2011;84(1):017102.  Available from: https://doi.org/10.1103/PhysRevE.84.017102.
  * [5] Barabási AL, Albert R.  Emergence of scaling in random networks.  science. 1999;286(5439):509-12.  Available from: https://doi.org/10.1126/science.286.5439.509.
  * [6] Wu Z, López E, Buldyrev SV, Braunstein LA, Havlin S, Stanley HE.  Current flow in random resistor networks: The role of percolation in weak and strong disorder.  Physical Review E. 2005;71(4):045101.  Available from: https://doi.org/10.1103/PhysRevE.71.045101.
  * [7] Kang MY, Berthelot G, Tupikina L, Nicolaides C, Colonna JF, Sapoval B, et al.  Morphological organization of point-to-point transport in complex networks.  Scientific reports. 2019;9(1):8322.  Available from: https://doi.org/10.1038/s41598-019-44701-6.
  * [8] López E, Buldyrev SV, Havlin S, Stanley HE.  Anomalous transport in scale-free networks.  Physical review letters. 2005;94(24):248701.  Available from: https://doi.org/10.1103/PhysRevLett.94.248701.
  * [9] Kovács IA, Luck K, Spirohn K, Wang Y, Pollis C, Schlabach S, et al.  Network-based prediction of protein interactions.  Nature communications. 2019;10(1):1-8.  Available from: https://doi.org/10.1038/s41467-019-09177-y.
  * [10] Mauroy B, Filoche M, Weibel E, Sapoval B.  An optimal bronchial tree may be dangerous.  Nature. 2004;427(6975):633-6.  Available from: https://doi.org/10.1038/nature02287.
  * [11] Connor-Streich G, Henshaw AJ, Brasington J, Bertoldi W, Harvey GL.  Let’s get connected: A new graph theory-based approach and toolbox for understanding braided river morphodynamics.  Wiley Interdisciplinary Reviews: Water. 2018;5(5):e1296.  Available from: https://doi.org/10.1002/wat2.1296.
  * [12] Rinaldo A, Rigon R, Banavar JR, Maritan A, Rodriguez-Iturbe I.  Evolution and selection of river networks: Statics, dynamics, and complexity.  Proceedings of the National Academy of Sciences. 2014;111(7):2417-24.  Available from: https://doi.org/10.1073/pnas.1322700111.
  * [13] Shao S, Huang X, Stanley HE, Havlin S.  Percolation of localized attack on complex networks.  New Journal of Physics. 2015;17(2):023049.  Available from: https://doi.org/10.1088/1367-2630/17/2/023049.
  * [14] Mattsson LG, Jenelius E.  Vulnerability and resilience of transport systems–A discussion of recent research.  Transportation Research Part A: Policy and Practice. 2015;81:16-34.  Available from: https://doi.org/10.1016/j.tra.2015.06.002.
  * [15] Pan S, Yan H, He J, He Z.  Vulnerability and resilience of transportation systems: A recent literature review.  Physica A: Statistical Mechanics and its Applications. 2021;581:126235.  Available from: https://doi.org/10.1016/j.physa.2021.126235.
  * [16] von Ferber C, Berche B, Holovatch T, Holovatch Y.  A tale of two cities.  Journal of Transportation Security. 2012;5(3):199-216.  Available from: https://doi.org/10.1007/s12198-012-0092-9.
  * [17] Zhang L, Lu J, Fu Bb, Li Sb.  A review and prospect for the complexity and resilience of urban public transit network based on complex network theory.  Complexity. 2018;2018.  Available from: https://doi.org/10.1155/2018/2156309.
  * [18] Holme P, Kim BJ, Yoon CN, Han SK.  Attack vulnerability of complex networks.  Physical review E. 2002;65(5):056109.  Available from: https://doi.org/10.1103/PhysRevE.65.056109.
  * [19] Bellwood DR, Hughes TP, Folke C, Nyström M.  Confronting the coral reef crisis.  Nature. 2004;429(6994):827-33.  Available from: https://doi.org/10.1038/nature02691.
  * [20] Hanel R, Thurner S.  Solution of the unanimity rule on exponential, uniform and scalefree networks: A simple model for biodiversity collapse in foodwebs.  The European Physical Journal B. 2008;62(3):327-30.  Available from: https://doi.org/10.1140/epjb/e2008-00160-7.
  * [21] Haldane AG, May RM.  Systemic risk in banking ecosystems.  Nature. 2011;469(7330):351-5.  Available from: https://doi.org/10.1038/nature09659.
  * [22] Murase Y, Jo HH, Török J, Kertész J, Kaski K.  Modeling the role of relationship fading and breakup in social network formation.  PloS one. 2015;10(7):e0133005.  Available from: https://doi.org/10.1371/journal.pone.0133005.
  * [23] Rizzo DM, Garbelotto M.  Sudden oak death: endangering California and Oregon forest ecosystems.  Frontiers in Ecology and the Environment. 2003;1(4):197-204.  Available from: https://doi.org/10.1890/1540-9295(2003)001[0197:SODECA]2.0.CO;2.
  * [24] Şekercioğlu ÇH, Daily GC, Ehrlich PR.  Ecosystem consequences of bird declines.  Proceedings of the National Academy of Sciences. 2004;101(52):18042-7.  Available from: https://doi.org/10.1073/pnas.0408049101.
  * [25] Elliott M, Golub B, Jackson MO.  Financial networks and contagion.  American Economic Review. 2014;104(10):3115-53.  Available from: https://doi.org/10.1257/aer.104.10.3115.
  * [26] Crucitti P, Latora V, Marchiori M.  Model for cascading failures in complex networks.  Physical Review E. 2004;69(4):045104.  Available from: https://doi.org/10.1103/PhysRevE.69.045104.
  * [27] Gao J, Buldyrev SV, Stanley HE, Xu X, Havlin S.  Percolation of a general network of networks.  Physical Review E. 2013;88(6):062816.  Available from: https://doi.org/10.1103/PhysRevE.88.062816.
  * [28] Ma W, Trusina A, El-Samad H, Lim WA, Tang C.  Defining network topologies that can achieve biochemical adaptation.  Cell. 2009;138(4):760-73.  Available from: https://doi.org/10.1016/j.cell.2009.06.013.
  * [29] Reznik E, Segre D.  On the stability of metabolic cycles.  Journal of theoretical biology. 2010;266(4):536-49.  Available from: https://doi.org/10.1016/j.jtbi.2010.07.023.
  * [30] Berthelot G, Tupikina L, Kang MY, Sapoval B, Grebenkov DS.  Pseudo-Darwinian evolution of physical flows in complex networks.  Scientific reports. 2020;10(1):1-6.  Available from: https://doi.org/10.1038/s41598-020-72379-8.
  * [31] O’Kelly ME.  Network hub structure and resilience.  Networks and Spatial Economics. 2015;15(2):235-51.  Available from: https://doi.org/10.1007/s11067-014-9267-1.
  * [32] Kirkpatrick S.  Percolation and conduction.  Reviews of modern physics. 1973;45(4):574.  Available from: https://doi.org/10.1103/RevModPhys.45.574.
  * [33] Klein DJ, Randić M.  Resistance distance.  Journal of mathematical chemistry. 1993;12(1):81-95.  Available from: https://doi.org/10.1007/BF01164627.
  * [34] Moody J, Aravind P.  Resistor networks based on symmetrical polytopes.  Electronic Journal of Graph Theory and Applications (EJGTA). 2015;3(1):56-69.  Available from: http://dx.doi.org/10.5614/ejgta.2015.3.1.7.
  * [35] Sudhendra C, Mahule V, Pillai A, Mohanty A.  A novel space cloth using resistor grid network for radar absorbers in stealth applications.  In: 2011 International Conference on Communications and Signal Processing. IEEE; 2011. p. 83-6.  Available from: https://doi.org/10.1109/ICCSP.2011.5739405.
  * [36] Medina O, Shapiro A, Shvalb N.  Resistor-based shape sensor for a spatial flexible manifold.  IEEE Sensors Journal. 2016;17(1):46-50.  Available from: https://doi.org/10.1109/JSEN.2016.2619760.
  * [37] Mirzaei S, Fernandez A.  Retard system solution on electric mining trucks.  In: 3rd IEEE International Symposium on Sensorless Control for Electrical Drives (SLED 2012). IEEE; 2012. p. 1-5.  Available from: https://doi.org/10.1109/SLED.2012.6422816.
  * [38] Tabarra M, Guan D.  Measurement of train brake heat in underground systems.  In: Independent Technical Conference, Tunnel Design & Systems Engineering; 2005. p. 93-102.  Available from: https://doi.org/10.13140/RG.2.1.3747.5281.
  * [39] Iñiguez G, Battiston F, Karsai M.  Bridging the gap between graphs and networks.  Communications Physics. 2020;3(1):1-5.  Available from: https://doi.org/10.1038/s42005-020-0359-6.
  * [40] Pastor-Satorras R, Vespignani A.  Evolution and structure of the Internet: A statistical physics approach.  Cambridge University Press; 2004.  Available from: https://doi.org/10.1017/CBO9780511610905.
  * [41] Nicolaides C, Cueto-Felgueroso L, Juanes R.  Anomalous physical transport in complex networks.  Physical Review E. 2010;82(5):055101.  Available from: https://doi.org/10.1103/PhysRevE.82.055101.
  * [42] Redner S.  A guide to first-passage processes.  Cambridge University Press; 2001.  Available from: https://doi.org/10.1017/CBO9780511606014.
  * [43] Zhao L, Cupertino TH, Park K, Lai YC, Jin X.  Optimal structure of complex networks for minimizing traffic congestion.  Chaos: An Interdisciplinary Journal of Nonlinear Science. 2007;17(4):043103.  Available from: https://doi.org/10.1063/1.2790367.
  * [44] Allesina S, Azzi A, Battini D, Regattieri A.  Performance measurement in supply chains: new network analysis and entropic indexes.  International Journal of Production Research. 2010;48(8):2297-321.  Available from: https://doi.org/10.1080/00207540802647327.
  * [45] Yazdani A, Otoo RA, Jeffrey P.  Resilience enhancing expansion strategies for water distribution systems: A network theory approach.  Environmental Modelling & Software. 2011;26(12):1574-82.  Available from: https://doi.org/10.1016/j.envsoft.2011.07.016.
  * [46] Rosas-Casals M, Valverde S, Solé RV.  Topological vulnerability of the European power grid under errors and attacks.  International journal of bifurcation and chaos. 2007;17(07):2465-75.  Available from: https://doi.org/10.1142/S0218127407018531.
  * [47] Nardelli PH, Rubido N, Wang C, Baptista MS, Pomalaza-Raez C, Cardieri P, et al.  Models for the modern power grid.  The European Physical Journal Special Topics. 2014;223(12):2423-37.  Available from: https://doi.org/10.1140/epjst/e2014-02219-6.
  * [48] Graf RF.  Modern dictionary of electronics.  Newnes; 1999.  Available from: https://doi.org/10.1016/C2009-0-26363-X.
  * [49] Gompelmann D, Eberhardt R, Herth F.  Collateral ventilation.  Respiration. 2013;85(6):515-20.  Available from: https://doi.org/10.1159/000348269.
  * [50] Santulli G.  Angiogenesis: insights from a systematic overview.  Nova Science Publishers, Inc.; 2013.
  * [51] Alexander JH, Smith PK.  Coronary-artery bypass grafting.  New England Journal of Medicine. 2016;374(20):1954-64.  Available from: https://doi.org/10.1056/nejmra1406944.
  * [52] Albert R, Jeong H, Barabási AL.  Error and attack tolerance of complex networks.  nature. 2000;406(6794):378-82.  Available from: https://doi.org/10.1038/35019019.
  * [53] Ostrouchov G.  Parallel computing on a hypercube: an overview of the architecture and some applications.  In: Computer Science and Statistics, Proceedings of the 19th Symposium on the Interface; 1987. p. 27-32.
  * [54] Sardar MS, Liu JB, Siddique I, Jaradat MM.  A Novel and Efficient Method for Computing the Resistance Distance.  IEEE Access. 2021;9:107104-10.  Available from: https://doi.org/10.1109/ACCESS.2021.3099570.
  * [55] di Bernardo M, Maini E, Manzalini A, Mazzocca N.  Traffic dynamics and vulnerability in hypercube communication networks.  In: 2014 IEEE International Symposium on Circuits and Systems (ISCAS). IEEE; 2014. p. 2221-4.  Available from: https://doi.org/10.1109/ISCAS.2014.6865611.
  * [56] Toshniwal B, Kataoka K.  Comparative Performance Analysis of Underlying Network Topologies for Blockchain.  In: 2021 International Conference on Information Networking (ICOIN); 2021\. p. 367-72.  Available from: https://doi.org/10.1109/ICOIN50884.2021.9333978.
  * [57] Wu Y, Chen Z, Yao K, Zhao X, Chen Y.  On the correlation between fractal dimension and robustness of complex networks.  Fractals. 2019;27(04):1950067.  Available from: https://doi.org/10.1142/S0218348X19500671.
  * [58] Iyer S, Killingback T, Sundaram B, Wang Z.  Attack robustness and centrality of complex networks.  PloS one. 2013;8(4):e59613.  Available from: https://doi.org/10.1371/journal.pone.0059613.
  * [59] Lü L, Chen D, Ren XL, Zhang QM, Zhang YC, Zhou T.  Vital nodes identification in complex networks.  Physics Reports. 2016;650:1-63.  Available from: https://doi.org/10.1016/j.physrep.2016.06.007.
  * [60] Oldham S, Fulcher B, Parkes L, Arnatkevičiūtė A, Suo C, Fornito A.  Consistency and differences between centrality measures across distinct classes of networks.  PloS one. 2019;14(7):e0220061.  Available from: https://doi.org/10.1371/journal.pone.0220061.
  * [61] Freeman LC.  Centrality in social networks conceptual clarification.  Social Networks. 1978;1(3):215-39.  Available from: https://doi.org/10.1016/0378-8733(78)90021-7.
  * [62] Brandes U, Fleischer D.  Centrality measures based on current flow.  In: Annual symposium on theoretical aspects of computer science. Springer; 2005. p. 533-44.  Available from: https://doi.org/10.1007/978-3-540-31856-9_44.
  * [63] Newman ME.  A measure of betweenness centrality based on random walks.  Social networks. 2005;27(1):39-54.  Available from: https://doi.org/10.1016/j.socnet.2004.11.009.
  * [64] Agryzkov T, Tortosa L, Vicent JF.  A variant of the current flow betweenness centrality and its application in urban networks.  Applied Mathematics and Computation. 2019;347:600-15.  Available from: https://doi.org/10.1016/j.amc.2018.11.032.
  * [65] Doyle PG, Snell JL.  Random walks and electric networks. vol. 22.  American Mathematical Soc.; 1984.  Available from: https://doi.org/10.5948/UPO9781614440222.
  * [66] Jackson JB, Kirby MX, Berger WH, Bjorndal KA, Botsford LW, Bourque BJ, et al.  Historical overfishing and the recent collapse of coastal ecosystems.  science. 2001;293(5530):629-37.  Available from: https://doi.org/10.1126/science.1059199.
  * [67] Dorogovtsev SN, Mendes JF.  Evolution of networks: From biological nets to the Internet and WWW.  Oxford university press; 2003.
  * [68] Jeong H, Mason SP, Barabási AL, Oltvai ZN.  Lethality and centrality in protein networks.  Nature. 2001;411(6833):41-2.  Available from: https://doi.org/10.1038/35075138.
  * [69] Barabasi AL, Oltvai ZN.  Network biology: understanding the cell’s functional organization.  Nature reviews genetics. 2004;5(2):101-13.  Available from: https://doi.org/10.1038/nrg1272.
  * [70] Jeong H, Tombor B, Albert R, Oltvai ZN, Barabási AL.  The large-scale organization of metabolic networks.  Nature. 2000;407(6804):651-4.  Available from: https://doi.org/10.1038/35036627.
  * [71] Albert R, Barabási AL.  Statistical mechanics of complex networks.  Rev Mod Phys. 2002 Jan;74:47-97.  Available from: https://link.aps.org/doi/10.1103/RevModPhys.74.47.
  * [72] Klimek P, Hausmann R, Thurner S.  Empirical Confirmation of Creative Destruction from World Trade Data.  PLOS ONE. 2012 06;7(6):1-9.  Available from: https://doi.org/10.1371/journal.pone.0038924.
  * [73] Boss M, Elsinger H, Summer M, Thurner 4 S.  Network topology of the interbank market.  Quantitative Finance. 2004;4(6):677-84.  Available from: https://www.tandfonline.com/doi/abs/10.1080/14697680400020325.
  * [74] Newman MEJ.  The structure of scientific collaboration networks.  Proceedings of the National Academy of Sciences. 2001;98(2):404-9.  Available from: https://www.pnas.org/doi/abs/10.1073/pnas.98.2.404.
  * [75] Faloutsos M, Faloutsos P, Faloutsos C.  On Power-Law Relationships of the Internet Topology.  SIGCOMM Comput Commun Rev. 1999 aug;29(4):251–262.  Available from: https://doi.org/10.1145/316194.316229.
  * [76] Albert R, Jeong H, Barabási AL.  Diameter of the world-wide web.  nature. 1999;401(6749):130-1.  Available from: https://doi.org/10.1038/43601.
  * [77] Guimerà R, Mossa S, Turtschi A, Amaral LAN.  The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles.  Proceedings of the National Academy of Sciences. 2005;102(22):7794-9.  Available from: https://www.pnas.org/doi/abs/10.1073/pnas.0407994102.
  * [78] Li W, Cai X.  Empirical analysis of a scale-free railway network in China.  Physica A: Statistical Mechanics and its Applications. 2007;382(2):693-703.  Available from: https://www.sciencedirect.com/science/article/pii/S0378437107003949.
  * [79] Carmi S, Wu Z, López E, Havlin S, Eugene Stanley H.  Transport between multiple users in complex networks.  The European Physical Journal B. 2007;57(2):165-74.  Available from: https://doi.org/10.1140/epjb/e2007-00129-0.
  * [80] Carmi S, Wu Z, Havlin S, Stanley HE.  Transport in networks with multiple sources and sinks.  EPL (Europhysics Letters). 2008;84(2):28005.  Available from: https://doi.org/10.1209/0295-5075/84/28005.