Network theory - models II.
- 12 minsNetwork models
The Erdős-Rényi model
The Erdős-Rényi model is based on generating a network with N nodes and distributing M links between them evenly or formalised othewrwise, linking the nodes with probability \(p\).
It was already discussed here that a two nodes are linked with probability \(p\) and not linked with probability \(1-p\) therefore resulting in a Binomial degree distribution and in the \(N \rightarrow \infty\) limit in a Poisson degree distribution where \(\langle k \rangle = Np\).
The variance can be calculated as well. It can be tiresome to go through \(\sum_{k = 0}^{N}k^{2} \cdot Binom(k, N)\) which is:
\[\langle k^{2} \rangle ~ = ~ \sum_{k=0}^{N} k^{2}\frac{N!}{(N-k)!k!}p^{k}(1-p)^{N-k}\]For this first see:
\[\langle k \rangle ~ = ~ \sum_{k=0}^{N} k\frac{N!}{(N-k)!k!}p^{k}(1-p)^{N-k} = Np\]Reparametrizing the equation for \(\langle k^{2} \rangle\) :
\[\langle k^{2} \rangle ~ = Np(N-1)p + Np\]Thus the variance is:
\[Var(k) ~ = ~ \langle k^{2} \rangle - \langle k \rangle ^{2} = Np(1-p)\]In the \(N \rightarrow \infty\) limit \(p \rightarrow 0\) while the \(\langle k \rangle\) is constant so therefore the variance becomes negligeble. A large Erdős-Rényi graph is extremely homogenous with no outliers.
Also, all the nodes have approximately the same clustering coefficient so \(C_{i} \approx \langle C \rangle\). It can be interpreted as probability of neighbors \(i\) being connected which corresponds to \(p = \langle C \rangle\).
Giant component in the Erdős-Rényi model:
- Given that the giant component \(S_{1}\) has a relative size \(S = \frac{S_{1}}{N}\) the fraction of the nodes that are not in the giant component is \(u = 1 - S\).
- Taking one node not in the giant component \(i\) we can say about its connection to \(j\) the following:
- not connected to \(i\) directly with probability \((1-p)\)
- not in the giant component with prob. \(u\cdot p\)
- Therefore we found that if \(i\) is not connected to any other point or connected but not in the giant component for \(N-1\) points with probability:
- \((1-p + pu)^{N-1}\) which should correspond to not being in the giant component \(u\)
From this equation we can approximate in the large \(N\) limit that \(\langle k \rangle = 1\) is the critical avarage node degree above which a giant component forms.
Generating function
We have the degree distribution \(p(k)\) and we assume no degree correlation (we are in a random network), we approach the problem from the state where the network can be assumed sparse and local tree-like.
The generating function:
\[G_{X}(z) = \sum_{k=0}^{\infty}z^{k}p_{X}(k)\]Where:
\[p_{X}(k) = \frac{1}{k!}\frac{dG_{X}(z)}{dz^{k}} \Big| _{z=0}\]And the m\(th\) moment is:
\[\langle X^{m} \rangle ~ = ~ \langle k^{m} \rangle ~ = ~ \Big[ z\frac{d}{dz} \Big]^{m} G_{X}(z) \Big| _{z = 1}\]For \(n\) intependent variables \(Z = \sum_{i = 1}^{n}X_{i}\):
\[G_{Z}(x) = \prod_{i=1}^{n}G_{X_{i}}(x)\]\(p(k)\) is the degree distribution function, \(I(k)\) is the distribution function of a randomly chosen node being in component of size \(k\), while \(H(k)\) is the distribution function of a link being connected to a component of size \(k\) on one end.
\(H_{m}(k)\) should denote the probability distribution of randomly chosing \(m\) links which on one end sum up to \(k\) in component size.
The idea behind creating these PDFs a component can be separated in such a way.
- Choosing a node with \(m\) links the probability of the links to sum up to size \(k-1\). The node and its neighbors therefore sum up to \(k\) in size and that distribution is \(I(k)\):
Taking the generating function of both sides:
\[G_{I}(x) ~ = ~ \sum_{k=0}^{\infty}\sum_{m=0}^{\infty}p(m)H_{m}(k-1)x^{k}\]Where:
\[H_{m}(k-1) = \frac{1}{(k-1)!}\frac{d^{k-1}}{dx^{k-1}}G_{H, m}(x) | _{x=0} ~ x^{k}\]Since \(H_{m}(k)\) was chosen that \(m\) links to sum to \(k\) in compoennt size, therefore \(G_{H, m}(x) = [G_{H}(x)]^{m}\), substituting this into \(G_{I}(x)\):
\[G_{I}(x) = \sum_{m=0}^{\infty}p(m)[G_{H}(x)]^{m}x = xG(G_{H}(x))\]Where \(G\) is the degree distribution’s generating function. From this we can get the mean component size in a random graph:
\[\langle S \rangle = G'_{I}(1) = [xG(G_{H}(x))]'|_{x=1} = G(G_{I}(1)) + G'(1)G'_{H}(1)\]Where \(G'(1) ~ = ~ \langle k \rangle\) but and for calculating \(G'_{H}(1)\) we should see:
\[H(k) = \sum_{m=0}^{\infty}q(m)H_{m}(k-1)\]Where \(q(k)\) is the probability distribtuion of a randomly choosen link to be able to proceed to \(k\) direction at one end.
Taking the generating function on both sides and making the same assumptions as before:
\[G_{H}(x) = xG_{q}(G_{H}(x))\]And therefore the derivative can be translated into:
\[G'_{H}(1) = \frac{1}{1 - G'_{q}(x)}\]So we find that the critical point should be at \(G'_{q}(1) = 1\) since:
\[\langle S \rangle ~ = ~ 1 + \langle k \rangle G'_{H}(1) ~ = ~ 1 + \frac{1}{1 - G'_{q}(1)}\]We can actually calculate \(q(k)\) by simply saying that:
\[P(~node~with~degree~~\underline{k}~~link~at~one~end) ~ = ~\frac{kN_{k}}{\sum_{k'}k'N_{k'}} ~ = ~ \frac{kp(k)}{\langle k \rangle }\]There are \(N_{k}\) nodes with \(k\) degrees therefore there are \(N_{k}\cdot k\) links with a \(k\) degree node at one end. \(q(k)\) denotes the probability of a link to have a node at one end with \(k\) other connections so basically the probability of having a node with a \(k+1\) degree node at one end:
\[q(k) ~ = ~ \frac{k+1}{\langle k \rangle }p(k+1)\]And the generating function of this is simple:
\[G_{q}(x) ~ = ~ \sum_{k=0}^{\infty}x^{k}q(k) ~ = ~ \sum_{k=0}^{\infty}x^{k}\frac{k+1}{\langle k \rangle }p(k+1) ~ = ~ \frac{1}{\langle k \rangle }\sum_{l=1}^{\infty}lp(l)x^{l-1} ~ = ~ \frac{G'(x)}{\langle k \rangle }\]We are not done yet, introducing \(q_{m}(k)\) as the probability of choosing \(m\) random links that at one end sum to \(k\) other connections. Therefore the number of second neighbors can be calculated:
\[n_{second}(k) ~ = ~ \sum_{m=0}^{\infty}p(m)q_{m}(x)\]Taking the generating function of both sides:
\[G_{second}(x) ~ = ~ \sum_{k=0}^{\infty}\sum_{m=0}^{\infty}p(m)q_{m}(x)x^{k} ~ = ~ ... ~ = ~ G(G_{q}(x))\]Finally:
\[\langle n_{second} \rangle ~ = ~ G'_{second}(1) ~ = ~ \langle k \rangle G'_{q}(1) ~ \rightarrow ~ G'_{q}(1) ~ = ~ \frac{\langle n_{second} \rangle }{\langle k \rangle }\]After all we arrive at the concluding formula regarding the giant component size:
\[\langle S \rangle ~ = ~ 1 + \frac{\langle k \rangle }{1 - \frac{\langle n_{second} \rangle }{\langle k \rangle }} ~ = ~ 1 + \frac{\langle n_{second} \rangle ^{2}}{\langle k \rangle - \langle n_{second} \rangle }\]Therefore if \(\langle k \rangle ~~ \langle ~~ \langle n_{second} \rangle\) a giant component form, otherwise the system is critical or smaller clusters form only.
It was shown that:
\[\langle n_{second} \rangle ~ = ~ \langle k \rangle G'_{q}(1) ~ = ~ \langle k \rangle \sum_{k=0}^{\infty}kq(k) ~ = ~ ... ~ = ~ \langle k^{2} \rangle - \langle k \rangle\]For scale-free networks \(\langle k^{2} \rangle\) is always divergent therefore they always contain a giant component!
The Erdős-Rényi model does not compare well to real networks, it does not show scale-free behaviour ( no power law degree distibution ), doesn’t have a large clustering coefficient ( \(\langle C \rangle ~ \rightarrow ~ 0\) )and only shows the small-world effect ( small \(\langle l \rangle\) ). It is and important reference system but not more.
The Watts-Strogatz model
It tries to make small-world and local clustering co-exist in a simple random graph by some slight modifications.
The model
Start from a regular ring of nodes in which the first \(q\) neighbors are linked and then rewire each link randomly with probability \(\beta\).
When \(\beta ~ = ~ 0\) for large \(N\):
\[\langle l \rangle ~=~ \frac{N}{4q}\]And:
\[\langle C \rangle ~=~ C = \frac{q(q-1)\frac{1}{3}}{q(2q-1)} ~=~ \frac{3q-3}{4q-2}\]Also when \(\beta ~=~ 0\) we get back the totally random Erdős-Rényi model:
\[\langle l \rangle ~\propto~ logN ~~and~~ \langle C \rangle ~=~ \frac{2q}{N-1}\]There are a range of \(\beta\) values when \(\langle l \rangle\) is relatively low while \(C\) is still very high, meaning high clustering and small wolrd properties.
Takeaway:
It takes a lot of randomness to ruin the clustering, but a very small amount to overcome locality.
Number of random links in the system: \(\beta q N\). What happens when \(\beta q N \langle \langle 1\)? Basically there will be not many random links that can change the graph thus \(\langle l \rangle ~\propto~ N\). In the case when \(\beta q N \rangle \rangle 1\) then the system becomes random and \(\langle l \rangle ~\propto~ lnN\). Approximating the transition at \(\beta_{critical} q N = 1\)!
It can be shown that a scaling function where:
\[l = N \cdot f(N/N_{critical}) \\f(x) = \Big(const. ~ x \langle \langle 1, ~~~ ln(x)/x ~ x \rangle \rangle 1 \Big)\]From numerical studies \(N_{critical} ~\propto~ \beta^{-\tau}\), therefore:
\[l = N\cdot f(\beta^{\tau}N)\]The Barabási-Albert model
The problem was still open until the Barabási-Albert model of how to generate scale-free random graphs in a simple way.
Motivated by real networks the network size is not static, the system grows at each time step.
A new node can be connected random or can be connected to high degree nodes with a larger probability. \(~\rightarrow~\) very logical based on real networks, it is called preferential attachement.
Generating procedure:
Adding one node with m links at a time-step (the initial core should be at least containing m nodes) and choosing node i with probability that is proportional to its degree.
For a large \(t\) timestep:
- \(N ~\propto~ t\) and \(M ~\propto~ mt\)
- the probability of coohsing node \(i\) is:
- with this probability \(m\) new links could be added to node \(i\) therefore the change in its degree can be approximated by:
From which the differential equation:
\[\frac{\partial k_{i}}{\partial t} ~=~ m\frac{k_{i}}{\sum_{j}k_{j}}\]For large \(t\) the sum of the degrees is twice the number of links \(\sum_{j}k_{j} ~=~ 2M ~=~= 2mt\) therefore the differential equation is very simle and can be analitically solved:
\[\frac{\partial k_{i}}{\partial t} ~=~ \frac{k_{i}}{2t} ~~~~~ \rightarrow k_{i}(t) ~=~ C\sqrt{t}\]Given that at timestep \(t_{i}\) the degree of node \(i\) is \(m\) the constant can be eliminated as \(C = m\cdot t_{i}^{-\frac{1}{2}}\).
We want to calculate the degree distibution function and expect it to be scale-free. The probabilit of finding a node with degree at least \(k\) is:
\[P(k) = P(k_{i} \langle k) = P(m t_{i}^{-\frac{1}{2}}\sqrt{t} \langle k) = P\Big(\frac{t}{t_{i}} \langle \Big(\frac{k}{m}\Big)^{2}\Big)\]Where:
\[P(k) = P\Big(\frac{t_{i}}{t} \rangle \Big(\frac{m}{k}\Big)^{2}\Big)\]So the relative length of the time steps \(t_{i}/t\) tells that:
\[P(k) ~=~ 1 - \Big(\frac{m}{k}\Big)^{2}\]From the cumulative distibution function we can get the degree-distribution by simply derivating by \(k\) not considering that the problem is discrete. Therefore:
\[p(k) ~=~ 2m^{2}k^{-3}\]Which is a scale-free distibution with \(\gamma ~=~ 3\).
If links are connected with uniform porbability instead of preferential attachement \(P_{i} = 1/N ~\approx~ 1/t\):
\[\frac{\partial k_{i}}{\partial t} ~=~ mP_{i} = \frac{m}{t} ~~~ \rightarrow ~~ k_{i}(t) = m\cdot ln(t/t_{i}) + m\]Making the same chain of calculations this result in a degree distibution that is not scale free \(p_{k} = (e^{1-k/m})/m\), therefore preferential attachement is truly necessary.
To calculate the clustering coefficient in the Barabási-Albert model we should ask the quation of what the probability is that node \(i\) intorduced at \(t_{i}\) is connected to node \(j\) introduced at \(t_{j}\).
\[P(i - j) = mP_{i} = m\frac{k_{i}}{2mt} = \frac{k_{i}}{2t} = m\Big(\frac{t_{j}}{t_{i}}\Big)^{1/2}\frac{1}{2t_{j}} = \frac{m}{2}(t_{i}t_{j})^{-1/2}\]What is the expected number of links between a nodes links at the end of the generating process which was introduced at timestep \(t_{l}\)?
\[n_{l} ~=~ \frac{1}{2}\sum_{t_i = 1}^{N}\sum_{t_j = 1}^{N}P(l-i)P(l-j)P(i-j) = ... = \frac{m^{3}}{16t_l}(lnN)^{2}\]With words: if \(l\) is linked to \(j\) and it is linked to \(i\) the probability of \(i\) being linked to \(j\) is \(P(i-j)\) and it is true for all the links of \(l\) and therefore the summation, taking the continous limit and actually integrating in the \(...\) process one can acquire the result above.
The number of links between the neighbors of \(l\) is \(\approx ~ \frac{k^{2}_l}{2} = \frac{m^{2}N}{2t_{l}}\) in \(t = N\). The clustering coefficient is the number of links between the neighbors of \(l\) in the paths where \(l\) is present divided by all the edges.
\[C = \frac{m^{3}}{16t_l}(lnN)^{2}\frac{2t_l}{m^{2}N} = \frac{m(lnN)^{2}}{8N}\]We can see that it is not \(l\) dependent at all. This is decaying slower with \(N\) than the Erdős-Rényi model, however, in real networks there is no decay at all.
Preferential attachement can be measured by simply observing the system for \(\Delta t\) amount of time.
\[\frac{\Delta k_i}{\Delta t} ~\propto~ P(k_{i})\]Taking the integral of \(P(k)\) for all degrees in order to reduce noise in real networks.
\[\kappa (k) = \int P(k)dk\]If \(\kappa\) is proportional to \(k\) then there is no preferential attachement if it is proportional to \(k^{2}\) then there is.
The problem with the Barabási-Albert model so far is that in real networks \(\gamma\) is \(\in ]2;3[\) while here it is \(3\). This results in oldest nodes having the most connections which is not true for real networks either.
We can introduce a finesse \(a\), a parameter that makes \(\gamma\) tunable by modifying preferential attachement’s \(P_{i} \propto k_{i} - a\) probability.
Going to the same process and taking the large \(N\) limit:
\[P_{i} ~=~ \frac{k_{i} - a}{\sum_{j}(k_{j} - a)} = \frac{k_{i} - a}{2M - Na}\]After all the differential equation results in:
\[k_{i}(t) = m\cdot\Big(\frac{t}{t_{i}}\Big)^{\frac{1}{2 - a/m}} ~~\rightarrow ~~ p(k) = 2m^{2}k^{-3 + a/m}\]This can also be done with not an additive but a multiplicative finesse parameter \(\eta_{i}\) which is drawn from a \(\rho(\eta)\) distribution.
- scale-free : if \(\rho(\eta) = \delta(\eta - \eta_{0})\) results in the original Barabási-Albert model
- fit-gets-rich : nodes have different \(\eta\), \(\beta\) gets larger with \(\eta\) and it is scale-free and in the long run the largest hubs are the fittest
- Bose-Einsteinn condensation : winner takes all
Alex Olar
Christian, foodie, physicist, tech enthusiast