Models of Complex Networks
Binomial Model
A random binomial model on $n$ nodes, denoted by the expression $\mathcal G_{n,\frac12}$, is a network on $n$ nodes in which each line exists, independently of all other lines with probability of $\frac12$.
To generate one of these networks, we randomly fill an adjacency matrix with 1’s and 0’s with equal distribution.
Counting Binomial Networks
In a binomial network there are $n\choose 2$ values in the adjacency matrix (for an undirected graph). Therefore there are:
- $2^{n\choose 2}$ possible network combinations for this network type.
Properties of $\mathcal G_{n,p}$
We can generalise $\mathcal G_{n,\frac12}$ to have any probability $p$ of a particular arc being filled.
The generation of a uniform random network on $n$ nodes is equivalent to a random experiment in which we independently toss exactly ${n\choose2}=\frac{n(n-1)}{2}$ fair coins. Each coin toss corresponds to the decision about one of the $n\choose 2$ possible links in the network.
Each coin toss is called a Bernoulli trial and counting heads (or tails) in a finite sequence of Bernoulli trials gives raise to the well studies binomial probability distribution.
Vertex Degrees
The degree of any vertex in a random binomial model on $n$ nodes is equivalent to a random variable counting the number heads in $n-1$ independent coin tosses:
- The vertex degree has binomial distribution and its expected value is $\frac{n-1}2$.
- The expected value in the general $\mathcal G_{n,p}$ is $p(n-1)$.
Expected Degree Distribution
In $\mathcal G_{n,p}$, the expected value of $f_d$ is:
\[\text{Pr}[\deg(v)=d]=\binom{n-1}{d}p^d(1-p)^{n-1-d}\]as $\deg(v)$ is a binomial random variable.
Number of Links
The number of links in a random binomial model on $n$ nodes is a random variable counting the number of heads in $n\choose 2$ independent coin tosses:
- The number of links has binomial distribution and its expected value is $\frac12{n\choose2}$.
- The expected value in the general $\mathcal G_{n,p}$ is $p{n\choose2}$.
Diameter
The diameter is generally 2 for large values of $n$.