Assignment 3 Solution

Okay, let’s get back to the 6 networks we explored in the first assignment. Questions 2 through 4 will focus on them.



Measure the degree-degree assortativity. This is the standard Pearson correlation coefficient and the focus is on links, and then the nodes at the end of each link. For undirected networks, we need to think about how we choose the ordering of an edge’s two degrees when we perform the correlation. Which degree goes first? Or should we include both orderings? How about randomly choosing the ordering? Does it matter?




For directed networks, various correlations are possible (in-in, in-out, etc.). For this question, measure the correlation of the in-degree of the source node and the out-degree of the destination node for each link.




1


and becomes still broader as
! 1 , in which limit the












min
homo
1 by definition; for ! 0, Jmin=Jhomo ! 0, because t
number of iteration steps diverges as the minima becomes
vanishing
kl allow the remaining
kl ! 1.


less and less steep.










Figure 3(b) shows the behavior of minimal dissipati


1 presents a marginal case. The results of the
rate close to


1. For
smaller than 1, the relaxati
simulation suggest that the minimum is highly degenerate;
method only furnishes a local minimum, the Monte Ca
i.e., there are a large number of conductivity distributions
algorithm searching for the optimal tree topologies gi


2. Produce plots of the adjacency matrices.
lower dissipation values. The different values correspon
yielding the same minimal dissipation.




For
< 1, the output of
the
relaxation algorithm is
ing to different realization indicate
that the employ


3. Using a network visualization tool of your choice, produce plots of the networks (if




qualitatively different [Fig. 2(b)]. A large number of con-
Monte Carlo method does not find the exact global m


possible, depending on size).




ima. For


1,
the optimal
tree
obtained
by t
ductivities converge to zero so that no loop remains. The


highly redundant network is
transformed to
spanning
Monte Carlo algorithm is not the optimal solution sin


For the smaller one , please label the
odes numerically.














tree topology and the currents are canalized in a hierarch-
the absolute and only minima has loops. The dissipati
ical manner. This, too, is predicted
y the
results
rate which results from the
relaxation algorithm is then,


4. For river networks,
basin areanalyticalsaredistributed according to
P (a) / a .








[6]. In
contrast to
1, the conductivity
distribution
course, lower than the dissipation of any tree. While t
cannot
Determine the exponent in terms of the Horton ratios
R
and
Rs.




1 shows a cl
be interpreted
as a discrete approximation
of a
curve is continuous, the crossover at
conductivity tensor:FollowfortheNsamedia! procedure1,thestructureshownbecomesinlectures forchangeP(ℓ) in ℓthe
.slope of Jmin . One could interpret t


/




fractal.




behavior as a second order phase transition. (The change
5. (3 + 3 + 3) Reproduce Bohn and Magnasco’s Figs. 2a and 2b in [1]:
(a)
(b)


(c)




































FIG. 2. Examples of the optimized conductivity distributions obtained by the relaxation method for (a) 2:0 and (b) 0:5.

Steps are given below but please read through the paper to understand how they

< 1, the relaxation leads in general only to a local minimum. The global minimum can be approached by searching in the space tree topologies. Theset thingsresultforup. 0:5 is shown in (c). The arrows indicate the localized inlet.




The full team is encouraged to work together088702on-3 Slack.




(3) Construct an adjacency matrix A representing the hexagonal lattice used in [1]. Plot this adjacency matrix.



(3 + 3) Run a minimization procedure to construct Figs. 2a and 2b which



correspond to = 2 and = 1/2. Steps:




i. Set each link’s length to unity (the dkl). The goal then reduces to

minimizing the cost
∑




C =jIklj


k;l



where Ikl is the current on link kl and = 2 /( + 1).




place a current source of nominal size i0 at one node.



All other nodes are sinks, drawing a current of



ik =
i0
:


Nnodes 1










2



Suggest setting i0 = 1000 (arbitrary but useful value given the size of the network).
Generate an initial set of random conductances for each link, the f klg. These must sum to some global constraint as
∑

K = kl:




k;l




Note: There seems to be no reason not to set K = 1 but the power of




is a bit of a worry. (Also: we now have a lot of k types on deck.)




Solve the following to determine the potential U at each node, and hence the current on each link using:
∑

ik = kl(Uk Ul);




l




and then




Ikl = kl(Ul Uk):




Note: the paper erroneously has Ikl = Rkl(Ul Uk) below equation 4; there are a few other instances of similar miswritings of Rkl instead of

kl.




Now, use scaling in equation (10) to compute a new set of f klg from the Ikl. Everything boils down to



kl / jIklj ( 2);




where the constant of proportionality is determined by again making

sure K = ∑k;l kl:




Bonus: Please see reference 1 in [1] for a random connection to the next assignment’s code name.




Some help—Let’s sort out the key equation:




∑

ik = kl(Uk Ul):




l




Each time we loop around through this equation, we know the ik and the kl and

must determine the . In matrixology, we love A ⃗ problems so let’s see if we

Uk ⃗x = b

can fashion one: ∑

ik = kl(Uk Ul)




l

∑ ∑

= klUk klUl

l l




3
∑ ∑

= Uk kl KklUl

l l

⃗
kUk [ U ]k



where we have set k = ∑l kl; the sum of the kth row of the matrix K. We now construct a diagonal matrix with the k on the diagonal, and obtain:

⃗
⃗


i = (
K) U:


⃗
⃗
using standard features of
The above is in the form A x = b so we can solve for U
R, Matlab, Python, …(hopefully).







References




S. Bohn and M. O. Magnasco. Structure, scaling, and phase transition in the optimal transport network. Phys. Rev. Lett., 98:088702, 2007. pdf





















































































































4