Network Models

A graph generated by the binomial model of Erdos and Rényi (p = 0.01)

The parameter $p$ in this model can be thought of as a weighting function; as p increases from 0 to 1, the model becomes more and more likely to include graphs with more edges and less and less likely to include graphs with fewer edges. In particular, the case p = 0.5 corresponds to the case where all graphs on n vertices are chosen with equal probability.
The article will basically deal with the G (n,p) model where n is the no of nodes to be created and p defines the probability of joining of each node to the other.

Empirical Network Features:⚓︎

Power-law (heavy-tailed) degree destribution
Small average distance (graph diameter)
Large clustering coefficient (transitivity)
Giant connected component, hierachical structure,etc

Generative models:⚓︎

Random graph model (Erdos & Renyi, 1959)
Preferential attachement model (Barabasi & Albert, 1999)
Small world model (Watts & Strogatz, 1998)

Random Graph Model⚓︎

Erdos and Renyi, 1959.

There are two closely related variants of the Erdos–Rényi (ER) random graph model.

G(n, m) model⚓︎

In the G(n, m) model, a graph is chosen uniformly at random from the collection of all graphs which have $n$ nodes and $m$ edges. For example, in the G(3, 2) model, each of the three possible graphs on three vertices and two edges are included with probability 1/3.

Graph $G\{E, V\}$, nodes $n = |V|$, edges $m = |E|$ $G_{n,m}$ - a randomly selected graph from the set of $C^m_{n(n−1)/2}$ graphs with $n$ nodes and $m$ edges

G(n, p) model⚓︎

geeksforgeeks In the G(n, p) model, a graph is constructed by connecting nodes randomly. Each edge is included in the graph with probability p independent from every other edge. Equivalently, all graphs with $n$ nodes and $m$ edges have equal probability of $p^m(1-p)^{(\frac{n}{2}-m)}$

$G_{n,p}$, each pair out of $n(n − 1)/2$ pairs of nodes is connected with probability $p$, $m$ - random number, $\langle k \rangle$ - average node degree $$\langle m \rangle = p \frac{n(n − 1)}{2}$$ $$\langle k \rangle = \frac{1}{n} \sum_i{k_i}=\frac{2 m }{n}=p(n-1) \approx pn$$

Probability that i-th node has a degree $k_i = k$ $$P(k_i = k) = P(k) = C^k_{n-1}p^k(1-p)^{n-1-k}$$

(Bernoulli distribution) * $p^k$ - probability that connects to k nodes (has k-edges) * $(1 − p)^{n−k−1}$ - probability that does not connect to any other node * $C^k_{n-1}$ - number of ways to select k nodes out of all to connect to

Limiting case of Bernoulli distribution, when $n → ∞$ at fixed $\langle k \rangle = pn = λ$ (see upper formula) $$P(k) = \frac{\langle k \rangle^ke^{-\langle k \rangle}}{k!}=\frac{λ^ke^{-λ}}{k!}$$

(Poisson distribution)

Phase Transition⚓︎

One of the most interesting features of the Erdos-Renyi model is the phase transitions, that changes the system state. In our case phase transition reffers to the appearence of the gigantic connected component (GCC).

Consider $G_{n,p}$ as a function of $p$ * p = 0, empty graph * p = 1, complete (full) graph * There are exist critical $p_c$, structural changes from $p < p_c$ to $p > p_c$ * Gigantic connected component appears at $p > p_c$

Let $u$ - fraction of nodes that do not belong to GCC. The probability that a node does not belong to GCC $$u = p(k=1)•u + P(k=2)•u^2 + P(k=3)•u^3 ... =$$ $$= \sum_{k=0}^∞{P(k)u^k} = \sum_{k=0}^∞ \frac{λ^ke^-λ}{k!}= e^{-λ}e^{λu} = e^{λ(u-1)}$$

Let $s$ -fraction of nodes belonging to GCC (size of GCC) $$s = 1 — u$$ $$1-s=e^{-λs}$$ * when $λ \rightarrow ∞, s \rightarrow 1$ * when $λ \rightarrow 0, s \rightarrow 0$ * $λ=pn$

$λ_c = p_cn = 1$ $p_c = \frac{1}{n}$

Threshold probabilities when different subgraphs of g-nodes appear in a random graph⚓︎

$p_c \sim n^{-g/(g-1)}$ having a tree of order g
$p_c \sim n^{-1}$, having a cycle of order g
$p_c \sim n^{-2/(g-1)}$ complete subgraph of order g

Configuration model⚓︎

Select a sequence of nodes with degreees $D = \{k_1, k_2, k_3, … k_n\} : \sum_i {k_j} = 2m$ to follow given distribution $P(k)$. For example: 1 1 1 1 1 2 2 2 3 3 3... $$P(k) = \frac{ \#(k_i = k)}{2m}$$

Randomly select two nodes from the sequence and form an edge between them

Growing random graph⚓︎

Stochastic growth model: * t = 0, m unconnected nodes * growth: on every time step t = {1,2, 3,4...} add a node with m edges $k_i(t = i)=m$ * attachement: form m edges with existing nodes uniformly at random,

Expected i-th node degree at t $k_i(t) = m + \frac{m}{i+1} + \frac{m}{i+2} + … + \frac{m}{t}$