# Exploration of Network Scaling: Variations on Optimal Channel Networks

Lily Briggs  Mukkai Krishnamoorthy

###### Abstract

Metabolic allometry, a common pattern in nature, is a close-to-3/4-power
scaling law between metabolic rate and body mass in organisms, across and
within species. An analogous relationship between metabolic rate and water
volume in river networks has also been observed. Optimal Channel Networks
(OCNs), at local optima, accurately model many scaling properties of river
systems, including metabolic allometry. OCNs are embedded in two-dimensional
space; this work extends the model to three dimensions. In this paper we
compare characteristics of 3d OCNs with 2d OCNs and with organic metabolic
networks, studying the scaling behaviors of area, length, volume, and energy.
In addition, we take a preliminary look at comparing Steiner trees with OCNs.
We find that the three-dimensional OCN has predictable characteristics
analogous to those of the two-dimensional version, as well as scaling
properties similar to metabolic networks in biological organisms.

##  1 Introduction

Fractal Networks have been widely used to study well known network behaviors.
Some of the properties commonly used in the study of fractal networks are
scaling factors (or laws); scaling laws can describe how lengths are related
to area and areas are related to volumes. In this paper, we further study
these allometric scaling laws. We use simulation and elementary mathematical
bounding techniques to study such laws.

A common pattern in nature, known as metabolic allometry, is a 3/4-power
scaling law between metabolic rate ($M$) and body mass ($B$) in organisms,
across and within species: $B\propto M^{3/4}$. An analogous relationship
between water mass ($C$) and contributing area ($A$) in river networks has
also been observed: $A\propto C^{2/3}$.

The relationship in biological organisms was first observed by Max Kleiber in
1932 and has garnered a lot of attention in the last decade and a half from
biologists, mathematicians, and physicists alike [13]. The areas this
relationship finds application in include models of climate change effects in
rivers [19] and oceans [15], analyses of river stability [17], and in studies
of information networks [18]. Many theories concerning the origins and nature
of this phenomenon have been proposed, and there has been much debate about
how ubiquitous the scaling law really is.

In 1997, West, Brown and Enquist (WBE hereafter) introduced a theory
purporting to explain metabolic scaling [26]. Their theory is based on the
idea of a fractal space-filling hierarchical network of resource distribution,
with certain assumptions based on simplified biology. The geometry of the
network (e.g. branching ratios, vessel radius relationships) are important to
the development of their result. The authors claimed the model is applicable
even to organisms without a physical blood vessel network since they can be
treated as having a virtual distribution network [27].

Subsequent studies questioned the WBE results, by showing that data does not
appear to strictly follow a 3/4-power scaling law after all; the theoretical
approach taken by WBE has also been criticized [1, 28]. Some authors claim
that an exponent of 2/3 fits the data better [9], while others assert that no
universal scaling law exists at all [14]. Savage et al. pointed out that the
WBE model predicts a curvilinear relationship between $logB$ and $logM$, and
only predicts a constant power-law relationship in the infinite limit of body
size; however, even with finite size adjustments and variations in the
structural properties of the model, they found the results were still
inconsistent with data [25]. Some other modifications to the WBE model do
yield results somewhat more consistent with data, such as taking into account
body temperature [5] or fluid velocity [4]. Kolokotrones et al. use regression
on large set of organism data to show a quadratic, rather than linear,
relationship between $logB$ and $logM$ [14]. Also, their results reported a
lot of variation. They build off the modifications to WBE in [25] and find
that a model network with a proportional transition between area-increasing
and area-preserving branching yields a fit to the data almost as good as their
empirically-derived quadratic model.

Other theories and models have been put forth, some based on network
properties like the WBE model, and others on other biological properties.
Dodds [10] proposed a model based on virtual networks of metabolite
transportation rather than physical networks.

Banavar et al. proposed a general model for any efficient transportation
network, predicting $B\propto M^{D/(D+1)}$ (at most) where $D$ is the
dimension of the network (i.e. $D=3$ for organism metabolism, and $D=2$ for
river networks) [3]. Thus, they predict that if the network were as efficient
as possible, organism metabolism should scale as $B\propto M^{3/4}$, and
deviations of the exponent below $3/4$ might be explained by some inefficiency
in the metabolic distribution network. Later the authors added to this model a
supply and demand mechanism that accounts for the deviations [2].

Isaac et al. propose a less strict understanding of the “3/4-power law”:
though the 3/4 exponent might not be a consistent, universal constant, it is
still an observable trend; if there isn’t a single unifying principle
explaining why it appears, there still may be multiple reasons for it worth
studying [12].

In the context of river networks, the analogous properties to metabolic rate
and body mass are contributing area (A) and water mass (C). It is well-
observed that the properties obey a power-law relationship with an exponent of
slightly more than 2/3: $A\propto C^{2/3}$. This is consistent with the
general resource transportation model of Banavar et al. [3] for systems in two
dimensions, and also with the virtual network model of Dodds [10].

Rinaldo et al. devised a model of river networks called Optimal Channel
Networks (OCNs) [21]. This model uses a grid network to represent the area of
a river basin, and constructs a spanning network on the grid that minimizes a
functional representing the energy required to drain the area of land through
river channels. The energy functional is derived both from theoretical
physical characteristics and observed characteristics of river basins [23].
Statistical properties of Optimal Channel Networks (including metabolic
allometry) correspond excellently with observed properties of real river
networks [16, 22].

This paper explores a three-dimensional version of OCNs, using simulations to
compare characteristics of 3d OCNs with 2d OCNs and with organic metabolic
networks and study the scaling behavior of area, length, volume, and energy.
We do not attempt to explain 3/4-power scaling in nature, but rather explore
some interesting and potentially useful connections, somewhat in the spirit of
Isaac et al.’s proposed understanding of the scaling law [12].

We further study an alternative model using Steiner trees for OCNs and we
compare the scaling behaviors between these two models on small network sizes.

Section 2 describes definitions and methodologies used in our paper. In
Section 3, we derive lower bound results for various scaling laws. In section
4, we describe our simulation results and show Energy, Length and Volume
Scaling with respect to area and compare it with the lower bound results
described in Section 3. In Section 5, we describe an alternative model based
on Steiner Trees and derive analytical results for small network sizes.
Section 6 gives conclusions and suggestions for future work.

##  2 Definitions and Methods

Consider an area of land, and embed a grid network in it such that every node
in the network is associated with a unit area of land. Construct a spanning
tree on the grid and direct it so that all nodes have a path in the tree to a
single root (call it the outlet). Define a partial order on the nodes such
that $x\leq y$ iff $x$ is on the path from $y$ to the root. If $x<y$, we will
say $y$ is upstream of $x$. The terms area, volume, upstream length, link
length, and energy are defined here in this context.

Note that each node in the spanning tree, except for the root, has exactly one
link directed out of it. Thus we can name each link according to its
corresponding node; that is, when we speak of link $x$ we are referring to the
link out of node $x$. All the properties defined here for nodes will be
extended to their corresponding links. For example, the area of link $x$ is
defined to be the area of node $x$.

The area of node $x$, $A_{x}$, is the total number of nodes whose paths to the
outlet include $x$; that is, the number of nodes $y$ such that $x\leq y$. This
is equivalent to the sum of the areas of each node directly linked to $x$ plus
one for $x$ itself:

$A_{x}\>=\>\sum_{y}A_{y}\>+\>1$ (1)

where y ranges over the nodes directly linked to x [21].

The volume of node $x$, $C_{x}$, is the sum of all the areas of all nodes
upstream of $x$ [3]:

$C_{x}\>=\>\sum_{y|x<y}A_{y}$ (2)

Equation 2 can be transformed into a recursive definition for volume:

$C_{x}\>=\>\sum_{y}(C_{y}+A_{y})$ (3)

where y ranges over the nodes directly linked to x.

Upstream length is another quantity of interest; it is defined as the number
of links in the path from a node $x$ to a source node, where at each step
upstream the path taken goes to the node with the largest area [7].
Statistically, it is equivalent to define it as the distance (counted in
number of links) to the farthest away upstream source [20].

Link length is a weight assigned to each link, generally representing the
geometric length of the link in the embedding. The length of link $i$ is
denoted by $l_{i}$.

Energy is a function of the link lengths and areas of all the links. The
energy of a given tree configuration $s$ is given by:

$H_{\gamma}(s)=\sum_{i\in links(s)}{A_{i}^{\gamma}l_{i}}$ (4)

with $0\leq\gamma\leq 1$. A tree network that achieves the minimum
$H_{\gamma}(s)$ over all possible tree configurations on a given grid is an
optimal channel network [21].

Figure 1 shows a grid and a possible tree configuration $s_{1}$. $s_{1}$
minimizes $H_{1/2}(s)$ for all configurations on this grid. Area, volume and
upstream length values are also depicted for the nodes in $s_{1}$.

(a) Underlying grid

(b) Areas of nodes
in $s_{1}$

(c) Volumes of nodes
in $s_{1}$

(d) Upstream lengths
of links in $s_{1}$

Figure 1: The outlets are in the top left corners. Tree $s_{1}$ minimizes
$H_{1/2}(s)$ for the grid in 1(a). $H_{1/2}(s_{1})=24.3024964149$.

Rinaldo et al. [21] derived a gamma value of 1/2 from estimations of physical
properties of rivers, and hypothesized that natural rivers would minimize
$H_{1/2}(s)$. A remarkable result of [21] is that while the global optima of
OCNs do not match well statistically with real river networks, the local
optima are an excellent match. The idea that nature tends towards a local
optimum makes sense, so this suggests that OCNs are a good model for what
actually happens in a river [23].

When $\gamma=1$ and all links are of unit length, the energy is equivalent to
the volume. When $\gamma=0$, the energy is equivalent to the total length of
all links, so minimizing the energy is equivalent to finding a minimum
spanning tree (which, when all links are of unit length, would be _any_
spanning tree).

In most studies of OCNs, the network of potential links is a 2-dimensional
lattice with additional links between diagonally-adjacent pairs of nodes (Fig.
2(a)). For the sake of simplicity, all the links, diagonal and orthogonal, are
here considered to have unit length, because it has been shown ([23]) that the
properties with which this paper is concerned are independent of whether the
diagonal links are given realistic length or not.

(a) 7x7 network of potential links

(b) 2x2x2 3d network of potential links

Figure 2:

In this study we also analyzed a three dimensional version of optimal channel
networks, built on a 3-dimensional grid (Fig. 2(b)).

To make an OCN, we first generated a random spanning tree on a given grid. We
used Prim’s algorithm for minimum spanning trees for this. Essentially, the
algorithm builds the tree from a root node, maintaining a set of frontier
edges from the grid that are incident on exactly one node in the tree. Our
algorithm randomly chooses one edge at a time from this set, adds it to the
tree, and updates the set. Rinaldo et al. also began with random spanning
trees, though they did not specify their method for generating them [21].

The random tree was then optimized using a version of Lin’s algorithm for TSP,
as in [21]. That algorithm is as follows:

Input: Undirected graph $G$; random spanning tree $T$, directed so that there
exists a path in $T$ from each node to a single root

Output: Locally optimal spanning tree on $G$

while  _Convergence has not been reached_ do

Step 1: Choose a random node $i$ in $T$

Step 2: Choose a random neighbor of $i$ in $G$ distinct from the node $i$

links to in $T$

Step 3: Construct $T^{*}$ from $T$ by redirecting $i$ to link to this new node

if  _$T^{*}$ contains a loop_ then discard $T^{*}$ ;

else if  _$H_{\gamma}(T^{*}) <H_{\gamma}(T)$_ then discard $T$ and let $T^{*}$
be the new $T$ ;

else discard $T^{*}$;

The condition for convergence was that the number of improvements made be only
1% of the total number of iterations (or 2% for larger networks). See Figure 3
for an illustration of the process.

(a) Initial tree configuration $T$. The outlet is in the top left corner.
$H_{\gamma}(T)=9.65028$.

(b) Step 1: Node $i$ has been chosen; the unused links to its neighbours in
$G$ are highlighted.

(c) Step 3: A new link for $i$ in the tree has been chosen, creating $T^{*}$.
$H_{\gamma}(T^{*})=9.8637>H_{\gamma}(T)$, so this tree will be discarded.

(d) the next iteration, Step 3: A different new link for $i$ in the tree has
been chosen, creating $T^{*}$. $H_{\gamma}(T^{*})=9.44949<H_{\gamma}(T)$, so
this tree will become the new $T$.

Figure 3: Optimization algorithm

(a)

(b)

Figure 4: A random tree spanning a 60x60 grid (a) and the resulting locally
optimal OCN (b). The outlets are in the top left corners. Figure 5: An OCN on
a 3x3x3 grid; the red links are in the OCN.

Figure 4(a) shows a random tree on a 60x60 grid and Figure 4(b) shows the
result of using the above algorithm to optimize the tree. In order to make the
structure of the network clearer, links are drawn with a thickness
proportional to the log of their area. Figure 5 depicts a three-dimensional
OCN on a 3x3x3 grid.

A range of grid sizes were analyzed. Two-dimensional $n$x$n$ grids with $n=$
$10$, $20$, $30$, $40$, $50$, $60$, $70$, and $80$, and three-dimensional
$n$x$n$x$n$ grids with $n=8$, $10$, $12$, $14$, $16$, $18$, and $20$ were
used. For the smaller grids, data was averaged from at least $4$ realizations
of each size, while for the larger grids at least $3$ realizations were used
for each. The quantities measured were distributions of area and length in
whole basins, and average length, volume, and energy per area of subbasins and
whole basins.

##  3 Analytical Proofs

###  3.1 Energy bounds

In [8], Colaiori et al. proved lower bounds for the energy of OCNs on an
orthogonal grid (one with no diagonal links). Here, we look at lower bounds
for the energy of OCNs on an eight-neighbor grid. The main result for this
section (Theorem 3) is that for an $n\times n$ 8-way grid,
$\frac{3}{2}n^{2}-\frac{7}{2}n+1$ is a lower bound on $H_{0.5}(s)$.

######  Lemma 1.

Let (P) be the optimization problem

$\begin{array}[]{rl}\min&\displaystyle\sum_{i=1}^{n}A_{i}^{\gamma}\\\
\mbox{s.t.}&\displaystyle\sum_{i=1}^{n}A_{i}=n+m\\\ &A_{i}\geq 1\>\>\forall
i\\\ &A_{i}\in\mathbb{Z}\>\>\forall i\end{array}$

where $n$ is the number of entries in the vector $A$, $m$ is some natural
number, and $0\leq\gamma\leq 1$.

$A_{1}=A_{2}=...=A_{n-1}=1,A_{n}=m+1$ is an optimal solution to $(P)$.

###### Proof.

Suppose A is an optimal solution for $(P)$ and $\exists j$ s. t.
$1<A_{j}<m+1$.

$\exists k\>\>s.t.\>\>1<A_{k}<m+1,j\neq k$.

We can construct $A^{*}$ such that $A^{*}_{i}=A_{i}\>\>\forall i\neq j,k$;
$A^{*}_{j}=1$; $A^{*}_{k}=A_{j}+A_{k}-1$.

Then
$\sum_{i=1}^{n}{A^{*}_{i}}^{\gamma}=(\sum_{i=1}^{n}A_{i}^{\gamma})-A_{j}^{\gamma}-A_{k}^{\gamma}+1+(A_{j}+A_{k}-1)^{\gamma}$.

Since $f(x)=x^{\gamma}$ when $0\leq\gamma\leq 1$ is concave, and
$A_{j},A_{k}>1$, $(A_{j}+A_{k}-1)^{\gamma}\leq
A_{j}^{\gamma}+A_{k}^{\gamma}-1$. So
$\sum_{i=1}^{n}{A^{*}_{i}}^{\gamma}\leq\sum_{i=1}^{n}A_{i}^{\gamma}$. Thus
$A^{*}$ must be an optimal solution for $(P)$. By an iteration of this
argument, there must be an optimal solution $A^{+}$ with all entries except
for one equal to $1$. Without loss of generality, the entries can be
rearranged so that $A^{+}_{n}$ is the largest (only non-unit) entry. ∎

######  Theorem 2.

For an $n\times n$ eight-neighbor grid $G$, the optimal $H_{1}(s)$ is
$\frac{4n^{3}-3n^{2}-n}{6}$.

###### Proof.

Figure 6: The five “stripes” of a $5\times 5$ 8-way grid with the outlet in
the bottom left corner.

Consider the subsets of vertices $C_{k}$ where vertex $i\in C_{k}$ iff the
distance from $i$ to the outlet equals $k-1$ (Figure 6). In an $n\times n$
8-way grid there are n such stripes. Assuming the outlet is located in a
corner, $|C_{k}|=2k-1$. Clearly,

$H_{\gamma}(s)=\sum_{i\in links(s)}A_{i}^{\gamma}=\sum_{k=2}^{n}\sum_{i\in
C_{k}}A_{i}^{\gamma}$ (5)

Recall that the area of node $i$ is the number of nodes upstream of $i$, plus
$1$ for $i$ itself. So for a given $k$, $\sum_{i\in C_{k}}A_{i}^{\gamma}$ will
have to include the number of nodes in $C_{k}$ and the total number of nodes
upstream of all $i\in C_{k}$, which must include all the nodes
$j\in\bigcup_{l>k}C_{l}$, since their paths to the outlet must pass through
stripe $C_{k}$ at some point. $\bigcup_{l>k}C_{l}$ is simply the set of all
the nodes in the grid minus those within the $k$x$k$ section enclosed by
$C_{k}$, which is $n^{2}-k^{2}$ nodes. Thus the total amount of area being
passed through $C_{k}$ is at least

$|C_{k}|+n^{2}-k^{2}$ (6)

Then we have

$H_{1}(s)\>=\>\sum_{k=2}^{n}\sum_{i\in
C_{k}}A_{i}\>\geq\>\sum_{k=2}^{n}(2k-1+n^{2}-k^{2})$

The rightmost sum simplifies to $\frac{1}{6}(4n^{3}-3n^{2}-n)$; therefore this
is a lower bound on $H_{1}(s)$.

Consider the network $t$ where every link from node $i$ to node $j$ is such
that if $i\in C_{k}$ then $j\in C_{k-1}$. Here, quantity 6 is exactly the area
passing through stripe $C_{k}$, so $H_{1}(t)=\frac{1}{6}(4n^{3}-3n^{2}-n)$.
Hence the lower bound is achievable.

∎

######  Theorem 3.

For an $n\times n$ eight-neighbor grid, $\frac{3}{2}n^{2}-\frac{7}{2}n+1$ is a
lower bound on $H_{0.5}(s)$.

###### Proof.

Following the same reasoning as above, we have that

$H_{\gamma}(s)=\sum_{k=2}^{n}\sum_{i\in C_{k}}A_{i}^{\gamma}$ (7)

and the total amount of area being passed through $C_{k}$ is at least
$|C_{k}|+n^{2}-k^{2}$.

By Lemma 1, the optimal way to distribute this area over the vertices in
$C_{k}$ is to send all the upstream area, $n^{2}-k^{2}$, through one vertex in
$C_{k}$, leaving each of the other vertices in $C_{k}$ with area 1. (Note that
this is not usually feasible, but it is a lower bound.)
Thus for a given $k$,

$\sum_{i\in C_{k}}A_{i}^{\gamma}\geq|C_{k}|-1+(n^{2}-k^{2}+1)^{\gamma}$

Since $f(x)=x^{\gamma}$ is concave,

$\sum_{k=2}^{n}(n^{2}-k^{2}+1)^{\gamma}\>\geq\>\sum_{k=2}^{n}[n^{2\gamma}-(k^{2}-1)^{\gamma}]\>\geq\>n^{2\gamma+1}-n^{2\gamma}-\sum_{k=2}^{n}(k^{2})^{\gamma}$

So

$\sum_{k=2}^{n}\sum_{i\in
C_{k}}A_{i}^{\gamma}\>\geq\>\sum_{k=2}^{n}[2k-2+(n^{2}-k^{2}+1)^{\gamma}]\>\geq\>n^{2}-3n+n^{2\gamma+1}-n^{2\gamma}-\sum_{k=2}^{n}k^{2\gamma}$

For $\gamma=0.5$, this evaluates to
$2n^{2}-4n-(\frac{n^{2}-n}{2}-1)\>=\>\frac{3}{2}n^{2}-\frac{7}{2}n+1$. ∎

###  3.2 Volume Scaling

In [16], Maritan et al. make an analytical prediction for the scaling of
volume with area in rivers. Their analysis depends on the relationship
$\langle L_{x}\rangle\propto A_{x}^{h}$, where $\langle L_{x}\rangle$ is the
mean distance from vertices upstream of $x$ to $x$, and $h$ is Hack’s
exponent, from Hack’s law (a power-law relationship between basin length and
area) [11]. This is combined with the equation $V_{x}=A_{x}\langle
L_{x}\rangle$ to arrive at the relationship $V_{x}\propto A_{x}^{1+h}$. This
relationship is verified by their data on real river networks as well as OCNs,
where (for both of which) $h$ is typically close to $0.57$ [16].

If $h$ were to equal exactly $0.5$, this would imply isometric scaling of
length and area in river basins, as $A_{x}$ would scale directly with
$l_{x}^{2}$, and shape would be preserved. This would line up with the
prediction in [3] that $V\propto A_{x}^{{D+1}/D}$ in the most efficient
networks for $D=2$. However, since river basins tend to elongate with growth,
getting proportionally narrower as they get larger, $h$ is usually slightly
greater than $0.5$, and the lower bound predicted in [3] is rarely reached.

Shifting focus to three dimensions, we can look for evidence of a
corresponding Hack’s law for three dimensional OCNs (that is, evidence that
area scales with length to some constant power). If there is a relatively
constant scaling exponent $h$, the analysis in [16] can be extended to three
dimensions, since the steps taken there do not otherwise depend on dimension.
Thus, we might expect to see $V_{x}\propto A_{x}^{1+h}$ for some $h$;
according to the analysis in [3], $V_{x}$ should scale at least as
$A_{x}^{4/3}$, so we might expect $1/3$ to be a lower bound for $h$, with $h$
slightly greater than $1/3$ if three dimensional OCNs elongate in a similar
way to two dimensional ones. These predictions are borne out in the simulation
results that follow.

##  4 Experimental Results

###  4.1 Energy Scaling

Figure 7: Log-log plot of area vs. energy for 2-dimensional OCNs, showing both
analytical lower bound (lower, blue) and observed values (upper, red).

Fig. 7 shows how empirically observed minimum possible energy scales with area
in two-dimensional OCNs. The estimated line of best fit is shown, as well as
the analytical lower bound derived in Section 3. The observed values of energy
follow a power law with a small exponent, while the lower bound is essentially
linear with respect to area.

###  4.2 Length Scaling

Scaling exponents $h$ where $l\propto A^{h}$ in two and three dimensions is
shown in Table 1. The observed values of the exponents for two dimensions are
within the bounds found in other studies [11, 16]. For three dimensions, the
exponent is also fairly consistent, though less so than in two dimensions. It
also deviates slightly more from the isometric value of 1/3 than the two
dimensional version does from 1/2. The fact that it is higher than 1/3 fulfils
the hypothesis that three-dimensional basins elongate like two-dimensional
ones.

basins analyzed | $h$
---|---
2d whole basins | 0.6066895125
2d all subbasins | 0.5808520176
3d whole basins | 0.3645961454
3d all subbasins | 0.4230582779
Table 1: Length scaling exponents

###  4.3 Volume Scaling

Fig. 8 shows the scaling of volume with area in two-dimensional OCNs, for
whole networks and for all subbasins. Note that the exponents are very
similar, indicating that the scaling behavior is the same within basins as
across different sizes of basins. The exponents are both close to 1.57, as in
[16].

(a)

(b)

Figure 8: Volume plotted with area for whole nxn basins (8(a)) and all
subbasins (8(b)) of 2-dimensional OCNs.

(a) Whole nxn basins

(b) all subbasins

(c) subbasins of 10x10x10 OCNs

(d) all subbasins with Area $\leq$ 1000

Figure 9: Volume plotted with area for 3-dimensional OCNs. basins analyzed | $\alpha$
---|---
whole networks | 1.386
all subbasins | 1.424
all subbasins of 20x20x20 network | 1.437
subbasins with area $>$ 1000 | 1.3776
subbasins of 20x20x20 network with area $>$ 1000 | 1.342
all subbasins with area $\leq$ 1000 | 1.44456
subbasins of 20x20x20 network with area $\leq$ 100 | 1.457
subbasins of 10x10x10 network | 1.4506
Table 2: Volume scaling exponents for three-dimensional OCNs

The three-dimensional results for volume scaling are displayed in Fig. 9 and
summarized in Table 2. The differences in exponents between the different data
sets show higher scaling behavior in the sets of smaller basins; the
difference between the exponent for whole basins (9(a)) and all subbasins
(9(b)) is due to the greater concentration of smaller basins in the set of all
subbasins, skewing the slope. Note that the exponents in 9(c) and 9(d) are
similar, showing that scaling behavior in the subbasins is the same for the
same distributions of area independent of the size of the encompassing whole
basin. In Section 3 we predicted that $\alpha$ would equal $1+h$, using the
analysis in [16], and this relationship is clear in Tables 1 and 2.

The exponent $\alpha$ ranges from $\approx$1.34 to $\approx$1.46, with a
higher exponent for collections of smaller basins. These results are not
inconsistent with the data for metabolic allometry in biological organisms,
where a power-law fit to data from a wide range of sizes approximates that
metabolic rate scales with mass to the power of 0.70 ($1/\alpha$) [25]. Not
only is this value within the range found in the OCNs, but in organisms as
well it is found that sets of smaller organisms yield a higher exponent than
sets of larger ones [14, 24].

##  5 Alternative Models

###  5.1 Steiner Tree Model

In addition to studying OCNs, we took a preliminary look at comparing OCNs
with Steiner trees.

Steiner trees are minimum-weight trees that connect a given subset of nodes in
a graph. The specified nodes are called terminals. Steiner trees may include
non-terminal nodes; these are called Steiner points (or Steiner nodes).

In [6], Steiner trees built on a grid are considered. The underlying graph is
all points in a Euclidean plane, completely connected, and the terminals are
the points of a grid. We began comparing Steiner trees with OCNs by looking at
the relative optimality of OCNs minimizing $H_{0.5}(s)$ and normal Steiner
trees on grids of the same sizes.

In order to evaluate the energy of a Steiner tree, the tree needs to be
directed; this can be done by choosing the outlet to be an arbitrary corner
node and directing all the edges towards the outlet.

For the purposes of this study area was defined as the number of terminal
nodes in the subtree rooted at a given node. This way, the terminal nodes have
exactly one unit of area associated with each of them, just as the grid nodes
do in the OCN.

The OCNs here have realistic link lengths, where diagonal links are length
$\sqrt{2}$, to make them comparable to the Steiner trees.

OCNs $s$ of size 2x2, 3x3, 4x4, and 5x5 were constructed and $H_{\gamma}(s)$
for each were compared with $H_{\gamma}(t)$ for Steiner trees $t$ of the same
size. The Steiner trees used were found in [6]. Figure 10 depicts the pairs of
trees that were compared. On the left of each pair is the Steiner tree, with
open circles for the Steiner nodes, and on the right of each is the
corresponding OCN.

(a) 2x2

(b) 3x3

(c) 4x4

(d) 5x5

Figure 10: Steiner trees and OCNs for different nxn grids.

Since Steiner trees minimize total link length, it was clear that they would
always have lowest energy for $\gamma=0$. For larger values of gamma, however,
where area becomes a bigger factor than link length, we hypothesized that the
OCNs would have a lower energy value than the Steiner trees. Finding whether
this was true, and where the crossover point would be, was the goal of the
comparisons.

###  5.2 Analytic Results

(a) 2x2

(b) 3x3

(c) 4x4

(d) 5x5

Figure 11: Plots of $H_{\gamma}(s)$ (blue) and $H_{\gamma}(t)$ (red), where
$s$ is an OCN and $t$ a Steiner tree of the given size. In each plot, the
horizontal axis is $\gamma$ and the vertical axis is energy.

Figure 11 shows plots of the energy for corresponding Steiner trees and OCNs,
$0\leq\gamma\leq 1$. As expected, the Steiner trees have lower energy than the
OCNs for smaller $\gamma$, while for $\gamma$ past a certain crossover point
the OCNs are better. Table 3 lists the crossover values of $\gamma$ for each
size.

size | crossover $\gamma$
---|---
2x2 | 0.55433153188825812933
3x3 | 0.63036154802337965422
4x4 | 0.01907039679465522977
5x5 | 0.32264708810531986705
Table 3: Crossover values of $\gamma$

###  5.3 Interpretation

From the sizes studied, it is not possible to detect a trend in crossover
points.

The next step would be to combine the two models, constructing Steiner-type
trees that minimize $H_{\gamma}(s)$ for varying $\gamma$ and comparing them
with real river networks and with normal OCNs.

##  6 Conclusion

We have looked at three dimensional OCNs as they compare with metabolite
distribution networks in organisms. In the organism context, volume is
interpreted as volume of blood (which is directly proportional to the mass or
volume of an organism) and area is proportional to the number of capillaries
[25]. In this context, the grid used to create OCNs no longer represents fixed
space (as it does in the two-dimensional/river context) and the amount of
physical area directly associated with each node may not be the same over
different body masses. This would only have a linear effect on the
relationship between area and mass, however, so this has no effect on the
scaling exponent.

Though the three-dimensional networks do not actually look like the metabolic
networks in organisms, we have shown that they have similar area/volume
scaling behavior. This adds credence to the idea that the observed metabolic
scaling is a result of characteristics of the distribution network.

Another way to study the possible similarities between OCNs and metabolic
networks would be to derive an energy functional for three dimensional OCNs
from metabolic networks themselves, rather than using the one derived from
rivers. This could also include consideration of heterogeneity. Heterogeneity
in the river context is addressed in [23] and [8]; possibly this work could be
extended to three dimensions.

##  7 Acknowledgments

The first author was supported by a Graduate Fellowship from Rensselaer
Polytechnic Institute during the completion of this work.

## References

  * [1] Paul S. Agutter and Jack A. Tuszynski.  Analytic theories of allometric scaling.  The Journal of Experimental Biology, 214(7):1055–1062, April 2011\.
  * [2] Jayanth R. Banavar, John Damuth, Amos Maritan, and Andrea Rinaldo.  Supply-demand balance and metabolic scaling.  Proceedings of the National Academy of Sciences, 99(16):10506–10509, August 2002.
  * [3] Jayanth R. Banavar, Amos Maritan, and Andrea Rinaldo.  Size and form in efficient transportation networks.  Nature, 399(6732):130–132, May 1999.
  * [4] Jayanth R. Banavar, Melanie E. Moses, James H. Brown, John Damuth, Andrea Rinaldo, Richard M. Sibly, and Amos Maritan.  A general basis for quarter-power scaling in animals.  Proceedings of the National Academy of Sciences, 107(36):15816–15820, September 2010.
  * [5] James H. Brown, James F. Gillooly, Andrew P. Allen, Van M. Savage, and Geoffrey B. West.  Toward a Metabolic Theory of Ecology.  Ecology, 85(7):1771–1789, 2004.
  * [6] Fan Chung, Martin Gardner, and Ron Graham.  Steiner Trees on a Checkerboard.  Mathematics Magazine, 62:83–96, 1989.
  * [7] Marek Cieplak, Achille Giacometti, Amos Maritan, Andrea Rinaldo, Ignacio Rodriguez-Iturbe, and Jayanth R. Banavar6.  Models of Fractal River Basins.  Journal of Statistical Physics, 91, 1998.
  * [8] F. Colaiori, A. Flammini, A. Maritan, and Jayanth R. Banavar.  Analytical and numerical study of optimal channel networks.  Physical Review E, 55(2):1298+, February 1997.
  * [9] Dodds, Rothman, and Weitz.  Re-examination of the “3/4-law” of Metabolism.  Journal of Theoretical Biology, 209(1):9–27, March 2001.
  * [10] Peter S. Dodds.  Optimal Form of Branching Supply and Collection Networks.  Physical Review Letters, 104(4):048702+, January 2010.
  * [11] J. T. Hack.  Studies of longitudinal profiles in Virginia and Maryland.  U.S. Geological Survey Professional Paper, 294-B:45–97, 1957.
  * [12] Nick J. Isaac and Chris Carbone.  Why are metabolic scaling exponents so controversial? Quantifying variance and testing hypotheses.  Ecology letters, 13(6):728–735, June 2010.
  * [13] Max Kleiber.  Body size and metabolism.  Hilgardia, 6:315–351, January 1932.
  * [14] Tom Kolokotrones, Van Savage, Eric J. Deeds, and Walter Fontana.  Curvature in metabolic scaling.  Nature, 464(7289):753–756, April 2010.
  * [15] Angel Lopez-Urrutia, Elena San Martin, Roger P. Harris, and Xabier Irigoien.  Scaling the metabolic balance of the oceans.  Proceedings of the National Academy of Sciences, 103(23):8739–8744, June 2006.
  * [16] A. Maritan, R. Rigon, J. R. Banavar, and A. Rinaldo.  Network allometry.  Geophysical Research Letters, 29(11):1508+, June 2002.
  * [17] Peter Molnár and Jorge A. Ramírez.  An analysis of energy expenditure in Goodwin Creek.  Water Resources Research, 34(7):null+, July 1998.
  * [18] Melanie E. Moses, Stephanie Forrest, Alan L. Davis, Mike A. Lodder, and James H. Brown.  Scaling theory for information networks.  Journal of The Royal Society Interface, 5(29):1469–1480, December 2008.
  * [19] M. Renner, R. Seppelt, and C. Bernhofer.  Evaluation of water-energy balance frameworks to predict the sensitivity of streamflow to climate change.  Hydrology and Earth System Sciences, 16(5):1419–1433, May 2012\.
  * [20] A. Rinaldo, J. R. Banavar, and A. Maritan.  Trees, networks and hydrology.  Water Resources Research, 42, 2006.
  * [21] Andrea Rinaldo, Ignacio RodriguezIturbe, Riccardo Rigon, Rafael L. Bras, Ede Ijjasz-Vasquez, and Alessandro Marani.  Minimum energy and fractal structures of drainage networks.  Water Resources Research, 28(9):null+, 1992.
  * [22] Ignacio Rodriguez-Iturbe, Kelly K. Caylor, and Andrea Rinaldo.  Metabolic principles of river basin organization.  Proceedings of the National Academy of Sciences, 108(29):11751–11755, July 2011.
  * [23] Ignacio Rodriguez-Iturbe and Andrea Rinaldo.  Fractal River Basins: Chance and Self-Organization, chapter 4.  Cambridge University Press, 1997.
  * [24] V. M. Savage, J. F. Gillooly, W. H. Woodruff, G. B. West, A. P. Allen, B. J. Enquist, and J. H. Brown.  The predominance of quarter-power scaling in biology.  Functional Ecology, 18(2):257–282, 2004.
  * [25] Van M. Savage, Eric J. Deeds, and Walter Fontana.  Sizing Up Allometric Scaling Theory.  PLoS Comput Biol, 4(9):e1000171+, September 2008.
  * [26] Geoffrey B. West, James H. Brown, and Brian J. Enquist.  A General Model for the Origin of Allometric Scaling Laws in Biology.  Science, 276(5309):122–126, April 1997.
  * [27] Geoffrey B. West, James H. Brown, and Brian J. Enquist.  The Fourth Dimension of Life: Fractal Geometry and Allometric Scaling of Organisms.  Science, 284(5420):1677–1679, June 1999.
  * [28] Craig R. White, Michael R. Kearney, Philip G. Matthews, Sebastiaan A. Kooijman, and Dustin J. Marshall.  A manipulative test of competing theories for metabolic scaling.  The American naturalist, 178(6):746–754, December 2011.