Assignment 5 Solution

Description

1. For each of our main six networks, compute and present distributions of the shortest path length between all pairs of nodes. Notation: d_i;j is the shortest distance between i and j.

Also compute the average shortest path length, d .

2. Generate ensembles of random networks of the same ‘size’ as the six networks. Process 1 random network and then scale up as computing power/time/sanity permits. 1000 random networks would be good.

Size here means having the same number of nodes and the same number of edges. As for the real networks, compute the shortest path lengths for these random networks and present frequency distributions.

3. Determine how well/poorly random networks produce the shortest path distributions of real world networks.

Using whatever tests you like, show how well both the average shortest path length and the full distributions compare between the real network and their random counterparts.

3. (3+3+3)

3. 1. Determine all possible three node motifs for undirected networks and sketch them. (Do not consider motifs for which one or more nodes are disconnected.)

   2. Do the same as above for directed networks, allowing that a pair of nodes may have two edges traveling opposite ways behind them.

3. 3. For our base six networks, use the ensembles of random networks generated in assignment 3, question 2 to test for three node motifs in the manner of [2].

Note: You should be able to process the four smaller networks, and you should feel free to abandon the larger ones if your computing friend explodes.

5. For a uniformly distributed population, to minimize the average distance between individuals and their nearest facility, we’ve made a claim that facilities would be placed at the centres of the tiles on a hexagonal lattice (or the vertices of a triangular lattice). Why is this?

5. In two dimensions, the size-density law for distributed source density D(⃗x) given a sink density (⃗x) states that D / ^2/3. We showed in class that an approximate argument that minimizes the average distance between sinks and nearest sources gives the 2/3 exponent ([1]; also see Supply Networks lecture notes).

Repeat this argument for the d-dimensional case and find the general form of the exponent in D / .

5. Following Um et al.’s approach [3], obtain a more general scaling for mixed public-private facilities in two dimensions. Use the cost function:

c_i = n_i r_i with 0 1;

where, respectively, n_i and r_i are population and the average ‘source to sink’ distance for the population of the ith Voronoi cell (which surrounds the ith facility).

Note that = 0 corresponds to purely commercial facilities, and = 1 to strongly social ones.

References

1. M. T. Gastner and M. E. J. Newman. Optimal design of spatial distribution networks. Phys. Rev. E, 74:016117, 2006. pdf

2. S. S. Shen-Orr, R. Milo, S. Mangan, and U. Alon. Network motifs in the transcriptional regulation network of Escherichia coli. Nature Genetics, 31:64–68, 2002. pdf

3. J. Um, S.-W. Son, S.-I. Lee, H. Jeong, and B. J. Kim. Scaling laws between population and facility densities. Proc. Natl. Acad. Sci., 106:14236–14240, 2009. pdf

3