Optimization in Gradient Networks
Optimization in Gradient Networks
Natali Gulbahce∗
Theoretical Division and Center for Nonlinear Studies,
Los Alamos National Laboratory, MS B284, Los Alamos, NM 87545, USA
(Dated: November 5, 2018)
Gradient networks can be used to model the dominant structure of complex networks. Previous
works have focused on random gradient networks. Here we study gradient networks that minimize
jamming on substrate networks with scale-free and Erdős-Rényi structure. We introduce structural
correlations and strongly reduce congestion occurring on the network by using a Monte Carlo opti-
mization scheme. This optimization alters the degree distribution and other structural properties of
the resulting gradient networks. These results are expected to be relevant for transport and other
dynamical processes in real network systems.
PACS numbers: 89.75.k, 05.45.Xt, 87.18.Sn
Complex networks have been shown to offer a
powerful framework for the study of dynamical
processes in complex systems [1, 2]. A fundamen-
tal question in this context is to identify how the
structure of dominant connections influences the
dynamical properties of the entire system. Gradi-
ent networks have been introduced in references
[4, 5] precisely to characterize the structure gov-
erning transport in complex networks. Remark-
ably, similar structures have been identified re-
cently in the optimization of synchronizability in
oscillator networks [6, 7]. Here, we consider the
problem of optimization of transport and show
that by using a Monte Carlo approach congestion
can be reduced in complex networks. We discuss
the structural correlations that emerge with op-
timization and its implications for real systems.
I. INTRODUCTION
The efficiency of transport systems has been of interest
in various fields, including physics, biology and engineer-
ing. In transport processes, the item being transported
usually follows the steepest descent of the underlying sur-
face, e.g., water flowing down the slopes of a mountain.
Flow in networks has been modeled by Toroczkai et al.
[4, 5] by the introduction of local gradients on a sub-
strate network. The gradient network defined on this
network has provided significant insights into the domi-
nant structures that provide transport efficiency. They
have considered a fixed network of N nodes with a scalar
potential, Vi at each node i. The gradient ∇Vi of the po-
tential at each node i is a directed edge which points from
i to the neighbor with the minimum potential among all
the neighbors of i.
Toroczkai et al have shown several properties of gradi-
ent networks which we briefly summarize. An interest-
∗E-mail address:gulbahce@lanl.gov
ing topological property of the gradient network is that
its in-degree distribution is scale-free for both scale-free
(SF) and Erdős-Rényi (ER) substrate networks [2]. A
gradient network with a non-degenerate potential distri-
bution, is a group of trees, hence no loops exist in this
network other than self-loops. Only this property makes
the gradient networks very common in seemingly unre-
lated problems, i.e., synchronization in oscillatory net-
works [6, 7]. The relationship between network topology
and congestion has also been investigated [4, 5] by intro-
ducing a measure of congestion, the jamming coefficient.
This measure involves the ratio of the number of nodes
that receive at least one gradient link, Nreceive and the
number of nodes that send a link. By definition, every
node sends one out link, therefore the number of senders
in the network, Nsend = N . The jamming coefficient is
J = 1− 〈〈Nreceive/Nsend〉V 〉network . (1)
The operations 〈. . .〉V and 〈. . .〉network denote the sta-
tistical averaging over local potentials and networks re-
spectively. Maximal congestion occurs at J = 1, and
no congestion occurs when every link receives a gradient
link, corresponding to J = 0. It was also found that
J is independent of number of nodes N for scale free
substrate network, and these networks are not prone to
maximal jamming. The jamming coefficient was exten-
sively studied by Park et al. [8] where they compared it
for ER and SF networks with the same average degree,
〈k〉, for 2 < 〈k〉 < 200. With randomly assigned poten-
tials on each node, below 〈k〉 ≈ 10, they found that ER
networks are less congested than SF networks.
Here we introduce a Monte Carlo optimization scheme
that reduces jamming significantly and introduces struc-
tural correlations into the system that are not built in.
The remainder of the paper is organized as follows. In
Section II we introduce the algorithm for optimizing jam-
ming coefficient that is initially calculated from randomly
assigned scalar values at each node. We compare the op-
timized jamming values of a scale-free network and an
Erdős-Rényi network for various values of average de-
grees. In Section III we investigate the structure of the
http://arxiv.org/abs/0704.1144v1
mailto:gulbahce@lanl.gov
optimal gradient network. In particular we study the de-
gree distribution and the correlations between the degree
and the potential of each node. Finally in Section IV we
discuss the implications and the possible extensions of
optimal gradient networks.
II. OPTIMIZATION OF JAMMING
Previous work [4, 5] has focused on random gradient
networks where the potential on each node has a ran-
domly assigned value. More generally, the potentials can
be a dynamic quantity evolving in time due to perturba-
tions, sources and sinks internal and external to the sys-
tem of interest. Alternatively, the potentials can evolve
to become correlated to the network properties such as
its degree distribution. For example, consider the net-
works of routers where every router has a capacity. If a
router is central and highly connected, it usually has a
higher capacity in order to handle the traffic en-route ef-
fectively. Recently, a congestion aware routing algorithm
has been introduced where the transport on the network
of routers is driven by congestion-gradients [9].
Here we develop a Monte Carlo algorithm to achieve
two goals: reduce jamming in the network, and observe
the emerging optimal correlation between in-degree and
potential of each node. For a given network and potential
distribution, we redefine J in Eq. 1 as J = 1−Nreceive/N
where Nsend = N by definition. The initial potential dis-
tribution is chosen from a Gaussian distribution, and at
each iteration the potential of a random node is mod-
ified such that global congestion is reduced. We use a
Metropolis algorithm [11] with the following steps:
1. Pick a node, i at random.
2. Vary Vi by δV , i.e., Vinew = Vi + δV where δV is a
Gaussian random variable with variance σ2 = 1.
3. Recalculate J with Vinew.
4. Accept Vinew with probability p ∼ exp[−∆J/T ]
where ∆J = Jnew − Jold.
5. Go to step 1, and repeat.
The fictitious temperature, T is chosen to adjust the ac-
ceptance ratio to about 40%. We perform the optimiza-
tion procedure until J(t) equilibrates, i.e., at large t the
time autocorrelation function of J(t) [10],
CJ (t) =
[〈J(t)J(0)〉 − 〈J〉2]
[〈J2〉 − 〈J〉2]
, (2)
goes to zero.
Using the described optimization algorithm, we can
significantly reduce the jamming coefficient in both SF
and ER networks. Following previous work [4, 8] we
choose as the SF network a Barabási-Albert model [2, 3].
For this network the average connectivity is 〈k〉 = 2m
where each node has at minimum m links. The network
size throughout the paper is chosen to be N = 10000. For
the ER networks, 〈k〉 = pN where p is the probability of
having a link between any pair of nodes. We use the
same 〈k〉 when comparing the two types of network by
adjusting m and p. The evolution of jamming coefficient
during optimization is shown in Fig. 1 as a function of
algorithmic time in units of Monte Carlo steps (mcs) for
〈k〉 = 4. At t = 0 (see also inset of Fig. 1), the SF network
has a higher jamming coefficient, but after roughly 50000
mcs, the SF network becomes less congested compared
to the ER network. The initial and final jamming coeffi-
cients for the two networks are JiSF = 0.57, JiER = 0.52,
JfSF = 0.31, and JfER = 0.36, respectively.
 0  40000  80000
 4 10  6 10  8 10  1 10 2 10
t(mcs)
5. 5. 5. . 65.
FIG. 1: Optimized jamming, J(t), as a function of time in
Monte Carlo steps (mcs) for SF (•) and ER (◦) networks with
the same average degree, < k >= 4 and N = 10000. As shown
in the inset, SF network with random potential distribution
has a higher jamming coefficient at t = 0 compared to the ER
network. After optimization is completed, however, optimal
SF network has a lower jamming coefficient.
We define ∆Jr and ∆Jo, the difference in jamming be-
tween SF and ER networks for random and optimal net-
works respectively. For a given network with 〈k〉, ∆Jr is
calculated initially at t = 0 and ∆Jo at topt after opti-
mization is completed, for 2 ≤ 〈k〉 ≤ 126. As shown in
Fig. 2, ∆Jo < 0 for 〈k〉 > 2 whereas ∆Jr > 0 indicating
that SF networks have a lower jamming coefficient after
optimization, a result significantly different than those
for random gradient networks [8].
III. STRUCTURAL PROPERTIES OF OPTIMAL
NETWORKS
As shown in Fig. 1 congestion can be reduced in gra-
dient networks by varying the potentials at each node.
It is reasonable to expect that the obtained optimal po-
tentials may also alter the structure of the gradient net-
work. Next, we analyze the structural properties of op-
 0  20  40  60  80  100  120  140
random
optimal
FIG. 2: Difference between the jamming values of SF and ER
networks, ∆J = JSF − JER for various 〈k〉 for random (◦)
and optimal (•) gradient networks. ∆J < 0 for all simulated
〈k〉 > 2 indicating that optimal SF networks have a lower
jamming coefficient than optimal ER networks.
timal gradient networks such as the degree distribution.
Previously, the random gradient network of an ER sub-
strate network was shown numerically and analytically
[4, 5] to have an in-degree distribution of R(l) ∼ l−1.
However, the SF substrate network with degree distribu-
tion P (k) ∼ k−3, was shown to have a gradient degree
distribution of R(l) ∼ l−3.
The degree distribution of the random and optimal ER
and SF networks are shown for p = 0.001 (〈k〉 = 10) and
m = 3 (〈k〉 = 6) respectively in Figure 3 along with
the expected scaling exponents for the random gradient
networks of −1 and −3. The statistical averaging is ob-
tained over 100 networks. For ER networks, the scaling
region extends with higher average connectivity, however
we chose to use a small 〈k〉 = 10 for which optimization is
more efficient. The optimization is performed for 1 mil-
lion Monte Carlo steps. The jamming values initially are
0.62, 0.71 and after optimization reduce to 0.36, 0.60 for
SF and ER respectively. The in-degree distribution, R(l),
for the SF network varies significantly with the optimiza-
tion. The cut-off degree is reduced an order of magnitude
(from roughly 100 to 10) compared to the random one,
and the scaling is now steeper. On the other hand, the
ER network does not show a major change in the degree
distribution.
Next, we analyze the probability distribution of poten-
tials for nodes in the substrate networks with degree k,
before and after the optimization to observe any degree-
potential correlations. The results are shown in Fig. 4
for the SF network (m = 3). To reduce noise in the data
especially for large values of k, the degrees are binned
into four groups: 3 < k ≤ 10, 10 < k ≤ 30, 30 < k ≤ 50,
50 < k ≤ 100. Before optimization with initial random
Gaussian potentials within range [-4, 4] , each set has the
same probability distribution P (Vi) as shown in the inset
of Fig 4. This behavior is expected as no correlation was
 0.01
 0.01
 1000
FIG. 3: In-degree distributions, R(l), for gradient networks of
(a) SF and (b) ER networks with m = 3 and p = 0.001 respec-
tively before (◦) and after (•) optimization of jamming. The
dashed lined indicates the scaling of R(l) ∼ lα from Ref. [4, 5],
where α = −3 and −1 for random SF and ER networks re-
spectively. The scaling exponent α is not a good fit for opti-
mal SF data but a good fit for optimal ER network.
built in between the degree of a node and its potential.
After the optimization however, the range of the poten-
tials has broadened significantly, and the nodes with high
degree have accumulated very large potentials.
With the improved jamming coefficient, it is natural
to expect some correlation to emerge between the poten-
tial of the node and its degree. If the node has a large
degree and a small potential, this node will be preferred
by most of its neighbors for sending an out link, and
thus this will contribute to higher jamming. However if
the potential is large, the neighboring nodes will not pre-
fer this highly connected node and thus not increase the
jamming. This intuitive observation implies the possi-
bility of obtaining a reduced congestion by starting with
potentials that are inversely correlated with the degree
of each node on the substrate network. We tested this
case for the SF network (m = 3) with a correlated po-
tential distribution, Vi = r/ki at node i with degree ki
V (k)i
V (k)
 0.04
 0.08
 0.12
−40 −20  0  20  40
 0.00
−4 −2  0  2  4
FIG. 4: Probability distribution of the potentials of nodes
with degree k for SF network with m = 3 before (inset)
and after optimization. The degrees are binned to indicate
the correlation between degree of a node and its potential:
3 < k ≤ 10 (+), 10 < k ≤ 30 (�), 30 < k ≤ 50 (•),
50 < k ≤ 100 (◦). Before the optimization P (Vi) do not
show any correlations with k, however after the optimization,
nodes with high degree, get the large values of potential which
facilitates reduced jamming.
where r is a random number chosen from a uniform dis-
tribution. This assignment with correlations built-in did
not make the jamming coefficient lower. On the contrary
it was higher, J = 0.77, than the value without degree
correlation, J = 0.62.
An interesting observation that Fig. 4 provides is that
nodes with small degree carry potentials distributed over
a large range [−40, 40]. For example, nodes with degrees,
3 < k < 10 have a roughly Gaussian potential distribu-
tion. For higher k, the distribution narrows down and
shifts toward larger values. For nodes with 50 < k < 100,
all nodes have large potentials, within range [0, 40]. This
observation might explain why in the test case the jam-
ming was actually higher when the degree was correlated
with the potential. In that case, we only assigned low po-
tentials to low degree nodes which still yields congestion
much higher than the optimal one. An analytical for-
mulation that distributes the potentials according to its
degree mimicking the transitive behavior in Fig. 4 seems
possible, but is beyond the scope of this paper.
IV. CONCLUSION
We have introduced a Monte Carlo method to optimize
congestion in random gradient networks. Previously the
potentials have been assigned randomly and was shown
that ER networks had lower jamming coefficient below
〈k〉 = 10 than SF networks with the same connectivity
[8]. This was puzzling as the connectivity commonly ob-
served in natural and man-made networks [2] is usually
in this range, but tends to be scale-free, and in scale-free
networks jamming is independent of N . With the Monte
Carlo based optimization scheme we optimized jamming
by varying the potentials so that optimal congestion was
achieved. We found that optimal SF networks have lower
congestion factor for 〈k〉 > 2. This reduced congestion
is the result of a complex correlation between the degree
and the potential of a node. We found that nodes with
large degrees in the substrate network get large positive
values whereas nodes with small degrees get a Gaussian
like distribution of potentials.
Throughout the paper we have used the definition of
jamming introduced in Ref. [4] for a substrate network
with unweighted links. A natural extension of this work
for generality is to assign weights to links and redefine the
jamming coefficient accordingly. A possible definition is
wij−ci
ci where i = 1 · · ·N , j is the
number of neighboring links node i has, ci is the capacity
of node i, wij is the weight of the incoming link from j
to i, and the operation [x] = 0 if x < 0. If the weights
and capacity of all nodes are 1, then this definition of J
reduces to the one in Eq. 1 without the averaging. With
this definition and the optimization method introduced
in the paper, it is possible to study real world networks
and get insights to the dominant structures of transport
for these systems.
Acknowledgments
The author thanks Adilson E. Motter for useful dis-
cussions and suggestions, Gregory Johnson and Frank
Alexander for the careful reading of the manuscript. This
work was carried out under the auspices of the National
Nuclear Security Administration of the U.S. Department
of Energy at Los Alamos National Laboratory under
Contract No.DE-AC52-06NA25396 and supported by the
DOE Office of Science ASCR Program in Applied Math-
ematics Research.
[1] A. E. Motter, M. A. Matias, J. Kurths, and E. Ott, Phys-
ica D 224, vii (2006).
[2] M. E. J. Newman, A.-L. Barabási and D. J. Watts (Edi-
tors), The Structure and Dynamics of Networks (Prince-
ton University Press, 2006).
[3] A.-L. Barabási and R. Albert, Science 286, 509 (1999).
[4] Z. Toroczkai and K. E. Bassler, Nature 428, 716 (2004).
[5] Z. Toroczkai, B. Kozma, K. E. Bassler, N. W. Hengart-
ner, and G. Korniss, e-print cond-mat/0408262.
[6] T. Nishikawa and A. E. Motter Phys. Rev. E 73, 065106
(2006).
[7] T. Nishikawa and A. E. Motter, Physica D 224, 77
(2006).
[8] K. Park, Y.-C. Lai, L. Zhao, and N. Ye, Phys. Rev. E
71, 065105 (2005).
[9] B. Danila , Y. Yu, S. Earl, J. A. Marsh, Z. Toroczkai,
and K. E. Bassler, Phys. Rev. E 74, 046114 (2006).
[10] H. Gould, J. Tobochnik and W. Christian, Introduc-
tion to Computer Simulations Methods, Addison-Wesley
(2006).
[11] M. E. J. Newman and G. T. Barkema, Monte Carlo
Methods in Statistical Physics, Oxford University Press
(1999).
http://arxiv.org/abs/cond-mat/0408262
