In class we briefly discussed the Strogatz$-$Wells model for a small world network. Initially,

imagine $n$ nodes arranged around a circle, with each node connected by an edge to its $c$ nearest

neighbors $($for simplicity, you may assume that $c$ is even$).$

$($a$)$ What is the diameter of this network?

To turn the network into a small world network, do the following. Take each edge in turn, and

with probability $p$ delete that edge and add a new edge to the network between any randomly

chosen pair of edges. Networks so formed have two parameters: $c$ and $p.$ When $p=0,$ all networks

are connected only locally. As $p1$ the network approaches a Poisson$-$random network $($a form

of configuration network, with degree distribution given by the Poisson distribution, which is the

same as the Erd$$s$-$R$$nyi graph$).$

$($b$)$ Simulate a set of small$-$world network with $n=100$ nodes, $c=4$ and $($i$)p=0,($ii$)$

$p=0\mathrm{.}001,($iii$)p=0\mathrm{.}01,($iv$)p=0\mathrm{.}1.$ Make $30$ networks for each value of $p>0.$ Calculate

the average diameter of the networks made for each $p$ value $($if you are using Matlab for your

simulations, look up the function distances$),$ and plot it as a function of $p.$ You will find that

even a small number of random connections are enough to reduce the diameter of the graph to

something similar to the Erd$$s$-$R$$nyi diameter.