CN4 Small-world networks

Aims

• learn what is the small-world network: small diameter and large clustering coefficient.
• learn how to generate such a network.

Questions

• show that the diameter of Erdos-Renyi networks scales logarithmically with the network size.

  • see below.

• what is the expected clustering coefficient for $G(n,p)$ microstates?

  • $p$

• what clustering coefficient do you expect in the limit of infinite, sparse random networks?

  • 0

• what degree assortativity $r$ do you expect for $G(n,p)$ microstates?

  • 0

• describe the construction mechanism of a Watts-Strogatz network.

  • build a regular lattice m networks first
  • (no) for each node, randomly choose $p$ portion edges and rewire them to randomly selected other neighbours.
  • for each edge, rewire the source of it with the probability $p$ to a random node.

• show that the clustering coefficient in a ring lattice where s nearest neighbors are connected is $C=\frac{3s-3}{4s-2}$

  • see below

• which links represent weak ties in a Watts-Strogatz network?

  • the rewired ties to “far” nodes.

• write down an algorithmic formulation of the Molloy-Reed model, generating networks with a fixed degree distribution.

• Under what circumstances are random networks with a fixed degree sequence better “null models” than the Erdos-Renyi model?

  • see below

Keywords

• Erdos-Renyi network

Erdos-Renyi Network

The expected statistical index of ER model.

We have already know,

• the number of nodes $n$,
• the number of edges $\frac{n^2p}{2}$ (or others) or m
• the mean degree $np$
• the variance of edges $np(1-p)$

Clustering coefficient

In $G(n,p)$​ model, since links are independent,
$$
P[(j,k)\in E|(i,j)\in E,(i,j)\in E]=P[(j,k)\in E]=p=C
$$

Diameter

The idea is starting from an arbitrary node, how many expected steps will this node reach other nodes?

Suppose each node has $k$ neighbors, in $l$ steps, it will approximately reach $k+k^2+\cdots k^l$ nodes, totally $\frac{k^{l+1}-1}{k-1}\sim k^l$ nodes (including himself). When $k^l$ equals to $N$ , the total number of nodes, $l\sim\frac{\log N}{\log k}$

Small-world network

Stylised fact

• small diameters
• high clustering coefficient
• navigable: people are able to choose the “shortest” path that generate the small diameter, even without global knowledge.
  • how to do that?
  • Estimate the number of the shortest path through the certain person, and choose one with the highest number.

Strong / weak ties

• strong: within clusters/groups

• weak: “bridge” clusters/groups

  It is weak ties that makes social network navigable.

Detection

We can judge if a network is a small-world network by randomly generating networks and compare their diameter and clustering coefficient.

Watts-Strogatz Model

Idea

Randomly rewire links in ring lattice network of size $n$.

Parameters

• $d$: dimensionality (no deep study)
• $s$: the distance of the farthest neighbor
• $p$: the rewiring probability

Algorithm

1. start with regular lattice of dimension $d$ , ring lattice: $d = 1$​
2. connect nodes at lattice distance up to $s$, example: $s = 5$​
3. rewire source of each link to random node with probability $p$

Ring lattice

Clustering coefficient

Assume each node maintains a window with width of $2s+1$ . For each node, it has $2s$ neighbors. For the node with the distance $t,t<s$, its window overlaps with the original node with the size of $2s+1-t$. Among these $2s+1-t$ nodes, one is the original node and the other is the center of the new window. So, totally the new node is linked to $2s-1-t$ to the old node’s neighbors.

The clustering coefficient is the number of appearance links $\sum_i\text{overlap}i$​ divided by the total number of possible links $\frac{2s(2s-1)}{2}$ .
$$
C=\frac{2[\sum{i=1}^s(2s-i-1)]/2}{(2s-1)2s/2}=\frac{3s-3}{4s-2}
$$

Diameter

Assume a circle, in one step, a node can reach to the node with $s$ distance from it farthest. The farthest node has $\frac{n}{2}$ steps from it. It totally costs $\frac{n}{2s}$ steps.

Therefore, $D\sim \frac{n}{2s}$

Degree distribution

all the nodes have the same degree.

Clustering coefficient

$\frac{C_p}{C_0}$​ drops slowly first and then rapidly

Diameter

$\frac{l_p}{l_0}$​ drops rapidly first and then slowly.

Small world regime

A range of $p$, where $\frac{l_p}{l_0}\ll 1$and $\frac{C_p}{C_0}\gg 0$

Fix degree sequence network

We study degree sequence because we can

• analytically study expected properties of networks.
  • first of all, the degrees of nodes are one frequent source of heterogeneity in complex systems. We often want to incorporate heterogeneity into our model instead of assuming all the nodes are equal.
  • Secondly, the degree sequence allows us to study expected properties of networks beyond simple random models.
• understand which of a system’s properties are due to the level of connectivity of nodes rather than due to the actual topology of these connections.

Molloy-Reed model

1. create empty network with n nodes
2. for each node $i$ generate $d_i$ “link stubs”
3. draw pairs of link stubs uniformly at random and connect them until no stubs are left.

Difference with degree distribution

Given the degree sequence, the number of edges is given.

But given the degree distribution, e.g. Poisson degree distribution, the number of edges is still flexible, but the expectation is fixed.

Poisson Degree Distribution

$$
p(k)=\frac{\lambda^ke^{-\lambda}}{k!}
$$

• $\lambda$ is the mean degree
• it describes the degree distribution of sparse random networks
• for large $n$, it is equivalent to statistical ensemble generated by $G(n,p)$ model with $np=\lambda$

Zipf degree distribution

$$
p(k)=k^{-\gamma}\cdot \zeta(\gamma)^{-1}
$$

• power law with $\gamma\geq 2$
• it describes for a broad degree distribution, to imitate scale-free networks.