##################################################################################################################### # Author: Troy Tassier # Project advisor: Filippo Menczer # This version: April 7, 2001 # Copyright (2000, 2001) The University of Iowa # # The code is written for Perl. The Graph module (from http://cpan.org/) is also required to execute the program. # # The subroutine 'APSP_floyd_warshall_TT' listed at the end of this file can be placed inside # "Graph.pm" in order to calculate the characteristic path length of the evolved graph. # The subroutine is a slightly modified version of 'APSP_floyd_warshall' included in the standard Graph module. ##################################################################################################################### use Graph::Directed; $seed=60; srand($seed); for ($runs=0;$runs<1;$runs++){ #change loop condition to complete multiple runs ################################################################### # Paramaters: ################################################################### $deltak = 0.001; # probability of increasing network by 1 $deltakd = 0.001; # probability of decreasing network by 1 $deltap = 0.001; # range of change in Pa in any given period $omega = 0.01; # probability of being fired in any given period $po = 0; # base probability of hearing about a job in any period $initpo=0.01; # initial level of probability for all agents $theta = 10; # level of energy that must be held in order to reproduce $min=.3; # level of energy that must be held in order to live for the period $N =50; # number of agents in the initial population $Jobs = $N; # number of jobs in the economy $ko = 2; # number of friend links in initial period $ksat = 50; # maximum number of friends allowed in any one period $costpa = 1; # set $costpa equal to the average wage in 1st period $costka = 50; # set $costka equal to the maximum # of links allowed * avg wage in first period $ITERATIONS= 5000; # number of iterations to run simulation for $IT= 10; # number of random graphs created for comparison to each evolved graph $r_wage=0; # set to 1 for RANDOM WAGE experiment $evol=1; # turns on the reproduction algorithm if "evol=1" ########################################################################################## $gsp{$ITERATIONS} = Graph::Directed->new; $z=0; print "\nrun = $runs; friend cost = $costka; seed=$seed run=$runs\n\n"; initialize(); #initializes a set of agents, jobs and an initial random social network for ($z=1;$z<=$ITERATIONS;$z++) { job_search(); #agents search for jobs energy(); #agent energy s updated based on wages and search strategies mutate(); #the search strategies of the agents are varied to allow for "evolution" if ($evol==1){ #to turn off evolution set $evol to zero in paramaters above reproduce(); #reproduction algorithm agent_dies(); #death of agent algorithm } stats(); #computes and prints statistics associated with each run } Gen_r_graph(); #generates set of random graphs for comparison with evolved graph }#end runs ############################################################################ sub mutate{ foreach $i (keys %agent1){ ################################### #fire agent with probability omega ################################### $j=rand; if ($j<$omega){ if ($agent3{$i}!=-1 ) { $k=$agent3{$i}; # set $k=agent's job number $agent3{$i}=-1; # set agent's job number = -1 indicating unemployed $agent4{$i}=0; # set agent's wages = 0 $job1[$k]=-1; # set employee number of previous job = -1 indicating job is vacant } } ############### # Picks new Pa ############### if ($deltap>0) { $h=rand; $k=rand $deltap; if ($h < .5) { $agent2{$i}=($agent2{$i}+$k); #add [0,deltap) to agent's Pa } else { $agent2{$i}=($agent2{$i}-$k); #subtract [0,deltap) from agent's Pa } if ($agent2{$i}<0) { #truncate Pa to 0 if <0 $agent2{$i}=0; } if ($agent2{$i}+$po>1) { #truncate Pa to 1 if >1 $agent2{$i}=1-$po; } } ############################################### # With Pr(deltak) add one new link to a friend ############################################### $j=rand; if ($j<$deltak) { if ($graph[$i][0]<$ksat) { # check to see if number of friends is greater than allowed $agent1{$i}=$agent1{$i}+1; # w/ Pr(deltak) - add one to agent's Ka $graph[$i][0]=$agent1{$i}; # - add one to number of links to agent's node $k=$graph[$i][0]; # - save as $k the number of links in agent's graph add_link($i,$k); # create a link from agent k to agent i } # close if $agent } # close if $j ################################################################# # With Pr(deltak) delete one link at random from agent's friends ################################################################# $j=rand; if ($j<$deltakd) { if ($graph[$i][0]>2) { $k=($graph[$i][0]-1); # save number of links in agents graph as $k $agent1{$i}=($agent1{$i}-1); # set agent's number of friends = one less $graph[$i][0]=$agent1{$i}; # set number of links on graph to agent to one less $h=int (rand $k)+1; # pick node from 1 to $k+1 (k+1 to ensure you don't pick 0) $matrix[$i][$graph[$i][$h]]=0; while ($h<=($k+1)) { $graph[$i][$h]=$graph[$i][$h+1]; # moves every link back one $h++; $graph[$i][$h]=() # make last link the same node as previous } } } } #end for each } ####################################################################################### sub job_search{ ############################################################# # Pick a random agent to start job search loop ############################################################# $jj=0; foreach $id (keys %agent0) { $agentlist[$jj]=$id; $jj++; } for ($p=0;$p<$jj*5;$p++){ #shuffle list to get a random order $s1=int(rand $jj); $s2=int(rand $jj); $hold=$agentlist[$s1]; $agentlist[$s1]=$agentlist[$s2]; $agentlist[$s2]=$hold; } for ($s=0;$s<$jj;$s++){ $search=$agentlist[$s]; ################################## # Create job opening list ################################## $j=0; for ($i=0;$i<$Jobs-1;$i++) { if ($job1[$i] == -1) { $joblist0[$j] = $job0[$i]; # wage of first job on joblist $joblist1[$j] = $i; # job number of first job on list $j++; } } $numjobs=$j; # set $numjobs to the number of jobs on the joblist ################################### # notify search agent of job openings ################################### $i=0; $g=1; $h=0; for ($k=0;$k<$numjobs;$k++) { $agentknow[$search][$k] = 0; $h=rand; if ($h<($po+$agent2{$search})) { $agentknow[$search][$k]=1; # if agent knows about job, set agentknow to 1 for job k } if ($agentknow[$search][$k] == 0) { # check if agent $i knows about the job for ($g=1;$g<=$agent1{$search};$g++) { # if no check with each friend in $i's graph $friend=$graph[$search][$g]; $h=rand; if ($h<($po+$agent2{$friend})) { $agentknow[$search][$k]=1; } } } } ########################################################################### # Have each agent with an "agentknow" list of possible jobs to choose from # agent now chooses best job from his "agentknow" list ########################################################################### $max=0; for ($j=0;$j<$numjobs;$j++) { if ($agentknow[$search][$j] == 1) { if ($joblist0[$j]>$max) { $max=$joblist0[$j]; $maxjob=$joblist1[$j]; } } } if ($max>$agent4{$search}) { $temp1=$agent3{$search}; $job1[$temp1]=-1; $agent3{$search}=$maxjob; # sets agent's new job number $agent4{$search}=$max; # sets agent's new wage $job1[$maxjob]=$search; } for ($j=0;$j<$numjobs;$j++) { $agentknow[$search][$j]=(); } $agentknow[$search]=(); }#ends for loop } #ends subroutine ############################################################################ sub energy{ if ($r_wage==1){ $jj=0; foreach $value (values %agent0) { $agentlist[$jj]=$value; $jj++; } } foreach $i (values %agent0) { $agent7{$i}++; if ($r_wage==1){ #used in random wage experiment $number=int(rand $jj); $r_agent=$agentlist[$number]; $wage=$agent4{$r_agent}; #sets wage to that of a random agent in population $agent5{$i}=($agent5{$i}+$wage-$min); # adds energy from wages and subtracts energy required to live } if ($r_wage==0) { #used in normal runs of simulation $agent5{$i}=($agent5{$i}+$agent4{$i}-$min); # adds energy from wages and subtracts energy required to live $agent5{$i}=($agent5{$i}-($agent2{$i}/$costpa)); $agent5{$i}=($agent5{$i}-($agent1{$i}/$costka)); } } } ########################################################################### sub reproduce{ $jj=0; foreach $value (values %agent0) { $agentlist[$jj]=$value; $jj++; } for ($p=0;$p<$jj*5;$p++){ #shuffles agents into a random order $s1=int(rand $jj); $s2=int(rand $jj); $hold=$agentlist[$s1]; $agentlist[$s1]=$agentlist[$s2]; $agentlist[$s2]=$hold; } for ($s=0;$s<$jj;$s++){ $i=$agentlist[$s]; if ($agent5{$i}>$theta) { # agent reproduces! $agent7{$N}=0; $agent6{$N}=1; # birth of an agent! $agent5{$N}=$agent5{$i}/2; # gives offspring 1/2 of energy $agent5{$i}=$agent5{$i}/2; $agent4{$N}=0; # offspring has no inital wage $agent3{$N}=-1; # offspring has no initial job $agent2{$N}=$agent2{$i}; # offspring has same pa $agent1{$N}=$agent1{$i}; # offspring has same ka as parent $agent0{$N}=$N; if ($deltak>0) { foreach $ii (keys %agent1) { $matrix[$N][$ii]=0; #initialize matrix for new agent $matrix[$ii][$N]=0; } for ($j=0;$j<=$agent1{$N};$j++) { #fill social network of offspring as that of parent $graph[$N][0]=$j; if ($j>0) { $graph[$N][$j]=$graph[$i][$j]; # add_link($N,$j); $m=$graph[$N][$j]; $matrix[$N][$m]=1; } } } #if deltak loop $N=$N+1; } } #ends for loop } ################################################################## sub agent_dies{ $jj=0; foreach $value (values %agent0) { $agentlist[$jj]=$value; $jj++; } for ($p=0;$p<$jj*5;$p++){ #shuffle agents randomly $s1=int(rand $jj); $s2=int(rand $jj); $hold=$agentlist[$s1]; $agentlist[$s1]=$agentlist[$s2]; $agentlist[$s2]=$hold; } for ($s=0;$s<$jj;$s++){ $i=$agentlist[$s]; if ($agent5{$i}<0) { # agent dies! for($j=0;$j<=$agent1{$i};$j++) { $graph[$i][$j]=(); } $graph[$i]=(); $job1[$agent3{$i}]=-1; delete $agent0{$i}; #delete all references to the agent delete $agent1{$i}; delete $agent2{$i}; delete $agent3{$i}; delete $agent4{$i}; delete $agent5{$i}; delete $agent6{$i}; foreach $j (keys %agent0) { $matrix[$i][$j]=(); $matrix[$j][$i]=(); $matrix[$i]=(); for ($h=1;$h<=$agent1{$j};$h++) { if ($graph[$j][$h] == $i) { #for each outgoing link from i to j add a new random link to j add_link($j,$h); } } } } # end if $ agent } #ends for s loop } ###################################################################################### sub initialize{ %agent0=(); #reset all agent characteristics in the case of a multiple run implimentation %agent1=(); %agent2=(); %agent3=(); %agent4=(); %agent5=(); %agent6=(); %agent7=(); ################################################################### # initialization of agents and initial graph network ################################################################### for ($i=0;$i<=$Jobs;$i++) { $job0[$i]=rand; # gives job a random wage in [0,1) $job1[$i]=$i; # job initially given to corresponding agent } for ($i=0;$i<$N;$i++) { $agent0{$i}=$i; # initialize an agent id number $agent1{$i}=0; # initialize variable to 0; number of friends set below $agent2{$i}=$initpo; # initial propensity to read paper $agent3{$i}=$i; # initial job number $agent4{$i}=$job0[$i]; # initial wage $agent5{$i}=2; # initial energy $agent6{$i}=1; # indicates agent is "alive" $agent7{$i}=0; # age of agent } ######################### # initialize empty graph ######################### for ($i=0;$i<$N;$i++) { $graph[$i][0]=0; } ############################### # initialize matrix ############################### for ($i=0;$i<$N;$i++) { for ($j=0;$j<=$N;$j++){ $matrix[$i][$j]=0; } } ############################ # initialize agentknow list (used to reprsent knowledge of open jobs on the job list) ############################ for ($i=0;$i<$N;$i++) { for ($k=0;$k<$Jobs;$k++) { $agentknow[$i][$k]=-1; } } ####################### # initialize friends ####################### if ($ko>0) { for ($i=0;$i<$N;$i++) { for ($p=1;$p<=$ko;$p++){ # give each agent ko friends in the first period $agent1{$i}++; $graph[$i][0]=$agent1{$i}; add_link($i,$p); } } } #if ko>0 } ##################################################################################### sub add_link { my ($i,$k) = @_; #variables passed in are agent i, friend #k $test=1; while ($test == 1) { $test=0; $count=0; foreach $r (values %agent0) { #count the number of agents $AG{$count}=$r; $count++; } $Q=int (rand $count); $graph[$i][$k]=$AG{$Q}; # get link to test to $m=$graph[$i][$k]; $matrix[$i][$m]=1; if ($agent6{$m}!= 1) { # if agent is dead pick new agent (should never happen) $test=1; $matrix[$i][$m]=(); } if ($graph[$i][$k] == $i) { # if agent picks herself pick new agent $test=1; $matrix[$i][$m]=0; } my $h=1; while ($h<=$graph[$i][0]) { if ($h!=$k) { if ($graph[$i][$k] == $graph[$i][$h]) { # if agent picks someone already in her network pick new agent $test=1; } # close if } $h++; } # close while } # close while } ##################################################################################### #Calculates average clustering measure for the population ##################################################################################### sub cluster { #set a group of temporary variables to zero $j=1;$avgC=0;$links=0;$pos_links=0; $cluster=0;$sumko=0;$sumC=0;$avgC=0;$max=0; foreach $i (keys %agent1) { #for each agent in the pop, chack to see which of her friends know each other if ($agent1{$i}>1){ $sumko=$sumko+$agent1{$i}; if ($agent1{$i}>$max){$max=$agent1{$i};} for ($j=1;$j<=$agent1{$i};$j++) { for ($k=1;$k<=$agent1{$i};$k++) { if ($j != $k) { $p=$graph[$i][$j]; $q=$graph[$i][$k]; if (defined $matrix[$p][$q]){ if ($matrix[$p][$q] == 1) { $links++; } #if == 1 } $pos_links++; } } } $cluster++; #counts the number of agents to be included in the clustering measure if ($pos_links==0){$pos_links=1;} $avgC=$links/$pos_links; #calculate the clustering of each individual agent $sumC=$sumC+$avgC; #add agent's clustering to the sum of the previous agents $avgC=0;$links=0;$pos_links=0; $j=1; if ($cluster==0){$cluster=1;} $C=$sumC/$cluster; #calculates clustering } } } #ends subroutine ############################################################################## sub stats{ ########################### # CREATE SUMMARY STATISTICS FOR THE POPULATION AFTER EACH PERIOD ########################### $i=0; $j=1; $k=1; $links=0; $pos_links=0; $sumk=0; $sump=0; $alive=0; $employed=0; foreach $i (keys %agent1) { $sumk=$sumk+$agent1{$i}; #COUNTS FRIENDS $sump=$sump+$agent2{$i}; #counts total search effort $alive++; #counts agents alive in each period if ($agent3{$i}!=-1) {$employed++;} #counts number of unemploed agents for ($j=1;$j<=$agent1{$i};$j++) { if ($z==$ITERATIONS) {$gsp{$z}->add_edge($i, $graph[$i][$j]);} #creates graph to be used in path lenght subroutine } if ($z == $ITERATIONS) { #In the last period of the simulation print all the characteristics printf "\n%d, ",$agent0{$i}; # of each agent currently in the population printf "%d, ",$agent1{$i}; printf "%f, ",$agent2{$i}; printf "%d, ",$agent3{$i}; printf "%f, ",$agent4{$i}; printf "%f, ", $agent5{$i}; printf "%d, ",$agent7{$i}; for ($kk=1;$kk<=$agent1{$i};$kk++) { printf"%d, ",$graph[$i][$kk]; } } # if $ITERATIONS } #foreach loop if ($alive>0){ $avgk=$sumk/$alive; $avgp=$sump/$alive; } cluster(); if ($z==$ITERATIONS){print"\n\n Final statistics for the evolved graph\n";} printf"\n%d, avgk=%.3f, avgp=%.3f, agents=%d, C=%.3f, ",$z,$avgk,$avgp,$alive,$C; if ($z==$ITERATIONS && $deltak>0) { my $APSP = $gsp{$z}->APSP_floyd_warshall_TT; $APSP=(); $gsp{$z}=(); $next=$z+500; $gsp{$next} = Graph::Directed->new; } } # end stats ################################################################################# sub Gen_r_graph { ################################################################### # Generate random graph to compare to evolved graph ################################################################### print "\n\n Statistics for random graphs\n"; $zz=0; while ($zz<$IT) { $meas{0} = Graph::Directed->new; # initialize matrix $i=0; $k=0; $j=0; $sumC=0;$avgC=0; for ($i=1;$i<=$alive;$i++) { #Create a number of agents equal to that in population and initialize a friendship matrix for ($j=1;$j<=$alive;$j++) { $matrixM[$i][$j]=0; } $agentM1{$i}=0; #set number of friends of each agent equal to 0 } $in=0; for ($p=1;$p<=$sumk;$p++) { #for each edge in the evolved graph create a random edge in the random graph $i=int (rand ($alive-1))+1; $o=int (rand ($alive-1))+1; $matrixM[$i][$o]=1; $meas{$zz}->add_edge($i, $o); $agentM1{$i}++; $a=$agentM1{$i}; $graphM[$i][$a]=$o; $in++; } if ($IT>0){ ###################################################################################################### # CREATE STATISTICS FOR RANDOM GRAPH (code is identical to that above except the random graph is used) ###################################################################################################### $i=0; $j=1; $k=1; $links=0; $pos_links=0;$C=0;$cluster=0; foreach $i (keys %agentM1) { $cluster++; for ($j=1;$j<=$agentM1{$i};$j++) { if ($agentM1{$i}>1){ for ($k=1;$k<=$agentM1{$i};$k++) { if ($j != $k) { $p=$graphM[$i][$j]; $q=$graphM[$i][$k]; if (defined $matrixM[$p][$q]){ if ($matrixM[$p][$q] == 1) { $links++; } } $pos_links++; } } } } if ($pos_links==0){$pos_links=1;} $avgC=$links/$pos_links; $sumC=$sumC+$avgC; $avgC=0;$links=0;$pos_links=0; } #foreach loop $C=$sumC/$cluster; $sumC=0; printf "Random graph %d agents=%d, avgk=%.3f, C=%.3f, ", $zz, $cluster, $in/$alive, $C; my $APSP = $meas{$zz}->APSP_floyd_warshall_TT; $APSP=(); print"\n"; $meas{$zz}=(); $j=0; foreach $j (keys %agentM1){ while ($k<$agentM1{$j}) { $graphM[$j][$k]=(); $matrixM[$j][$k]=(); $k++; } } $next=$zz+1; $meas{$next} = Graph::Directed->new; $zz++; } # end if } # end while } # end Gen_r_graph ###################################################################################################### # Code used in the "drop 2 friends" experiment ###################################################################################################### sub drop_agents{ foreach $i (keys %agent1){ if ($graph[$i][0]>2) { $k=($graph[$i][0]-1); # save number of links in agents graph as $k $agent1{$i}=($agent1{$i}-1); # set agent's number of friends = one less $graph[$i][0]=$agent1{$i}; # set number of links on graph to agent to one less $h=int (rand $k)+1; # pick node from 1 to $k+1 (k+1 to ensure you don't pick 0) $matrix[$i][$graph[$i][$h]]=0; while ($h<=($k+1)) { $graph[$i][$h]=$graph[$i][$h+1]; # moves every link back one $h++; $graph[$i][$h]=() # make last link the same node as previous } } } foreach $i (keys %agent1){ if ($graph[$i][0]>2) { $k=($graph[$i][0]-1); # save number of links in agents graph as $k $agent1{$i}=($agent1{$i}-1); # set agent's number of friends = one less $graph[$i][0]=$agent1{$i}; # set number of links on graph to agent to one less $h=int (rand $k)+1; # pick node from 1 to $k+1 (k+1 to ensure you don't pick 0) $matrix[$i][$graph[$i][$h]]=0; while ($h<=($k+1)) { $graph[$i][$h]=$graph[$i][$h+1]; # moves every link back one $h++; $graph[$i][$h]=() # make last link the same node as previous } } } } ############################################################################################# # This is a modified version of the APSP_floyd_warshall subroutine from the Perl Graph module. # Place the code below as a subroutine inside "Graph.pm" in the graph module. ############################################################################################# sub APSP_floyd_warshall_TT { my ( $graph, $attr ) = @_; $attr = 'Weight' unless defined $attr; my @V = $graph->vertices; my $V = @V; my ( %v2i, @i2v ); my $vertex_id = 0; foreach my $v ( @V ) { $v2i{ $v } = $vertex_id++; # Number the vertices. $i2v[ $v2i{ $v } ] = $v; } my $dist; # The distance matrix diagonal is initially zero. # (and the path matrix diagonal is implicitly undefs). foreach my $v ( $graph->vertices ) { my $i = $v2i{ $v }; $dist->[ $i ]->[ $i ] = 0; } my $path; # The rest of the distance matrix are the weights # and the rest of the path matrix are the parent vertices. foreach my $e ( $graph->edges ) { my ( $p, $s ) = $e->vertices; my $i = $v2i{ $p }; my $j = $v2i{ $s }; $dist->[ $i ]->[ $j ] = 1; #EDIT all paths are length 1 !!! in original APSP rhs = '$e->attribute( $attr );' $path->[ $i ]->[ $j ] = $p; } my ( $prev_dist, $prev_path, $prev_dist_ij, $prev_dist_ikpkj, $prev_path_ij, $prev_path_kj ); # O($V**3) quite obviously: three $V-sized loops. for ( my $k = 0; $k < $V; $k++ ) { $prev_dist = $dist; # Save and... $dist = [ ]; # ...reset. $prev_path = $path; # Save and... $path = [ ]; # ...reset. for ( my $i = 0; $i < $V; $i++ ) { for ( my $j = 0; $j < $V; $j++ ) { if ( defined $prev_dist->[ $i ]->[ $j ] ) { $prev_dist_ij = $prev_dist->[ $i ]->[ $j ]; $prev_path_ij = $prev_path->[ $i ]->[ $j ]; } else { undef $prev_dist_ij; } if ( defined $prev_dist->[ $i ]->[ $k ] and defined $prev_dist->[ $k ]->[ $j ] ) { $prev_dist_ikpkj = $prev_dist->[ $i ]->[ $k ] + $prev_dist->[ $k ]->[ $j ]; $prev_path_kj = $prev_path->[ $k ]->[ $j ]; } else { undef $prev_dist_ikpkj; } $prev_path_ij = $prev_path->[ $i ]->[ $j ]; $prev_path_kj = $prev_path->[ $k ]->[ $j ]; # Find the minimum and update the distance # and path matrices appropriately. if ( defined $prev_dist_ij and ( not defined $prev_dist_ikpkj or $prev_dist_ij <= $prev_dist_ikpkj ) ) { $dist->[ $i ]->[ $j ] = $prev_dist_ij; $path->[ $i ]->[ $j ] = $prev_path_ij; } elsif ( defined $prev_dist_ikpkj ) { $dist->[ $i ]->[ $j ] = $prev_dist_ikpkj; $path->[ $i ]->[ $j ] = $prev_path_kj; } # Both were undef which means infinite. } } } # Map the matrices back to a graph. my $count=0; my $total=0; my $count_all=0; my $apsp = ( ref $graph )->new; for ( my $i = 0; $i < $V; $i++ ) { my $p = $i2v[ $i ]; for ( my $j = 0; $j < $V; $j++ ) { my $s = $i2v[ $j ]; my $e = $apsp->add_edge( $p->name, $s->name ); $e->attribute( $attr, $dist->[ $i ]->[ $j ] ); #print "$e $dist->[$i]->[$j] \n"; if ((defined $dist->[$i]->[$j]) && ($dist->[$i]->[$j]>0)) { $total=$total+(1/$dist->[$i]->[$j]); $count++; } else {$count_all++;} $e->attribute( 'Prev', $path->[ $i ]->[ $j ] ); } } printf"L=%.3f",(1/($total/($count+$count_all))); return $apsp; }