## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# Exploring network scaling through variations on optimal channel networks

Edited* by Andrea Rinaldo, Ecole Polytechnique Federale Lausanne, Lausanne, Switzerland, and approved October 15, 2013 (received for review July 31, 2013)

## Significance

Optimal Channel Networks (OCNs) model the drainage of a river basin through river channels, minimizing the energy expended in draining the basin. At local optima of this energy functional, OCNs accurately model many characteristics of real river networks, and thus are useful in studying river processes such as channel evolution and flooding. Efficient transportation networks have been studied more generally, with application to blood or metabolite distribution networks in organisms as well as to rivers. We extend the OCN model to three dimensions, toward a goal of a better understanding of efficient transportation networks. We focus on the scaling behaviors of several properties, and find that three-dimensional OCNs exhibit predictable scaling behavior similar to that of metabolite distribution networks.

## 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 2D 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. We find that the 3D OCN has predictable characteristics analogous to those of the 2D version, as well as scaling properties similar to metabolic networks in biological organisms.

Fractal properties of networks have been widely studied to better understand observed network behaviors. Some of the properties commonly used in the study of fractal networks are scaling laws, which describe how different properties relate to each other over varied resolutions. In this paper, we study allometric scaling laws relating to properties defined for tree networks such as lengths, areas, volumes, and energy. 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 (*B*) and body mass (*M*) in organisms, across and within species: . An analogous relationship between contributing area (*A*) and water mass (*C*) in river networks has also been observed: .

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 (1). The areas this relationship finds application in include models of climate change effects in rivers (2) and oceans (3), analyses of river stability (4), and in studies of information networks (5). 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 (6). The physical geometry of the network is important to the development of their result. The authors claimed the model is applicable even to organisms without a physical blood vessel network because they can be treated as having a virtual distribution network (7).

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 (8, 9). Some authors claim that an exponent of 2/3 fits the data better (10, 11), and others assert that no universal scaling law exists at all (12). Much work has been done in modifying the WBE model to reconcile it with the data, with mixed results (12⇓⇓–15).

Banavar et al. proposed a general model for any efficient transportation network, predicting (at most) where *D* is the dimension of the network (i.e., for organism metabolism and for river networks) (16). Thus, they predict that if the network were as efficient as possible, organism metabolism should scale as , 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 (17).

Isaac et al. propose a less strict understanding of the 3/4-power law: although the 3/4 exponent might not be a consistent universal constant, it is still an observable trend. If there is not a single unifying principle explaining why it appears, there still may be multiple reasons why it is worth studying (18).

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: . This is consistent with the general resource transportation model of Banavar et al. (16) for systems in two dimensions, and also with the virtual network model of Dodds (11).

Rinaldo et al. (19) and Rinaldo and coworkers (20) devised a model of river networks called optimal channel networks (OCNs). 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 related to an erosion model and is based on observed characteristics of river basins (21, 22). Statistical properties of locally optimized optimal channel networks (including metabolic allometry) correspond very well with observed properties of real river networks (23, 24).

This paper explores a 3D version of OCNs, using simulations to compare characteristics of 3D OCNs with 2D OCNs and with organic metabolic networks, and to 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 (18).

## Optimal Channel Networks

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 iff *x* is on the path from *y* to the root. If , 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 of 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*, , is the total number of nodes whose paths to the outlet include *x*; that is, the number of nodes *y* such that . This is equivalent to the sum of the areas of each node directly linked to *x* plus one for *x* itself:where y ranges over the nodes directly linked to *x* (19).

The volume of node *x*, , is the sum of all of the areas of all nodes upstream of *x* (16):Eq. **2** can be transformed into a recursive definition for volume: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 (25). Another common definition for upstream length is the distance (counted in number of links) from a node *x* to the farthest away upstream source; these two definitions are statistically equivalent (26).

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 . Energy is a function of the link lengths and areas of all of the links. The energy of a given tree configuration *s* is given by:with . A tree network that achieves the minimum over all possible tree configurations on a given grid is an optimal channel network (19).

Rinaldo et al. (19) and Rinaldo and coworkers (20) derived a gamma value of 1/2 from estimations of physical properties of rivers, and hypothesized that natural rivers would minimize . A remarkable result of refs. 19 and 20 is that although the global optima of OCNs do not match well statistically with real river networks (27), the local optima are an excellent match. The idea that nature tends toward a local optimum makes sense, so this suggests that OCNs are a good model for what actually happens in a river (21). Further supporting this is the result described in ref. 22 that locally optimal OCNs are stable solutions for a landscape evolution dynamical system.

When and all links are of unit length, the energy is equivalent to the volume. When , 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 2D lattice with additional links between diagonally adjacent pairs of nodes (Fig. 1*A*). For the sake of simplicity, all of the links, diagonal and orthogonal, are here considered to have unit length, because it has been shown (21) that the properties with which this paper is concerned are independent of whether the diagonal links are given realistic length or not.

In this study we also analyzed a 3D version of optimal channel networks, built on a 3D grid (Fig. 1*B*). We used the same energy functional as that derived for 2D OCNs: . Because our 3D version is not designed to model a real system, this energy functional has no practical meaning in the 3D case, unlike in the original OCN model where it is based on landscape erosion processes. We used the same functional, however, for two reasons. The first is that it allows our model to contain the original OCN model as the special case when the length along one dimension is 1. The other is that part of our goal was to explore the possibility of an OCN-like model reproducing the scaling behavior of metabolic networks, and thus any similar model is interesting to look at if it produces the hypothesized results.

Fig. 2*A* shows a random tree on a 60 × 60 grid and Fig. 2*B* shows the result of optimizing the energy of the tree with a local search algorithm. To make the structure of the network clearer, links are drawn with a thickness proportional to the log of their area. Fig. 3 depicts a 3D OCN on a 3 × 3 × 3 grid.

## Analytical Results

### Energy Bounds.

In ref. 28, 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 (see *Theorem 2*) is that for an *n* × *n* eight-way grid, is a lower bound on .

**Lemma 1.** *Let* (*P*) *be the optimization problem**where n is the number of entries in the vector A, m is some natural number, and* .

*Then* *is an optimal solution to* (*P*).

** Proof:** Suppose

*A*is an optimal solution for (

*P*) and ∃

*j*s. t..

By a pigeonhole argument, .

Construct such that

Then

Because when is concave, and , . So . Thus, must be an optimal solution for (*P*). By an iteration of this argument, there must be an optimal solution with all entries except for one equal to 1. Without loss of generality, the entries can be rearranged so that is the largest (only nonunit) entry.

**Theorem 1.** *For an n × n eight-neighbor grid G, the optimal* *is* .

** Proof:** Consider the subsets of vertices where vertex iff the distance from

*i*to the outlet equals

*k*− 1 (Fig. 4). In an

*n*×

*n*eight-way grid there are

*n*such stripes. Assuming the outlet is located in a corner, . Clearly,

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*, will have to include the number of nodes in and the total number of nodes upstream of all , which must include all of the nodes , because their paths to the outlet must pass through stripe at some point. Here, is simply the set of all of the nodes in the grid minus those within the *k* × *k* section enclosed by , which is nodes. Thus, the total amount of area being passed through is at leastThen we haveThe rightmost sum simplifies to ; therefore, this is a lower bound on .

Consider the network *t* where every link from node *i* to node *j* is such that if , then . Here, quantity 6 is exactly the area passing through stripe , so . Hence the lower bound is achievable.

**Theorem 2.** *For an n × n eight-neighbor grid,* *is a lower bound on* .

** Proof:** Following the same reasoning as above, we have thatand the total amount of area being passed through is at least .

By *Lemma 1*, the optimal way to distribute this area over the vertices in is to send all of the upstream area, , through one vertex in , leaving each of the other vertices in with area 1. (Note that this is not usually feasible, but it is a lower bound.)

Thus, for a given *k*,Because is concave,SoFor , this evaluates to .

### Volume Scaling.

In ref. 23, Maritan et al. make an analytical prediction for the scaling of volume with area in rivers. Their analysis depends on the relationship , where 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) (29). This is combined with the equation to arrive at the relationship . 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 (23).

If *h* were to equal exactly 0.5, this would imply isometric scaling of length and area in river basins, as would scale directly with , and shape would be preserved. This would line up with the prediction in ref. 16 that in the most efficient networks for . However, because 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 ref. 16 is rarely reached.

Shifting focus to three dimensions, we can look for evidence of a corresponding Hack’s law for 3D 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 ref. 23 can be extended to three dimensions, because the steps taken there do not otherwise depend on dimension. Thus, we might expect to see for some *h*; according to the analysis in ref. 16, should scale at least as , so we might expect 1/3 to be a lower bound for *h*, with *h* slightly greater than 1/3 if 3D OCNs elongate in a similar way to 2D ones. These predictions are borne out in the simulation results that follow.

## Experimental Results

### Energy Scaling.

Fig. 5 shows how empirically observed minimum possible energy scales with area in 2D OCNs. The lower bound derived earlier is also shown, along with estimated curves of best fit for both. The observed values of energy follow a power law with a small exponent, and the lower bound is essentially linear with respect to area for larger values of area. Note that because the plot is logarithmic, the gap between the estimated and observed values for higher areas is much bigger than it appears. Also, the empirical energy values were found by using a local search algorithm, and thus represent local optima rather than global optima.

### Length Scaling.

Scaling exponents *h* where in two and three dimensions are shown in Table 1. The observed values of the exponents for two dimensions are within the bounds found in other studies (23, 29). For three dimensions, the exponent is also fairly consistent, although less so than in two dimensions. It also deviates slightly more from the isometric value of 1/3 than the 2D version does from 1/2. The fact that it is higher than 1/3 fulfills the hypothesis that 3D basins elongate like 2D ones.

### Volume Scaling.

Fig. 6 shows the scaling of volume with area in 2D 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 ref. 23.

The 3D results for volume scaling are displayed in Fig. 7 and summarized in Table 2. The differences in exponents between the different datasets show higher scaling behavior in the sets of smaller basins; the difference between the exponent for whole basins (Fig. 7*A*) and all subbasins (Fig. 7*B*) is due to the greater concentration of smaller basins in the set of all subbasins, skewing the slope. Note that the exponents for the subbasins of the 10 × 10 × 10 network and for the set of subbasins with area ≤ 1,000 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. Earlier, we used the analysis in ref. 23 to predict that α would equal 1 + *h*, and this relationship is clear in Tables 1 and 2.

The exponent α ranges from ∼1.38 to ∼1.45, 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/α) (13). 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 (12, 30).

In addition to these results, we analyzed the volume scaling of networks optimized with different values of γ. Table 3 shows the results, with separate columns for different ranges of subbasin area. The case shows the least variation across different ranges of subbasins.

## Discussion

We have examined the scaling behavior of networks produced by extending the OCN model to a 3D grid. These networks can be compared 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 (13). In this context, the grid used to create OCNs no longer represents fixed space (as it does in the 2D/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.

We have shown that our 3D OCNs exhibit area/volume-scaling behavior similar to metabolic networks in organisms, despite the fact that our model is in no way derived from real metabolic networks. This adds some support to the idea that general characteristics of efficient resource distribution networks could be sufficient to explain the observed allometric scaling, without reference to specifically biological factors.

We noted earlier that our energy functional has no practical meaning in three dimensions, as our model is entirely abstract. A possible direction to further study the potential of an OCN-like model could be to derive an energy functional for 3D OCNs from metabolic networks themselves. This could also include consideration of heterogeneity, which was addressed in the river context in refs. 21, 27, and 28; possibly this work could be extended to three dimensions.

## Materials and Methods

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. The random tree was then optimized using a local search algorithm, as in refs. 19 and 20. 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). A range of grid sizes were analyzed. Two-dimensional *n* × *n* grids with *n* = 10, 20, 30, 40, 50, 60, 70, and 80, and 3D *n* × *n* × *n* grids with *n* = 8, 10, 12, 14, 16, 18, and 20 were used. For the smaller 2D grids, data were averaged from at least four realizations of each size, and for the 3D and larger 2D grids at least three realizations were used for each.

## Acknowledgments

The authors thank two anonymous reviewers for their helpful comments and James Hampton for help editing the manuscript. L.A.B. was supported by a graduate fellowship from Rensselaer Polytechnic Institute during the completion of this work.

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. E-mail: briggl{at}rpi.edu.

Author contributions: L.A.B. and M.K. designed research; L.A.B. performed research; L.A.B. analyzed data; and L.A.B. and M.K. wrote the paper.

The authors declare no conflict of interest.

↵*This Direct Submission article had a prearranged editor.

Data deposition: The data reported in this paper are available at www.cs.rpi.edu/research/groups/pb/Lily-OCN-Data.

## References

- ↵
- Kleiber M

- ↵
- ↵
- López-Urrutia A,
- San Martin E,
- Harris RP,
- Irigoien X

- ↵
- ↵
- Moses ME,
- Forrest S,
- Davis AL,
- Lodder MA,
- Brown JH

- ↵
- West GB,
- Brown JH,
- Enquist BJ

- ↵
- West GB,
- Brown JH,
- Enquist BJ

- ↵
- Agutter PS,
- Tuszynski JA

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- Banavar JR,
- et al.

- ↵
- ↵
- Banavar JR,
- Damuth J,
- Maritan A,
- Rinaldo A

- ↵
- ↵
- ↵
- Rodríguez-Iturbe I,
- Rinaldo A,
- Rigon R,
- Bras RL,
- Ijjasz-Vasquez E

- ↵
- Rodríguez-Iturbe I,
- Rinaldo A

- ↵
- ↵
- ↵
- Rodríguez-Iturbe I,
- Caylor KK,
- Rinaldo A

- ↵
- ↵
- Rinaldo A,
- Banavar JR,
- Maritan A

- ↵
- ↵
- ↵
- Hack JT

- ↵

## Citation Manager Formats

## Sign up for Article Alerts

## Article Classifications

- Physical Sciences
- Environmental Sciences