creation of a matrix for a given graph and to represent it

small
world

#1

link text

the figure named as figure 1 contains 3 graphs (regular, small world and random). Using regular graph we have to make a small world graph. Plz help me wid dis question