For Theorem 1.2, we are done by our choice of $\epsilon$.

For Theorem 1.4, we note that by Cauchy-Schwarz (as in Proposition 5.2),
$\mathbb{P}[\mathcal{E}_{e_{1}+e_{2}}]\leq\mathbb{P}[\mathcal{E}_{e_{1}-e_{2}}]$
and recall from above that $\exp(-H(\vec{p}))\leq\lVert\vec{p}\rVert_{2}^{2}$.
Using this, we can bound the right hand side of the above computation by

$2Ct+2n\mathbb{P}[\mathcal{E}_{e_{1}}]+2n^{2}\exp(\epsilon
n/2)\mathbb{P}[\mathcal{E}_{e_{1}-e_{2}}].$

The desired conclusion follows since $2n^{2}\exp(\epsilon
n/2)\leq(1+\epsilon)^{n}$ for all $\epsilon<1$ and $n$ sufficiently large.

## References

  * [1] Anirban Basak and Mark Rudelson, _Sharp transition of the invertibility of the adjacency matrices of sparse random graphs_ , arXiv:1809.08454.
  * [2] Jean Bourgain, Van H. Vu, and Philip Matchett Wood, _On the singularity probability of discrete random matrices_ , J. Funct. Anal. 258 (2010), 559–603.
  * [3] Asaf Ferber, Vishesh Jain, Kyle Luh, and Wojciech Samotij, _On the counting problem in inverse Littlewood–Offord theory_ , arXiv:1904.10425.
  * [4] Han Huang, _Singularity of Bernoulli matrices in the sparse regime $pn={O}(\log n)$_, arXiv:2009.13726.
  * [5] A. Irmatov, _Asymptotics of the number of threshold functions and the singularity probability of random $\\{\pm 1\\}$-matrices_, Doklady Mathematics 101 (2020), 247–249.
  * [6] Vishesh Jain, _Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices_ , arXiv:1904.10592.
  * [7] Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney, _Sharp invertibility of random Bernoulli matrices_ , in preparation.
  * [8] Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney, _The smallest singular value of dense random regular digraphs_ , arXiv:2008.04755.
  * [9] Jeff Kahn, János Komlós, and Endre Szemerédi, _On the probability that a random $\pm 1$-matrix is singular_, J. Amer. Math. Soc. 8 (1995), 223–240.
  * [10] Boris Sergeevich Kašin, _Diameters of some finite-dimensional sets and classes of smooth functions_ , Izvestiya: Mathematics 11 (1977), 317–333.
  * [11] J. Komlós, _On the determinant of $(0,\,1)$ matrices_, Studia Sci. Math. Hungar. 2 (1967), 7–21.
  * [12] A. E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann, _Smallest singular value of random matrices and geometry of random polytopes_ , Adv. Math. 195 (2005), 491–523.
  * [13] Alexander E Litvak and Konstantin E Tikhomirov, _Singularity of sparse Bernoulli matrices_ , arXiv:2004.03131.
  * [14] Galyna V Livshyts, _The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding_ , arXiv:1811.07038.
  * [15] Galyna V Livshyts, Konstantin Tikhomirov, and Roman Vershynin, _The smallest singular value of inhomogeneous square random matrices_ , arXiv:1909.04219.
  * [16] Hoi H. Nguyen, _On the singularity of random combinatorial matrices_ , SIAM J. Discrete Math. 27 (2013), 447–458.
  * [17] B. A. Rogozin, _On the increase of dispersion of sums of independent random variables_ , Teor. Verojatnost. i Primenen 6 (1961), 106–108.
  * [18] Mark Rudelson, _Invertibility of random matrices: norm of the inverse_ , Annals of Mathematics (2008), 575–600.
  * [19] Mark Rudelson and Roman Vershynin, _The Littlewood-Offord problem and invertibility of random matrices_ , Adv. Math. 218 (2008), 600–633.
  * [20] Gideon Schechtman, _Special orthogonal splittings of $L^{2k}_{1}$_, Israel J. Math. 139 (2004), 337–347.
  * [21] Terence Tao and Van Vu, _On random $\pm 1$ matrices: singularity and determinant_, Random Structures Algorithms 28 (2006), 1–23.
  * [22] Terence Tao and Van Vu, _On the singularity probability of random Bernoulli matrices_ , J. Amer. Math. Soc. 20 (2007), 603–628.
  * [23] Konstantin Tikhomirov, _Singularity of random Bernoulli matrices_ , Ann. of Math. (2) 191 (2020), 593–634.
  * [24] Tuan Tran, _The smallest singular value of random combinatorial matrices_ , arXiv:2007.06318.
  * [25] Roman Vershynin, _High-dimensional probability_ , Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47, Cambridge University Press, Cambridge, 2018, An introduction with applications in data science, With a foreword by Sara van de Geer.


11institutetext: KU Leuven, Belgium,
11email<EMAIL_ADDRESS>
22institutetext: University of Technology Kaiserslautern, Germany

# Adaptive rewiring evolves brain-like structure in directed networks

Ilias Rentzeperis 11 Steeve Laquitaine 11 Cees van Leeuwen 11 2 2

###### Abstract

Brain networks are adaptively rewired continually, adjusting their topology to
bring about functionality and efficiency in sensory, motor and cognitive
tasks. In model neural network architectures, adaptive rewiring generates
complex, brain-like topologies. Present models, however, cannot account for
the emergence of complex directed connectivity structures. We tested a
biologically plausible model of adaptive rewiring in directed networks, based
on two algorithms widely used in distributed computing: advection and
consensus. When both are used in combination as rewiring criteria, adaptive
rewiring shortens path length and enhances connectivity. When keeping a
balance between advection and consensus, adaptive rewiring produces
convergent-divergent units consisting of convergent hub nodes, which collect
inputs from pools of sparsely connected, or local, nodes and project them via
densely interconnected processing nodes onto divergent hubs that broadcast
output back to the local pools. Convergent-divergent units operate within and
between sensory, motor, and cognitive brain regions as their connective core,
mediating context-sensitivity to local network units. By showing how these
structures emerge spontaneously in directed networks models, adaptive rewiring
offers self-organization as a principle for efficient information propagation
and integration in the brain.

##  1 Introduction

Neuronal selectivity not only depends on local receptive fields, but also on
global contextual features [1]. Prominent examples are surround suppression
[2][3], sensorimotor prediction coding [4], orientation biases [5], and
normalization [6]. These and other contextualized effects are mediated by
short- and long-range connections within areas [7][8], and top-down feedback
[9]. A common mechanism accommodating contextual effects is pooling, i.e.
units collect inputs from many neurons which and then redistribute the
information back to the neurons [10]. This process can be accomplished via
convergent-divergent units [11]. Convergent-divergent units receive input from
many neurons (via convergent connections), process it, and subsequently
project the output to many neurons (via divergent connections).

We investigated how a network connectivity structure encompassing convergent-
divergent units could emerge spontaneously from adaptive plasticity in
artificial neural networks. It is well known that the brain’s connectivity
structure continually evolves during development [12], learning [13] and
recovery following injury [14][15]. Whereas most studies of adaptive
plasticity have been focused on activity evoked by external (i.e. sensory)
input [16][17], a major part of brain activity is ongoing and spontaneous
[18]. To investigate whether convergent-divergent units can emerge from
spontaneous activity, we used a simple, generic structural plasticity [19]
mechanism characterized as adaptive rewiring: strong activity between neural
components leads to the addition of network connections, while weak activity
leads to their pruning.

Previous studies on adaptive rewiring have shown that spontaneous activity can
lead to complex network structures, akin to the anatomy of the brain: modular
or centralized networks with rich club effect [20]-[24]. However, these
studies typically used undirected networks. Undirected networks propagate
activity indiscriminately in both directions of an edge connecting two nodes.
While this property is mathematically convenient and can capture some of the
aggregate effects of adaptive rewiring, it is physiologically implausible at
the neuronal level, in particular because of the asymmetry in signal transfer
through chemical synapses [25]-[27]. Moreover, undirected networks cannot
represent brain features that show directionality, such as convergent-
divergent units. Directed networks, therefore, offer a more plausible
framework for adaptive rewiring. In addition, such a framework is more general
than undirected networks, as the latter are included as a special case.

A recent study proposed to represent neuronal signal propagation as random
walks on an anatomical network, and characterize the propagation
stochastically in terms of heat diffusion [28]. We previously adopted a
similar principle in an adaptive rewiring model with undirected connections,
where activity propagation between nodes was represented by a heat kernel
[20][22]. In such models, adaptive rewiring amounts to adding shortcuts to
regions with intense diffusion, while pruning where diffusion is low, thereby
relating the connectivity structure of the network to neuronal traffic.

To model adaptive rewiring in directed networks, we use two algorithms closely
related to heat diffusion that can account for directionality of the
connections: advection and consensus [29]. Advection and consensus algorithms
have been used extensively in sparsely connected neural networks. In the
context of neuronal dynamics, both advection and consensus (and diffusion in
the undirected case) act as homeostatic factors that aim to reduce the
differences between neurons’ activities. Neuronal activity values are
interpreted as concentrations, and traffic between them is proportional to
their concentration differences. The goal of advection and consensus
algorithms is to approach a common concentration value for all the nodes
[29]-[31].

For both advection and consensus, we applied the same rewiring principle:
during each rewiring iteration, a connection with low traffic is cut and used
for an unconnected pair of nodes with high activity. We found that when a
random network rewires based on advection, the emerging network contains
converging hub nodes, which receive pooled inputs from many local (sparsely
connected) nodes. When rewiring is based on consensus, the network develops
diverging hub nodes, which broadcast outputs back to the local nodes. When
both advection and consensus are applied within the same rewiring scheme, the
network produces both diverging and converging hubs nodes. Intermediate nodes,
nodes on the path between a converging and diverging hub nodes, are densely
interconnected, multiple times more densely than the local nodes outside the
unit. In addition, a proportion of random rewiring facilitates the formation
of these structures and improves node-to-node communication.

Converging and diverging hub nodes, together with a dense network of
intermediate nodes, constitute converging-diverging units. These structures
arise in our model in a self-organized fashion, as the product of adaptive
rewiring, while the remaining network is sparse. We conclude that adaptive
rewiring offers a principle for the emergence of efficient context-sensitive
information processing in the brain.

##  2 Methods

###  2.1 Digraph preliminaries

A directed binary graph (or digraph) is defined as an ordered pair, $D=(N,E)$,
where $N$ corresponds to the set of nodes, $N=[1,…,n]$ and $E$ to ordered node
pairs denoting the directed edges (or connections), $E\subset\ N\times\ N$.
The ordered pair $(x,y)\in E$ if x and y are adjacent so that x is the tail of
the connection and y its head, also denoted as $x\ \rightarrow y$; if not,
then $\left(x,y\right)\notin E$. The cardinalities $\left|V\right|$ and
$\left|E\right|$ are the total number of nodes and edges of D respectively.
For a digraph with n vertices, the connectivity pattern is encapsulated by an
$N\times\ N$ adjacency matrix A. For binary digraphs all connections carry the
same weight, i.e. $A_{ij}=1$ indicates that $(j,i)\in E$, while $A_{ij}=0$
that $\left(j,i\right)\notin E$. We do not allow for a node to point to
itself, so A is zero along its diagonal.

The in-degree of node k is the number of connections that have node k as their
head; the tails of these connections constitute the in-degree neighborhood of
$k$, $N_{in}\left(k\right)$. The number of nonzero elements along the rows of
$A$ indicate the in-degrees of the nodes (Fig 1, row of A). The out-degree of
node $k$ is the number of connections that have node $k$ as their tail with
the corresponding heads being the out-degree neighborhood of $k$,
$N_{out}\left(k\right)$. The numbers of nonzero elements along the columns of
$A$ indicate the out-degrees of the nodes (Fig 1, column of A).

Figure 1: Schematic representation of the adjacency matrix From the rows of A,
we obtain the in-degree connectivity of the network, from the columns the out-
degree.

###  2.2 Advection and consensus dynamics

We use advection and consensus algorithms based on the heat (or diffusion)
equation. The heat equation describes how some quantity diffuses across a
medium over time. When operating on an undirected graph, the heat equation has
an explicit solution:

$\\\ \mathbf{x}\left(t\right)=\ e^{-Lt}\mathbf{x}\left(0\right)\\\ $ (1)

where $\mathbf{x}\left(0\right)$ and $\mathbf{x}\left(t\right)$ are
n-dimensional vectors containing the concentrations of the nodes of the
network, $x_{1}...x_{n}$ before and at time t after diffusion respectively.
$L$, the graph Laplacian, is defined as $L=D-A$, where $D$ is a diagonal
matrix with the degrees of the nodes in its diagonal entries and $A$ the
adjacency matrix. It is the discrete analogue of the Laplace-Beltrami operator
$(\nabla^{2}f)$ for graphs. In its discrete form, it emerges in optimization
problems such as graph partitioning [32], and dimensionality reduction [33].
In the diffusion context, the graph Laplacian is an $N\times\ N$ matrix that
quantifies the rate of change of flow across edges.

Mathematically, the difference between advection and consensus is their use of
different Laplacian matrices: the former uses the out-degrees of the nodes in
the diagonal entries of the Laplacian the latter the in-degrees. Both the
advection and consensus dynamics will produce the same values as heat
diffusion if the graph edges are stripped of their directionality.

Below, we give a brief description of the advection and consensus dynamics. A
more detailed description is given elsewhere[29]. The advection equation in a
continuous manifold is given by:

$\frac{\partial u}{\partial t}=\ -\nabla\bullet\left(\vec{y}u\right)$ (2)

where $\nabla$ is the divergence operator, and $\vec{y}$ a vector field that
affects how the concentration $u$ of a material is distributed. Advection, for
example, can describe how the concentration of oil or other pollutants changes
within a river stream.

In a digraph setting, the direction and weight of the edges define the vector
field $\vec{y}$, and the nodes’ values the concentration $u$. The rate of
change of the concentration of node i is defined as the flow into the node
minus the flow out of the node:

${\dot{x}}_{i}\left(t\right)=\sum_{{\forall\ j|j\rightarrow
i}}{w_{ij}x_{j}\left(t\right)}-\sum_{\left\\{\forall\ k\middle|\ i\rightarrow
k\right\\}}{w_{ki}x_{i}\left(t\right)}$ (3)

where at time $t$, $w_{ij}x_{j}(t)$ indicates the flow through the edge
$j\rightarrow i$. Collectively, the advection dynamics can be represented in
matrix form as:

$\dot{\mathbf{x}}\left(t\right)=\ -\mathcal{L}_{out}\mathbf{x}\left(t\right)$
(4)

where at time $t$,
$\dot{\mathbf{x}}\left(t\right)=\left[{\dot{x}}_{1}\left(t\right),\ldots,\
{\dot{x}}_{n}\left(t\right)\right]^{T}$ contains the rate of change of the
concentration of each node,
$\mathbf{x}\left(t\right)=\left[{x}_{1}\left(t\right),\ldots,\
{x}_{n}\left(t\right)\right]^{T}$ the concentration of the nodes, and
$\mathcal{L}_{out}$, the out-degree Laplacian, an $N\times\ N$ matrix with the
following entries:

$\mathcal{L}_{out}=\begin{cases}\sum_{k=1}^{n}A_{ki}&\text{if $i=j$}\\\
-A_{ij}&\text{if $i\neq j$}\end{cases}$

The out-degree strengths of the nodes are in the diagonal entries of
$\mathcal{L}_{out}$. The solution to (4) is:

$\mathbf{x}\left(t\right)=\ e^{{-L}_{out}t}\mathbf{x}\left(0\right)$ (5)

For advection, the concentrations of the nodes are sum conservative, i.e. for
any time $t$
$\sum_{i=1}^{n}{x_{i}\left(t\right)=\sum_{i=1}^{n}{x_{i}\left(0\right)\ }\ }$.
The consensus dynamics for each node is given by:

$\dot{x_{i}}\left(t\right)=\sum_{{\forall\ j|j\rightarrow
i}}{w_{ij}(x_{j}\left(t\right)-x_{i}\left(t\right))}\ \ \ \ i=1,\ldots,n$ (6)

Eq. (6) implies that there is diffusion whenever there is a difference in
concentrations between adjacent nodes.

Collectively, the consensus dynamics (6) are represented in matrix form as:

$\dot{\mathbf{x}}\left(t\right)=\ -\mathcal{L}_{in}\mathbf{x}\left(t\right)$
(7)

where $\mathcal{L}_{in}$ is the in-degree Laplacian, an $N\times\ N$ matrix
with the following entries:

$\mathcal{L}_{in}=\begin{cases}\sum_{k=1}^{n}A_{ik}&\text{if $i=j$}\\\
-A_{ij}&\text{if $i\neq j$}\end{cases}$

In the case of $\mathcal{L}_{in}$ now, its diagonal entries contain the in-
degree strengths of the nodes. The solution to (7) is:

$\mathbf{x}\left(t\right)=\ e^{{-L}_{in}t}\mathbf{x}\left(0\right)$ (8)

For balanced networks, where the sum of the weights of in-degrees are equal to
the sum of the weights of out-degrees for all nodes, the advection and
consensus dynamics are equal, i.e. Eq (5) is equal to Eq (8) and both are
equal to heat diffusion. For the purposes of our adaptive rewiring algorithm,
we use the exponential part of (5) for advection, which indicates the dynamics
when we project unit output to a node (while the rest are zero) for all the
nodes in parallel. We call this part $\alpha(t)$, the advection kernel:

$\alpha\left(t\right)=\ e^{{-L}_{out}t}I_{nxn}=e^{{-L}_{out}t}$ (9)

Similarly, the consensus kernel, $c(t)$, is:

$c\left(t\right)=\ e^{{-L}_{in}t}I_{nxn}=e^{{-L}_{in}t}$ (10)

###  2.3 Adaptive rewiring algorithm

Before the onset of the adaptive rewiring algorithm, the initial network is
$D\ =\ D_{random}$, a network with $N=100$ nodes and
$m=\left[2\log{\left(n\right)}\left(n-1\right)\right]=\ 912$ randomly assigned
to pairs of nodes, with the only exception being that the node cannot point to
itself. The network size and the number of connections have been tested for
undirected networks in previous studies [20] [21]. Adaptive rewiring proceeds
as follows for in-degree connections (and analogously for out-degrees):
Step 1.Select with uniform probability a node k from the nodes with nonzero,
but not n-1, in- and out-degrees.

Step 2.Delete edge (i2, k) and add edge (i1, k). With probability prandom
select i1 and i2 based on the criteria of step 2.1 (random rewiring) otherwise
select them based on step 2.2 (instructed rewiring).
Step 2.1. i1 is selected randomly from the set (i,k)$\notin$E, i.e. nodes that
are not in the in-degree neighborhood of k. i2 is selected randomly from the
set (i,k)$\in$E, i.e. nodes that are in the in-degree neighborhood of k.
Step 2.2. Calculate the kernel of the algorithm used, f(t). From the set of
nodes (i,k))$\notin$E, i1 is the one with the highest concentration transfer
with k. From the set (i,k)$\in$E, i2 is the one with the lowest concentration
transfer with k. Mathematically, this is expressed as follows (f($\tau$)
function represents either $\alpha$($\tau$) or c($\tau$)):

$i_{1}=argmax_{(i,k)\notin E,i\neq k}f_{ik}(\tau)$ (11)
$i_{2}=argmin_{(i,k)\in E,i\neq k}f_{ik}(\tau)$ (12)

Step 3. Go back to step 1 until r edge rewirings have been reached.

We refer to the time variable of the kernel as the rewiring rate ($\tau$),
since before each rewiring we let the concentrations spread for $t=\tau$. We
found that for different rewiring rates, the rewired networks converge to
similar topologies. Thus, in the Results section we show rewired networks for
fixed $\tau=1$. Unless otherwise stated, for each rewiring run we perform r =
4000 rewirings.

###  2.4 Measurement of path length

The path length, Lij defined as the distance between node pairs i and j along
their shortest paths. The average path length of a network is defined as:

$L_{ave}=\ \sum_{i\neq j}\ L_{ij}$ (13)

The drawback with this definition is that we cannot include node pairs that
are not connected via a path between them, for a pair of that sort has
infinite path length. To remedy this, we first measure the efficiency of the
network. Efficiency is defined as the inverse of path length:

$E_{ij}=\frac{1}{L_{ij}}\ $ (14)

For this measure, an ordered pair of nodes yields zero efficiency if there is
no path in the network from the first node in the pair to the second.
Following this definition for the efficiency of a single pair of nodes, the
average efficiency of the whole network -and for n possible node pairs-is then

$E_{ave}=\ \frac{1}{n}\sum_{i\neq j}\ E_{ij}$ (15)

After measuring Eave, we take its inverse to estimate a path length metric.

##  3 Results

###  3.1 Advection and consensus create winner-take-all hubs

We identify a set of nodes as a convergent-divergent unit, if they can receive
input from a pool of nodes in the network and provide an output back to the
pool (Fig. 2). We first investigated which parts of convergent-divergent units
arise from iteratively rewiring an initially randomly connected network, using
solely advection or consensus as a basis for rewiring. For advection-based
rewiring, a characteristic topology evolved when candidate nodes’ out-degree
connections were rewired; the resulting network contained a small subset of
convergent hub nodes, which received connections from all other nodes (Fig
S1A). Conversely, random topology was preserved when advection-based rewiring
was applied to the in-degree neighborhoods (Fig S1B). For consensus-based
rewiring of the in-degree neighborhoods of the nodes, this time the resulting
network obtained a characteristic structure where a small subset of the nodes,
acting as divergent hubs, projected their connections to all other nodes (Fig
S1D). Rewiring the out-degree neighborhoods based on consensus, by contrast,
preserved the network’s random topology (Fig S1C).

Figure 2: A schematic representation of a convergent-divergent structure. A
subset of the nodes receives all the nodes’ input, process it, and outputs it
back to the nodes.

Advection and consensus rewiring affords networks with convergent and
divergent hubs respectively, the main building blocks of convergent-divergent
units. This process is remarkably fast; when out-degree neighbours were
rewired based on advection only, or in-degree neighbours based on consensus
only, the network produced winner-take-all configurations already after 200
rewirings (Fig 3), a much faster convergence compared to the emergence of
modular or centralized structures in undirected networks1,2. However, neither
advection nor consensus by themselves produced convergent-divergent units. We
thus ask: Can their combination produce convergent-divergent units?

Figure 3: Networks converge to winner-take-all configurations after few
rewirings. (A) The evolution of the adjacency matrix at different stages of
rewiring when we use the advection algorithm and rewire the out-degree
neighborhood. The rightmost illustration shows a schematic of a converging hub
(B) Same as (A) but for the consensus algorithm when we rewire the in-degree
neighborhood. The rightmost illustration shows a schematic of a diverging hub.

###  3.2 Combined advection and consensus effects improve node-to-node
communication

To study the combined effects of advection and consensus in one rewiring
scheme, for each iteration of the rewiring algorithm we randomly chose with
probability p(advection) to rewire based on advection the out-degree
neighborhood of a candidate node, and with probability 1-p(advection) to
rewire based on consensus the in-degree neighborhood of a candidate node. We
found that as we increase p(advection), the network transitions from one
dominated by divergent hubs to one dominated by convergent hubs: the vertical
connectivity in the adjacency matrix transitions to a horizontal one (Fig S2).
For any combination of advection and consensus, rewiring resulted in a sharp
decrease in the path length and an increase in the number of nodes connected
via a path compared to the networks rewired solely by advection or consensus
(Fig S3).

We probed further the mixed advection-consensus algorithm for the specific
case of balanced rewiring, when rewiring was based with equal probabilities on
either advection or consensus. This scheme offers a level playing field, on
which networks can develop a balance of hub structures with in-coming or out-
going connections. Maintaining the balance of advection and consensus, we
introduced various proportions Prandom of random rewirings to the algorithm.
That is, at each rewiring we randomly chose with 1- Prandom a rewiring based
with equal proportions on either advection or consensus or with Prandom a
random rewiring. Previous findings have shown that regular network topologies
with some random connections can, to a large extent, maintain their structural
properties while also becoming more efficient in node-to-node communication
[35]. In line with that, we found that random rewiring further decreases the
average path length (Fig S4A) and increases the number of possible paths (Fig
S4B) in the emerged networks. In all cases, we define the average path length
as the inverse of the average efficiency of the network. This enabled us to
incorporate in the measure the node pairs that do not have a path between them
(see Methods subsection: Measurement of Path Length). We found that the
average path length of all possible node combinations (cyan line in Fig 4)
decreases precipitately as Prandom increases (1/Eave,All = 5.28, 4.66, 3.15,
2.44, 2.17 for Prandom = 0, 0.2, 0.4, 0.6, 0.8 respectively). The average
paths lengths between nodes that are connected by a path in the network (blue
line in Fig 4) do not change to a large extent (1/Eave,Paths = 2.42,
2.71,2.37, 2.17 for Prandom = 0.2,0.4,0.6,0.8 respectively). Thus, the
decrease can be attributed to a decrease in the proportion of unconnected node
pairs (red bar in Fig 4).

Figure 4: The number of non-connected nodes decreases (available paths
increase) as Prandom increases. Metrics for rewired networks based on balanced
mixed consensus-advection algorithm for different Prandom values. The orange
bars show the distribution of path lengths, the red bar the proportion of node
pairs that do not have a path, the blue line shows the inverse of the average
efficiency of the networks when considering only the node pairs with a path
between them, and the cyan all possible node pairs. We consider the last two
measures as path length metrics.

We may consider as optimal those networks that have small path lengths (a
topology that is essential for better node-to-node communication) and that
still exhibit the structural properties effectuated by advection and consensus
(convergent and divergent hubs). We find however, that as we increase the
proportion of random rewiring and reduce the path length, we also reduce the
number of hubs in the network (Fig 5A).

To quantify the effects of those two opposing forces, we devised two measures
we call structure efficiency metrics. High values correspond to networks with
high efficiency in terms of node-to-node communication (small path length and
large number of node pairs that are connected via a path) that also maintain
to a large extent their structure (hub nodes). The first metric takes path
length into account. This metric is defined as the ratio of the number of hubs
over the path length. The second metric takes into account the number of
connected nodes. This metric is defined as the number of connected nodes times
the number of hubs. We find that the structure efficiency metric based on path
length reaches a global maximum in absence of random rewiring, but it also has
a local maximum for intermediate proportions of random rewiring (Fig 5B). When
measuring structure efficiency based on available paths, we obtain a different
pattern: the maximum for hubs with smaller in- and out-degrees (50, 60) is
found at intermediate random rewiring proportions (Fig 5C).

Figure 5: Random rewiring can increase structure efficiency in terms of nodes’
connectivity (available paths). (A) Number of hubs as a function of random
rewiring. Hubs are defined as nodes with a minimum number of out-degrees (from
50 to 90) (B) Structure efficiency metric that uses path length as a function
of random rewiring (C) Structure efficiency metric that uses the number of
connected nodes (or available paths) as a function of random rewiring.

###  3.3 Convergent-divergent structures within the network

Synthesizing our results so far, we are now able to obtain structures within
the network that can be identified as convergent-divergent units. Convergent-
divergent units receive input from local nodes, process it, and then outputs
it back to the local nodes (Fig 2). Candidate hub nodes that are part of the
convergent-divergent unit are the ones with a large number of degrees (both
in- and out-degrees). We selected as hub nodes the ones with a minimum number
of total degrees (the addition of in- and out-degrees had to be greater than a
preselected value), that also had a greater than one in- or out-degree. Nodes
outside of the convergent-divergent units were referred to as local nodes.

We require a path for local nodes to access the convergent-divergent unit, and
for the hub nodes in the convergent-divergent unit to feed back to the local
nodes. To this end, we probed the amount of the incoming flow from the local
nodes to the convergent-divergent unit, and of the outgoing flow from the
convergent-divergent unit back to the local nodes. For the incoming flow, we
measured the proportion of local nodes with a path to at least one of the hub
nodes. For the outgoing flow, we measured the proportion of local nodes that
can receive input from the hub nodes. We found that the proportion of nodes
with an incoming path to the convergent-divergent unit and of outgoing paths
from the unit back to the nodes grows with increasing Prandom. The number of
nodes that qualify to be in the convergent-divergent unit also grows with
increasing Prandom, with Prandom $\geq$ 0.4 the proportion for ingoing and
outgoing paths being greater that 0.9 (Fig 6A).

We are also interested in the number of nodes that qualify as hub nodes and
how random rewiring affects this number. We found that the number of hub nodes
increases with increasing Prandom (Fig 6B). This runs counter to intuition
since, in our previous analysis, we showed that random rewiring is detrimental
to the build-up of hub structures. However, in our selection of hub nodes one
requirement is that they have in- and out-degrees that are at least greater
than 1. In absence of random rewiring, there are many nodes that either have
only in-coming or out-going connections. This imbalance is counteracted by
random rewiring. Removing the constraint that hub nodes need to have both in-
and out-connections would reverse the trend, as the number of hub nodes then
decreases with the proportion of random rewiring.

We subsequently examined the connections within the convergent-divergent unit
that are in-between the hub nodes. We consider those that are part of the
shortest path from a pair of converging to diverging hubs. For these
intermediate units, for processing and transformation of incoming information
from the local nodes, dense connectivity and ease of communication within the
convergent-divergent substructure are desirable. We found that the
connectivity density of the in-between nodes, we collectively call the
intermediate unit, is greater than that of connected subnetworks of local
nodes (same number of nodes for both subnetworks; P¡0.001) randomly chosen
from the same network (Fig S5A). This feature facilitates communication and
computation within convergent-divergent units. Along with the hub nodes, which
by definition form a dense subnetwork, the intermediate unit forms the
connective core[36] of the rewired network. Note that the intermediate unit
grows as Prandom increases (Fig S5B).

Figure 6: Paths incoming to the convergent-divergent unit and out of the unit
back to the nodes, as well as the number of nodes qualifying as part of the
unit grow with increasing Prandom. A. Proportion of nodes with a path to the
convergent-divergent unit, and nodes in the unit with an outgoing path back to
the nodes. Left side (In) corresponds to the nodes with incoming connections
to the convergent-divergent unit, and right side (Out) to the unit’s outgoing
connections to the nodes. For the ‘In’ connections, a node is considered to be
connected to the unit if one of its outgoing connections has a path to at
least one of the hub nodes constituting the unit. For the ‘Out’ connections, a
node is considered to be connected to the unit if at least one of the hub
nodes in the unit has an outgoing path to it. A hub node and part of the unit
is considered a node with a minimum number of in-going plus out-going
connections. This number varies from left to right. B. Average number of nodes
in the unit as a function of Prandom for different hub nodes.

##  4 Discussion

Convergent-divergent units are neural network core structures that receive
their input from the local nodes and sends it back to them after processing.
We investigated the emergence of convergent-divergent units within neural
networks through adaptive rewiring based on spontaneous activity. We found
that adaptively rewiring of initially random directed networks leads to the
emergence of converging-diverging units, when the flow of activity is
represented by the directed equivalents of diffusion, advection and consensus.
An additional proportion of random connections improves extensively node
communication by decreasing the average path length and increasing the number
of available paths while maintaining the converging-diverging structure.

For adaptive rewiring to produce converging-diverging units in neural network
models, the application of both advection and consensus is necessary.
Advection-based rewiring of the out-degree neighborhoods produces convergent
hubs; consensus-based rewiring of the in-degree neighborhoods of the nodes
produces divergent hubs. The prominence of either type of hubs in the network
depends on the relative frequency with which consensus or advection-based
rewiring is chosen. Convergent hubs are suitable for information integration,
divergent ones for broadcasting. The proportion may therefore be varied
depending on the position of a hubs in the information processing hierarchy
(e.g. more divergence early in the perceptual processing stream: more
convergence in higher-order areas).

We investigated balanced networks, networks with equal proportions of
advection and consensus-based rewiring. The shortest path between each input
(converging) and output (diverging) hub, could consist of a number of nodes
that are not hubs; we call those intermediate nodes. We found that the
intermediate nodes have a connectivity density that is higher than the local
nodes outside the convergent divergent units. The greater density is a product
of the adaptive rewiring, which adds connections to neighborhoods with
intensive traffic flow. Their position between an input and output hub assures
that intermediate nodes have an intensive in and outflow. The resulting dense
connectivity serves the function of the networks of intermediate nodes as
information processing cores.

Convergent-divergent units with abundant connectivity have been shown to offer
a robust representation and propagation of input in a cascading structure
[37]. Moreover, convergence of variable inputs are pervasive in the brain, for
example neurons in superior temporal sulcus receiving a multimodal sensory
input [38].

The present convergent-divergent structure, which feeds back to its input
nodes is a mechanism that can also give rise to selectivities of sensory
neurons that respond not only to local features but are also sensitive to long
range contextual information. In visual processing, at least as early as in
V1, neurons have been shown to respond to a number of stimuli outside of their
local classical receptive field1, a property that is reflected in perception
[39].

Previous applications of the adaptive rewiring principle on undirected
networks showed topological effects emerging from aggregate activity that
mirrored brain anatomy [20]-[24][40]-[43]. Namely, adaptive rewiring was
sufficient for gradually transforming random undirected networks into
structured architectures with features pervasive in the brain such as small
worldness [44][45], modular connectivity [46][47], and rich-club organization
[48][49]. We studied directional networks, as they offer a more realistic
representation of signal transfer [25]-[27]. Directionality of connections is
important for establishing a processing hierarchy at the level of motifs
[50][51], circuits [52][53], layers [54], clustered axonal branches [55][56],
and functional regions [57]-[59], e.g. for processing sensory information
[58][60] and for sensorimotor control [61]. In addition, as shown here,
networks of directed connections spontaneously evolve a core structure of
convergent-divergent units under adaptive rewiring. Adaptive rewiring can
therefore be considered a key principle of self-organization in brain
networks.

## References

  * [1] Alexander, D. M. and Van Leeuwen, C. Mapping of contextual modulation in the population response of primary visual cortex. Cogn. Neurodyn. 4, 1–24 (2010).
  * [2] Hubel, D. H. and Wiesel, T. N. Receptive fields and functional architecture in two nonstriate visual areas (18 and 19) of the cat. J. Neurophysiol. 28, 229–289 (1965).
  * [3] Blakemore, C. and Tobin, E. A. Lateral inhibition between orientation detectors in the cat’s visual cortex. Exp. Brain Res. 15, 439–440 (1972).
  * [4] Keller, G. B., Bonhoeffer, T. and Hübener, M. Sensorimotor mismatch signals in primary visual cortex of the behaving mouse. Neuron 74, 809–815 (2012).
  * [5] Sasaki, Y. et al. The radial bias: a different slant on visual orientation sensitivity in human and nonhuman primates. Neuron 51, 661–670 (2006).
  * [6] Carandini, M., Heeger, D. J. and Movshon, J. A. Linearity and normalization in simple cells of the macaque primary visual cortex. J. Neurosci. 17, 8621–8644 (1997).
  * [7] Das, A. and Gilbert, C. D. Topography of contextual modulations mediated by short-range interactions in primary visual cortex. Nature 399, 655–661 (1999).
  * [8] Keller, A. J. et al. A disinhibitory circuit for contextual modulation in primary visual cortex. Neuron 108, 1181–1193 (2020).
  * [9] Hupé, J. M. et al. Cortical feedback improves discrimination between figure and background by V1, V2 and V3 neurons. Nature 394, 784–787 (1998).
  * [10] Carandini, M. and Heeger, D. J. Normalization as a canonical neural computation. Nat. Rev. Neurosci. 13, 51–62 (2012).
  * [11] Kumar, A., Rotter, S. and Aertsen, A. Spiking activity propagation in neuronal networks: reconciling different perspectives on neural coding. Nat. Rev. Neurosci. 11, 615–627 (2010).
  * [12] Sur, M. and Leamey, C. A. Development and plasticity of cortical areas and networks. Nat. Rev. Neurosci. 2, 251–262 (2001).
  * [13] Plautz, E. J., Milliken, G. W. and Nudo, R. J. Effects of repetitive motor training on movement representations in adult squirrel monkeys: role of use versus learning. Neurobiol. Learn. Mem. 74, 27–55 (2000).
  * [14] Nudo, R. J. Recovery after brain injury: mechanisms and principles. Front. Hum. Neurosci. 7, 887 (2013).
  * [15] Nudo, R. Adaptive plasticity in motor cortex: implications for rehabilitation after brain injury. J. Rehabil. Med.-Suppl. 41, 7–10 (2003).
  * [16] Hardy, D. and Saghatelyan, A. Different forms of structural plasticity in the adult olfactory bulb. Neurogenesis 4, e1301850 (2017).
  * [17] Chrol-Cannon, J. and Jin, Y. Learning structure of sensory inputs with synaptic plasticity leads to interference. Front. Comput. Neurosci. 9, 103 (2015).
  * [18] Sadaghiani, S., Hesselmann, G., Friston, K. J. and Kleinschmidt, A. The relation of ongoing brain activity, evoked neural responses, and cognition. Front. Syst. Neurosci. 4, 20 (2010).
  * [19] Butz, M., Woergoetter, F. and van Ooyen, A. Activity-dependent structural plasticity. Brain Res. Rev. 60, 287–305 (2009).
  * [20] Rentzeperis, I. and van Leeuwen, C. Adaptive rewiring evolves brain-like structure in weighted networks. Sci. Rep. 10, 1–11 (2020).
  * [21] Jarman, N., Trengove, C., Steur, E., Tyukin, I. and van Leeuwen, C. Spatially constrained adaptive rewiring in cortical networks creates spatially modular small world architectures. Cogn. Neurodyn. 8, 479–497 (2014).
  * [22] Jarman, N., Steur, E., Trengove, C., Tyukin, I. Y. and Leeuwen, C. van. Self-organisation of small-world networks by adaptive rewiring in response to graph diffusion. Sci. Rep. 7, 1–9 (2017).
  * [23] Gong, P. and van Leeuwen, C. Evolution to a small-world network with chaotic units. EPL Europhys. Lett. 67, 328 (2004).
  * [24] van den Berg, D. and van Leeuwen, C. Adaptive rewiring in chaotic networks renders small-world connectivity with consistent clusters. Europhys. Lett. EPL 65, 459–464 (2004).
  * [25] Sheng, M., Sabatini, B. and Südhof, T. C. The Synapse: A Subject Collection from Cold Spring Harbor Perspectives in Biology. (Cold Spring Harbor Laboratory Press, 2012).
  * [26] Heuser, J. et al. Synaptic vesicle exocytosis captured by quick freezing and correlated with quantal transmitter release. J. Cell Biol. 81, 275–300 (1979).
  * [27] Harlow, M. L., Ress, D., Stoschek, A., Marshall, R. M. and McMahan, U. J. The architecture of active zone material at the frog’s neuromuscular junction. Nature 409, 479–484 (2001).
  * [28] Abdelnour, F., Voss, H. U. and Raj, A. Network diffusion accurately models the relationship between structural and functional brain connectivity networks. Neuroimage 90, 335–347 (2014).
  * [29] Chapman, A. Advection on Graphs. in Semi-Autonomous Networks: Effective Control of Networked Systems through Protocols, Design, and Modeling (ed. Chapman, A.) 3–16 (Springer International Publishing, 2015).
  * [30] Olfati-Saber, R., Fax, J. A. and Murray, R. M. Consensus and cooperation in networked multi-agent systems. Proc. IEEE 95, 215–233 (2007).
  * [31] Ren, W., Beard, R. W. and Atkins, E. M. Information consensus in multivehicle cooperative control. IEEE Control Syst. Mag. 27, 71–82 (2007).
  * [32] Jianbo Shi and Malik, J. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22, 888–905 (2000).
  * [33] Belkin, M. and Niyogi, P. Laplacian eigenmaps and spectral techniques for embedding and clustering. in Advances in neural information processing systems 585–591 (2002).
  * [34] Rentzeperis, I. and van Leeuwen, C. Adaptive Rewiring in Weighted Networks Shows Specificity, Robustness, and Flexibility. Front. Syst. Neurosci. 15, 13 (2021)
  * [35] Watts, D. J. and Strogatz, S. H. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998).
  * [36] Shanahan, M. The brain’s connective core and its role in animal cognition. Philos. Trans. R. Soc. B Biol. Sci. 367, 2704–2714 (2012).
  * [37] Shaw, G. L., Harth, E. and Scheibel, A. B. Cooperativity in brain function: assemblies of approximately 30 neurons. Exp. Neurol. 77, 324–358 (1982).
  * [38] Barraclough, N. E., Xiao, D., Baker, C. I., Oram, M. W. and Perrett, D. I. Integration of visual and auditory information by superior temporal sulcus neurons responsive to the sight of actions. J. Cogn. Neurosci. 17, 377–391 (2005).
  * [39] Rentzeperis, I., Alexander, D. M., Kiper, D. C. and van Leeuwen, C. Orientation perception anisotropies indicate functional segregation within the color system. J. Vis. 15, 13–13 (2015).
  * [40] Gong, P. and van Leeuwen, C. Emergence of scale-free network with chaotic units. Phys. Stat. Mech. Its Appl. 321, 679–688 (2003).
  * [41] Hellrigel, S., Jarman, N. and van Leeuwen, C. Adaptive rewiring in weighted networks. Cogn. Syst. Res. 55, 205–218 (2019).
  * [42] Rubinov, M., Sporns, O., van Leeuwen, C. and Breakspear, M. Symbiotic relationship between brain structure and dynamics. BMC Neurosci. 10, (2009).
  * [43] Papadopoulos, L., Kim, J. Z., Kurths, J. and Bassett, D. S. Development of structural correlations and synchronization from adaptive rewiring in networks of Kuramoto oscillators. Chaos Interdiscip. J. Nonlinear Sci. 27, 073115 (2017).
  * [44] Bassett, D. S. and Bullmore, E. T. Small-world brain networks revisited. The Neuroscientist 23, 499–516 (2017).
  * [45] Sporns, O. and Zwi, J. D. The small world of the cerebral cortex. Neuroinformatics 2, 145–162 (2004).
  * [46] Hilgetag, C.-C., Burns, G. A., O’Neill, M. A., Scannell, J. W. and Young, M. P. Anatomical connectivity defines the organization of clusters of cortical areas in the macaque and the cat. Philos. Trans. R. Soc. Lond. B. Biol. Sci. 355, 91–110 (2000).
  * [47] Bullmore, E. and Sporns, O. Complex brain networks: graph theoretical analysis of structural and functional systems. Nat. Rev. Neurosci. 10, 186 (2009).
  * [48] van den Heuvel, M. P. and Sporns, O. Rich-Club Organization of the Human Connectome. J. Neurosci. 31, 15775–15786 (2011).
  * [49] Zamora-López, G., Zhou, C. and Kurths, J. Cortical hubs form a module for multisensory integration on top of the hierarchy of cortical networks. Front. Neuroinformatics 4, 1 (2010).
  * [50] Milo, R. et al. Network motifs: simple building blocks of complex networks. Science 298, 824–827 (2002).
  * [51] White, J. G., Southgate, E., Thomson, J. N. and Brenner, S. The structure of the nervous system of the nematode Caenorhabditis elegans. Philos Trans R Soc Lond B Biol Sci 314, 1–340 (1986).
  * [52] Somers, D. C., Nelson, S. B. and Sur, M. An emergent model of orientation selectivity in cat visual cortical simple cells. J. Neurosci. 15, 5448–5465 (1995).
  * [53] Adesnik, H., Bruns, W., Taniguchi, H., Huang, Z. J. and Scanziani, M. A neural circuit for spatial summation in visual cortex. Nature 490, 226–231 (2012).
  * [54] Mountcastle, V. B. The columnar organization of the neocortex. Brain J. Neurol. 120, 701–722 (1997).
  * [55] Leong, A. T. et al. Long-range projections coordinate distributed brain-wide neural activity with a specific spatiotemporal profile. Proc. Natl. Acad. Sci. 113, E8306–E8315 (2016).
  * [56] Oh, S. W. et al. A mesoscale connectome of the mouse brain. Nature 508, 207–214 (2014).
  * [57] Parent, A. and Hazrati, L.-N. Functional anatomy of the basal ganglia. I. The cortico-basal ganglia-thalamo-cortical loop. Brain Res. Rev. 20, 91–127 (1995).
  * [58] Van Essen, D. C. and Maunsell, J. H. Hierarchical organization and functional streams in the visual cortex. Trends Neurosci. 6, 370–375 (1983).
  * [59] Mogenson, G. J., Jones, D. L. and Yim, C. Y. From motivation to action: functional interface between the limbic system and the motor system. Prog. Neurobiol. 14, 69–97 (1980).
  * [60] Felleman, D. J., and Van Essen, D. C. Distributed hierarchical processing in the primate cerebral cortex. Cerebral cortex (New York, NY: 1991) 1.1, : 1-47 (1991)
  * [61] Loeb, G. E., Brown, I. E. and Cheng, E. J. A hierarchical foundation for models of sensorimotor control. Exp. Brain Res. 126, 1–18 (1999).

Supplemental Materials: Adaptive rewiring evolves brain-like structure in
directed networks

Figure S1: Examples on the effects of advection (left side) and consensus
(right side) on the evolution of a random network (adjacency matrix in the
middle) when only the out-degree neighbors of the candidate nodes are rewired
(top) or the in-degree neighbors (bottom). Figure S2: As we increase
p(advection), the vertical (out-degree hubs) connectivity transitions to a
horizontal (in-degree hubs) one. From left to right: example adjacency
matrices for p(advection) = 0.2, 0.5, 0.8.

Figure S3: The combination of advection and consensus in a rewiring scheme
decreases path length and increases possible paths compared to rewiring based
only on advection or consensus (A) Average path length as a function of
p(advection) (B) Possible paths as a function of p(advection). The data points
and vertical lines in these and subsequent figures denote the means and
standard deviations from 100 runs.

Figure S4: In a combined advection/consensus scheme, random rewiring
contributes in decreasing path length and increasing connectivity between
nodes (A) Average path length and (B) Possible paths as a function of Prandom.

Figure S5: The intermediate connections in a convergent-divergent unit are
denser compared to a subset of simple nodes. A. Density of the intermediate
connections from the convergent-divergent unit and from a subset of simple
nodes as a function of Prandom for different hub nodes criteria values. The
nodes constituting the subset of simple nodes were selected randomly from the
pool of all the simple nodes in the network. The number of nodes in the two
substructures had to be equal. B. Number of intermediate nodes as a function
of Prandom for different hub nodes criteria values.