{VERSION 3 0 "IBM INTEL NT" "3.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 
0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{PSTYLE "Normal" 
-1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 
-1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "
" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "with(networks):" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 431 "If the Internet were connected at
 random then you might expect the average number of steps between any \+
two nodes to grow as the number of nodes increases. Since the Internet
 works by joining nodes over variousn routes involving many  links thi
s would lead to a gradual slowing down of the response. The first part
 of this problem is to show how the rate of growth scales with the num
ber of nodes for a randomly connected network.. " }}{PARA 0 "" 0 "" 
{TEXT -1 199 "To do this we use the built-in graph functions in Maple \+
to generate random networks and to calculate their diameters. (The dia
mater of a network is the average number of links between any two node
s.)" }}{PARA 0 "" 0 "" {TEXT -1 115 "First create a random network wit
h m nodes and 2n undirected connections (i.e. n edges) by random(m,n).
 For example" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "G := random
(5,10):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "Now have a look at wha
t G looks like:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "draw(G);
" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 169 "G has 10 edge
s; since each edge joins 2 nodes there are 4 links leaving (or enterin
g) each node. What are the range of values for n/m for a connected gra
ph ( = network)?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 256 7 "Answer:" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 100 "The function diameter calculates \+
the average length of the shortest path between any pair of nodes. " }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "diameter(G);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 328 "
How does the diameter of a random network vary with (a) the ratio of n
odes to edges (i.e the average number of connections per node) and (b)
 the size of the network (i.e. the number of nodes for a fixed ratio m
/n)? Use \n                                                           \+
  with(plots): plot([[x1,y1],[x2,y2],[x3,y3],...]" }}{PARA 0 "" 0 "" 
{TEXT -1 94 "to plot a set of points at (x1,y1), (x2,y2) ... in order \+
to display your results graphically. " }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 196 "We now construct a different type of graph called a smal
l world network. The task is to investigate the diameter of this type \+
of network and to decide whether it is a better model of the Internet.
" }}{PARA 0 "" 0 "" {TEXT -1 92 "We start by constructing a cycle grap
h (every vertex connected to its k nearest neighbours):" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "G1:='G1':G1:=cycle(6):" }{TEXT -1 
0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 119 "This creates a cycle graph with 6 vertices and k=2. We need to
 increase k. The following gives a cycle graph with k=4. " }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 106 "for i from 1 to 4 do addedge(\{i,i
+2\},G1) od:for i from 6 to 5 by -1 do addedge(\{i, i-4\},G1) od: draw
(G1); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "edges(G1);" }}
{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 80 "Make a new copy of G1 so
 we can return to it if required; work with the copy G2." }}{PARA 0 ">
 " 0 "" {MPLTEXT 1 0 18 "G2:=duplicate(G1):" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 577 "The following reconnects each of the edges of each of \+
the vertices of the cycle graph with probability p, producing a so-cal
led small world network. The object is to plot how the diameter of a s
mall world network changes with p and N and to decide if small world n
etworks give a better representation of the Internet. (You will need t
o use a range of values of p and quite large values of N. For small va
lues of N, as in the example below, the program is not accurate becaus
e it does not check that an edge is not added more than once. This wil
l not matter for large networks.)" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 10 "N:=6:k:=4:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
74 "numb:=rand(1..N):numb2:=rand(0..100):p:=0.7:#set up random number \+
function" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "for i from 1 to
 k*N \ndo cond:=numb2()/100: x1:=numb():x2:=numb(): " }}{PARA 0 "> " 
0 "" {MPLTEXT 1 0 74 "    x3:=x1+i-1:                           # choo
se an edge label at random" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "    e
d:=cat(`e`,x3):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 296 "      if cond >
 p and member(ed,edges(G2))='true' then\n         v1:=op(1,ends(ed,G2)
):delete(ed,G2): #insert check that v1<>x2                            \+
                 addedge(\{v1,x2\},G2):\n         fi:  # if the edge i
s in G2 reconnect the end v1 to x2 at random                          \+
     " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od:" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 18 "draw(G2);ends(G2);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#<-<$\"\"\"\"\"#<$F%\"\"$<$F%\"\"&<$F&F(<$F&\"\"%<$F(F-<
$F(F*<$F-F*<$F*\"\"'<$F%F2<$F&F2" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 26 "diameter(G2);diameter(G1);" }}{PARA 11 "" 1 "" {TEXT 
-1 0 "" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 0 "" }{XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 0 "" }}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "21 0 0" 18 }{VIEWOPTS 1 1 0 
1 1 1803 }