Description
-
Given N labelled nodes and allowing for all possible number of edges m, what’s the total number of undirected, unweighted networks we can construct?
How does this number scale with N?
-
Given N labelled nodes and a variable number of m edges, for what value of m do we obtain the largest diversity of networks? And for this m, how does the number of networks scale with N?
-
We’ve seen that large random networks have essentially no clustering, meaning that locally, random networks are pure branching networks. Nevertheless, a finite, non-zero number of triangles will be present.
For pure random networks, with connection probability p = k /(N 1), what is the expected total number of triangles as N ! 1?
-
Repeat the preceding calculation for cycles of length 4 and 5 (triangles are cycles of length 3).
5. Show that the second moment of the Poisson distribution is
k2 = k 2 + k :
and hence that the variance is 2 = k .
-
We’ve figured out in class that for large enough N (and k fixed), a random network always has a Poisson degree distribution:
P (k; ) = k e
k!
where = k . And as we’ve discussed, we don’t find these networks in the real world (they don’t arise due to simple mechanisms). Let’s investigate this oddness a little further.
Compute the expected size of the largest degree in an infinite random network given k and as a function of increasing sample size N. In other words, in selecting (with replacement) N degrees from a pure Poisson distribution with mean k , what’s the expected minimum value of the largest degree min kmax?
A good way to compute kmax is to equate it to the value for which we expect 1/N of our random selections to exceed. (We had a question in 300 along these lines for power-law size distributions.)
Hint—Of course we’ll be using Stirling’s Approximation.:
http://www.youtube.com/v/uK5yakuX59M?rel=0
2
