Generative Models

Preferential Attachment

Start with any type of network.
Additinonal nodes get added one at a time.

Each node in the network (except the existing nodes) have $c$ directed links out of them.
Each link is directed to a randomly chosen, previously generated, node.

The chance that a node with in-degree $d$ is the end-point of a directed link is:
\[\frac{d+a}{\sum(d+a)}\]

This produces the result that old nodes become more popular as they have a greater preferential attachment.

Consider we start with a network with a single node:

graph LR
1

We can then continue the example by calculating the preferential attachment in a table, where $a=0.5$:

Iteration	1	2	3	4
1	$\frac11$
2	$\frac34$	$\frac{1}{4}$
3	$\frac{1.5}{3.5}$	$\frac{1.5}{3.5}$	$\frac{.5}{3.5}$
4	$\frac{1.5}{5}$	$\frac{1.5}{5}$	$\frac{1.5}{5}$	$\frac{.5}{5}$

flowchart LR
2 --> 1
3 --> 2
4 --> 2

Additional nodes are chosen by random number, weighted by the distribution of preferential attachment in the table.