  According to Goldbach conjecture, any even number can be broken up as the sum
of two prime numbers : $n = p + q$. We construct a network where each node is a
prime number and corresponding to every even number $n$, we put a link between
the component primes $p$ and $q$. In most cases, an even number can be broken
up in many ways, and then we chose {\em one} decomposition with a probability
$|p - q|^{\alpha}$. Through computation of average shortest distance and
clustering coefficient, we conclude that for $\alpha > -1.8$ the network is of
small world type and for $\alpha < -1.8$ it is of regular type. We also present
a theoretical justification for such behaviour.
