### Exponential network

For the case in wich any of the existing node can be selected with the same probability to be connected with the new added node, the probability $\Pi (k,t)$ in independent of $k$ and is given by the following expression

$\Pi (k,t)=\frac{1}{N(t)}=\frac{1}{t+1}$

Where $N(t)=t+1}$ is the nodes total number at time $t}$. After long enough time the function $P(k,t)$ reaches a steady state in which $P(k,t+1)=P(k,t)=P(k)$. In that steady state the solution for the time evolution is

$P(k)=2^{-k}$

which is the exponential distribution. It is important to mention that this distribution emerges in the context of networks growth as a result of having equal probability of any existing node of being selected to form a new connection, with the recently added node.

### Free-scale topology

In many networks in real life, connections are not formed based on equivalent probabiliies of being selected. For this reason, Barabasi introduced the concept of preferential attachment, in which the new nodes are added to the network with some bias. Networks following this principle present, few hubs that have lots of connections, while anyother else only has few. Barabasi suggested that the probability of connection $\Pi (k,t)$ should take the following form:

$\Pi (k,t)=\left ( \sum_{n=0}^{N(t)}k_{n} \right )^{-1}k$

where $k_{n}$ is the n-th node connectivity existing at time $t$. The factor before $k$ is just to guarantee that the probability $\Pi (k,t)$ is normalized. With this expression, the behaviour is as follows: the larger the connectivity, the larger the probability of form a connection with it. Due to the fact that nodes are added in each time step, if we start with zero conecctions at time $t=0$ then for any time $t>0$ we have

$\sum_{n=0}^{N(t)}k_{n}=2t$

and furthermore,

$\Pi (k,t)=\frac{k}{2t}$
In the limit of $t\to \infty$, the system reaches a steady state and then the stationary connection distribution $P(k)$ can be expressed as follows
$P(k)=\frac{4}{k(k+1)(k+2)}$
Although , the above expression is not a perfect power law (figure at the bottom), for high values of k, the distribution behaves as $P(k)\sim k^{-3}$. This result is very interesting because, the preferencial attachment leads to connectivity distributions that have free-scale tails. These tails are responsible of generating elements highly connected. On the other hand the result is also discouraging because the preferencial attachment process allways gives us the exponent $\gamma =3$, which is not frequently found in nature. In other words, eventhougth the preferential attachment behaviour gives us a power law, is it unable of accurately describe the variety of exponents found in nature. For this reason, there have been many proposals for the probability function $\Pi (k,t)$ to describe different preferential attachments.

Log-Log plot of connections distribution for free-scale topology The red dashed line is a power law plot $f(k)=4k^{-3}$, we should note that $P(k)\sim 4k^{-3}$ for high values of $k$

Back     Next