The recipe or method for generating random networks with preferential attachment can have slight variations, though they all produce highly similar results. In this problem sheet we will consider a slightly different version from the steps in the lecture notes with gaps:

Begin with a set of $3$ nodes that each have $2$ edges and so form a triangle, i$.$e$.$ a clique of $3.$ In this version of the method each node will start with $2$ edges $($rather than $3$ as in the lecture notes$).$

Add a new node to the network.

Form a new random edge with one of the existing nodes, using preferential attachment such that

$Pr($ new node links with node $i)prop{k}_i=\frac{k_i}{{\displaystyle \underset{i}{\overset{?}{}}}{k}_i},$

where $k_i$ is the current degree of node $i.$

$4.$ Let the chosen node from Step $3($that you just connected to the new node$)$ be node $j.$

$5.$ Add a second random edge to the new node, again using preferential attachment to choose the node to connect with, but avoid duplicating the first edge by excluding node $j.$ The probabilities will be given by$,$

$)(j$

where $k_i$ is the current degree of node $i.$

$6.$ Repeat Steps $2-5$ until you have the desired number of nodes.

Question $1.$ Generate a random graph with preferential attachment $($using the steps above$)$ until you have $12$ nodes. You will need a random number generator and it will likely take $30$ minutes or more to do this question. Present the network you generate as an edge$-$list $($who is connected to whom$)$ and a sketch of your network. Your working for this question may take several pages so do not include it$.$