Simulating Small-World Networks
by Mary Lynn Reed


Listing One

#!/usr/bin/perl

# Generate an Erdos-Renyi Random Graph with $N nodes 
# and edge probability $p using random seed $seed
# 

$N = 50;
$p = 0.2;
$seed = 11967;

print "graph ER { \n";
print "node [shape=point,color=blue,width=.1,height=.1];\n";

srand($seed);
foreach $i (1..$N){
    foreach $j ($i+1..$N){
	  $r = rand();
	  if($r < $p){
		print "$i -- $j;\n";
	  }  
    }
}

print "}\n";




Listing Two

#!/usr/bin/perl

# Generate a Watts-Strogatz Small World Network
# with $N nodes, starting degree $K, and probability
# of rewiring $p

$N = 80;
$K = 4;
$p = .3;
$seed = 189123;

print "graph WS { \n";
print "node [shape=point,color=blue,width=.1,height=.1];\n";

srand($seed);

# initial step -- set up ring lattice with 
# $N nodes, each of degree $K
foreach $i (0..$N-1){
    $left = int($K/2); # num nodes to connect to left
    $right = $K - $left; # num nodes to connect to right
    foreach $j (1..$left){
	  $ln = ($i-$j) % $N;	  
	  $graph{$i}{$ln} = 1;	  
	  $graph{$ln}{$i} = 1;	  
    }
    foreach $j (1..$right){
	  $rn = ($i+$j) % $N;	  
	  $graph{$i}{$rn} = 1;	  
	  $graph{$rn}{$i} = 1;	  
    }
}

# Rewire each edge with probability $p

foreach $i (keys %graph){   
    foreach $j (keys %{$graph{$i}}){
	  $r = rand();	  
	  if($r < $p){
		# randomly select a new node $jnew to connect to $i
		$done = 0;		
		while(!$done){
		    $jnew = int($N*rand());
		    if( ($jnew != $i) && ($jnew != $j) ){
			  $done = 1;			  
		    }
		    
		}	
		# remove edge $i <-> $j
		undef $graph{$i}{$j};		
		undef $graph{$j}{$i};		
		# add edge $i <-> $jnew
		$graph{$i}{$jnew}++;		
		$graph{$jnew}{$i}++;		
	  }
    }
}

# print graph
foreach $i (keys %graph){   
    foreach $j (keys %{$graph{$i}}){	  	  
	  print "$i -- $j\n";	  
    }
}
print "}\n";

	  
    


Listing Three

#!/usr/bin/perl

# Generate a Barabasi-Albert Scale-Free Network
# with $N nodes, starting with $m_0 nodes and
# adding $m edges at each timestep

$N = 500;
$m_0 = 10;
$m = 1;
$seed = 5255221;

print "graph BA { \n";
print "node [shape=point,color=blue,width=.1,height=.1];\n";

srand($seed);

# start with $m_0 nodes and no edges
# First step -- add 1 node and $m new edges
# no preferential attachment here since no edges exist yet
foreach $i (1..$m){
    # select one of first $m_0 nodes (labelled 0..$m_0-1)
    # to attach to node $m_0
    $j = int($m_0*rand());    
    $graph{$m_0}{$j} = 1;    
    $graph{$j}{$m_0} = 1;    
}

# Preferential Attachment Growth
$num_steps = $N - $m_0 - 1;
foreach $t (1..$num_steps){
    $new_node = $m_0 + $t;    
    #calculate degree seq and sum of degrees
    $sumdeg = 0;    
    foreach $i (0..$new_node-1){
	  if(exists $graph{$i}){
		$degree{$i} = keys %{$graph{$i}};		
	  } else {
	      $degree{$i} = 0;	      
	  }
	  $sumdeg += $degree{$i};	  
    }
    
    foreach $j (1..$m){
	# preferentially select node
	$R = int($sumdeg*rand());	
	$cS = 0;    $i = 0;	
	while($cS < $R){
	    $cS += $degree{$i};
	    $i++;	    
	}
	$sel_node = $i ? $i-1 : 0;	
	# add edge $new_node <-> $sel_node
	$graph{$new_node}{$sel_node} = 1;	
	$graph{$sel_node}{$new_node} = 1;	
  }
}


# print graph
foreach $i (keys %graph){   
    foreach $j (keys %{$graph{$i}}){	  	  
	  print "$i -- $j\n";	  
    }
}
print "}\n";

	   
	  




