《学习导览》 | 1. Complex networks demonstration via MATLAB (By Jari Saramaki)-Research Centre of Nonlinear Science

Complex networks demonstration via MATLAB (By Jari Saramaki)

[按语] 教学过程中发现了Jari Saramaki (Laboratory of Computational Engineering, Helsinki University of Technology)为他的复杂网络课程写的一个动态小例子,非常形象,分享给选课的同学们.

[运行环境] Matlab

clear all; close all;

% ------------------------------------------------------- complex networks demonstration

% ------------------------------------------------------- Laboratory of Computational Engineering,

% ------------------------------------------------------- Helsinki University of Technology

% ------------------------------------------------------- jsaramak@lce.hut.fi

% references: see e.g.

% Watts, Strogatz, Nature 393, 441 (1998)

% Barabasi, Albert, Science 286, 509 (1999)

% Albert, Barabasi, Nature 406, 378 (2000)

fprintf('\nCOMPLEX NETWORKS TUTORIAL\n');

fprintf('Helsinki University of Technology\n');

fprintf('\nIn the first part of the demonstration, three kinds of networks will be compared:\n')

fprintf('random networks, ordered networks and small-world networks.\n');

fprintf('All networks will have 150 nodes, and on the average 4 links per node.\n');

fprintf('\nPress any key to begin...\n');

pause;

% -------------------------------------------------------first item: a N-node random network with m=4;

fprintf('\nDisplaying a random network.\n');

N=150;

for i=1:N,

x(i)=cos(2*pi*i/N); y(i)=sin(2*pi*i/N); %display coordinates

end;

xy=[x; y]';

A=spalloc(N,N,4*N); % connection matrix: if A(i,j)=1, there's a link between i,j

for i=1:N,

for connects_to=1:2,

j=ceil(rand(1,1)*N);

A(i,j)=1;

A(j,i)=1;

end;

[xplot yplot]=gplot(A,xy); %generate punctuated vectors for graph plotting, see help gplot

fig1=plot(xplot,yplot,'ko-'); set(fig1,'MarkerFaceColor','k'); drawnow;

st=sprintf('A %d-node random network, with 4 neighbors per node\n',N);

title(st);

Arand=A; % save for later use

fprintf(st);

fprintf('Press any key\n');

pause;

% ----------------------------- second item: a N-vertex regular, circular 1-D lattice with 2 nearest-neighbor-connections

fprintf('\nDisplaying an ordered network.\n');

A=spalloc(N,N,2*N);

for i=1:N,

e2=i-2; if e2<1 e2=e2+N; end;

e1=i-1; if e1<1 e1=e1+N; end;

f1=i+1; if f1>N f1=f1-N; end;

f2=i+2; if f2>N f2=f2-N; end;

A(i,e1)=1; A(i,e2)=1; A(i,f1)=1; A(i,f2)=1;

A(e1,i)=1; A(e2,i)=1; A(f1,i)=1; A(f2,i)=1;

end;

[xplot yplot]=gplot(A,xy); %generate punctuated vectors for graph plotting, see help gplot

fig1=plot(xplot,yplot,'ko-'); set(fig1,'MarkerFaceColor','k'); drawnow;

st=sprintf('1-dimensional regular lattice with 2-nearest-neighbor-connections\n');

title(st);

A0=A; % save for later use

fprintf(st);

fprintf('\nPress any key...\n');

pause

% ---------------------------------- 3rd item: a small-world network with rewiring probability 5/100

fprintf('\nDisplaying a Watts-Strogatz small-world network.\n');

steps=ceil(N*5/100);

for k=1:steps,

i=ceil(rand(1,1)*N); % link from this node to be rewired

choices=[-2 -1 1 2];

delta=choices(ceil(rand(1,1)*4));

j=i+delta; % link to this node to be rewired (original -2,-1,+1, or +2)

if j<1 j=j+N; end;

if j>N j=j-N; end;

jumpto=ceil(rand(1,1)*N); % rewire to this node

A(i,j)=0; A(j,i)=0;

A(i,jumpto)=1; A(jumpto,i)=1;

[xplot yplot]=gplot(A,xy);

set(fig1,'XData',xplot,'YData',yplot); drawnow;

st=sprintf('Rewiring links, %d of %d rewired',k,N);

title(st);

pause(0.01);

end;

st=sprintf('A small-world network with p=%2.2f\n',steps/N);

title(st);

fprintf('Rewiring probability p=%2.2f\n',steps/N);

pause

% ------------------------------- 4th item: spreading on random network -----------------------------------------

fprintf('\nNext, the average distances between nodes are illustrated.\n');

fprintf('Distance between nodes = shortest number of links to be followed to get from A to B.\n');

fprintf('This is done with a simple spreading mechanism, where first one node is "infected",\n');

fprintf('and on every turn all nodes in contact with an infected node also become infected.\n');

fprintf('\nPress any key to start spreading in random network\n');

pause;

infected=zeros(1,N);

infected(1)=1; %infected=1 if infected

inf_index=find(infected);

[xplot yplot]=gplot(Arand,xy);

subplot(1,2,1), fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); hold on; drawnow;

title('Spreading in random network');

subplot(1,2,1), fig1b=plot(x(1),y(1),'ro-'); set(fig1b,'MarkerFaceColor','r');

subplot(1,2,2), fig2=plot(1,1,'r-'); st=sprintf('Amount of infected vs time');

fig2label=title(st);

tempA=Arand*diag(infected);

counter=1;

inf_count=zeros(1,N);

inf_count(1,1)=1;

while (sum(infected)<N), % repeat infection until everyone infected

new_infected=Arand*infected';

infected=or(infected,new_infected'); % <--- keep ones, don't need to know how long infected

counter=counter+1;

inf_count(1,counter)=sum(infected);

inf_index=find(infected);

[xplot yplot]=gplot(tempA,xy);

tempA=Arand*diag(infected);

set(fig1b,'XData',xplot,'YData',yplot);

set(fig2,'XData',1:counter,'YData',inf_count(1,1:counter));

st=sprintf('Amount of infected vs time: %d',inf_count(counter));

set(fig2label,'String',st);

drawnow;

pause(0.5);

end;

rand_inf=inf_count(1:counter); %save for later use

rand_countmax=counter;

fprintf('\nInfection spreads rapidly, meaning that average distances between nodes are short.\n');

fprintf('Press any key to start spreading in regular lattice\n');

pause;

% ------------------------------------------ 5th item: spreading on regular lattice ---------------------------------------

infected=zeros(1,N);

infected(1)=1; %infected=1 if infected

[xplot yplot]=gplot(A0,xy);

subplot(1,2,1), hold off; fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); hold on; drawnow;

title('Spreading in regular lattice');

inf_index=find(infected); % indices to infected nodes

subplot(1,2,1), fig1b=plot(x(inf_index),y(inf_index),'bo-'); set(fig1b,'MarkerFaceColor','b');

subplot(1,2,2), fig2=plot(1,1,'b'); st=sprintf('Amount of infected vs time'); hold on; plot(1:rand_countmax,rand_inf(1:rand_countmax),'r');

fig2label=title(st);

tempA=A0*diag(infected);

counter=1;

inf_count=zeros(1,N);

inf_count(1,1)=1;

while (sum(infected)<N), % repeat infection until everyone infected

new_infected=A0*infected';

infected=or(infected,new_infected'); %<--- keep ones, don't need to know how long infected

counter=counter+1;

inf_count(1,counter)=sum(infected);

inf_index=find(infected);

[xplot yplot]=gplot(tempA,xy);

tempA=A0*diag(infected);

set(fig1b,'XData',xplot,'YData',yplot);

set(fig2,'XData',1:counter,'YData',inf_count(1,1:counter));

st=sprintf('Amount of infected vs time: %d',inf_count(counter));

set(fig2label,'String',st);

drawnow;

pause(0.5);

end;

reg_inf=inf_count(1:counter);

reg_countmax=counter;

fprintf('\nSpreading takes longer, as understandable because of very long node-to-node distances.\n');

% -------------------------------------------------- 6th item: spreading in the small-world network ------------------------------

fprintf('Press any key to start spreading in small world\n');

pause

infected=zeros(1,N);

infected(1)=1; %infected=1 if infected

[xplot yplot]=gplot(A,xy);

subplot(1,2,1), hold off; fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); hold on; drawnow;

title('Spreading in small-world network');

inf_index=find(infected); % indices to infected nodes

subplot(1,2,1), fig1b=plot(x(inf_index),y(inf_index),'go-'); set(fig1b,'MarkerFaceColor','g');

subplot(1,2,2), hold off; fig2=plot(1,1,'g-'); hold on; st=sprintf('Amount of infected vs time: %d',1);

fig2label=title(st);

plot(1:reg_countmax,reg_inf(1:reg_countmax),'b'); plot(1:rand_countmax,rand_inf(1:rand_countmax),'r');

tempA=A*diag(infected);

counter=1;

inf_count=zeros(1,N);

inf_count(1,1)=1;

while (sum(infected)<N), % repeat infection until everyone infected

new_infected=A*infected';

infected=or(infected,new_infected'); infected=and(infected,infected); % <--- keep ones, don't need to know how long infected

counter=counter+1;

inf_count(1,counter)=sum(infected);

inf_index=find(infected);

[xplot yplot]=gplot(tempA,xy);

tempA=A*diag(infected);

set(fig1b,'XData',xplot,'YData',yplot);

set(fig2,'XData',1:counter,'YData',inf_count(1,1:counter));

st=sprintf('Amount of infected vs time: %d',inf_count(counter));

set(fig2label,'String',st);

drawnow;

pause(0.5);

end;

fprintf('\nDue to the shortcuts, spreading proceeds quite rapidly.\n');

fprintf('The average node-to-node distance is short in small-world networks (hence the name :-)\n');

fprintf('Thus, in terms of distance, small-world-networks resemble random networks.\n');

fprintf('\n');

fprintf('Next, the networks will be compared in terms of clustering. Networks, where neighbors of\n');

fprintf('nodes are likely to be neighbors between themselves as well are highly clustered.\n');

fprintf('This tendency is observed in e.g. social networks - your friends are likely to know\n');

fprintf('each other as well.\n');

sw_inf=inf_count(1:counter);

sw_countmax=counter;

% -------------------------------------------- 7th item: comparing random, ordered and small-world networks --------------------------

for zz=1:3,

fprintf('\nPress any key to randomly select starting points\n');

pause;

if zz==1

fprintf('\nBlue nodes are neighbors of red nodes.\n');

fprintf('Blue lines show connections between neighbors of red nodes.\n');

fprintf('(To check ordered & small-world nets, zoom in)\n');

end;

[xplot yplot]=gplot(Arand,xy);

subplot(1,3,1), hold off; fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'Color',[0.7 0.7 0.7],'MarkerFaceColor','k'); hold on; drawnow;

title('Random network');

[xplot yplot]=gplot(A0,xy);

subplot(1,3,2), hold off; fig2a=plot(xplot,yplot,'ko-'); set(fig2a,'Color',[0.7 0.7 0.7],'MarkerFaceColor','k'); hold on; drawnow;

title('Ordered network');

[xplot yplot]=gplot(A,xy);

subplot(1,3,3), hold off; fig3a=plot(xplot,yplot,'ko-'); set(fig3a,'Color',[0.7 0.7 0.7],'MarkerFaceColor','k'); hold on; drawnow;

title('Small-world network');

% ------------------------------ random node on random lattice, plot node and its neighbors

subplot(1,3,1); hold on;

N0=ceil(rand(1,1)*N);

neighs=find(Arand(N0,:));

tempxy=xy(neighs,:); tempxy(length(tempxy)+1,:)=xy(N0,:); tempA=zeros(length(tempxy),length(tempxy)); tempA(length(tempxy),:)=1;

[tempx tempy]=gplot(tempA,tempxy);

fig1d=plot(tempx,tempy,'r'); set(fig1d,'Linewidth',2); fig1b=plot(x(N0),y(N0),'ro'); set(fig1b,'MarkerFaceColor','r');

fig1c=plot(x(neighs),y(neighs),'bo'); set(fig1c,'MarkerFaceColor','b');

N0rand=N0;

neighsrand=neighs;

% ------------------------------ random node on regular lattice, plot node and its neighbors

subplot(1,3,2); hold on;

N0=ceil(rand(1,1)*N);

neighs=find(A0(N0,:));

tempxy=xy(neighs,:); tempxy(length(tempxy)+1,:)=xy(N0,:); tempA=zeros(length(tempxy),length(tempxy)); tempA(length(tempxy),:)=1;

[tempx tempy]=gplot(tempA,tempxy);

fig2d=plot(tempx,tempy,'r'); set(fig2d,'Linewidth',2); fig2b=plot(x(N0),y(N0),'ro'); set(fig2b,'MarkerFaceColor','r');

fig2c=plot(x(neighs),y(neighs),'bo'); set(fig2c,'MarkerFaceColor','b');

N0reg=N0;

neighsreg=neighs;

% ------------------------------ random node on small-world lattice, plot node and its neighbors

subplot(1,3,3); hold on;

N0=ceil(rand(1,1)*N);

neighs=find(A(N0,:));

tempxy=xy(neighs,:); tempxy(length(tempxy)+1,:)=xy(N0,:); tempA=zeros(length(tempxy),length(tempxy)); tempA(length(tempxy),:)=1;

[tempx tempy]=gplot(tempA,tempxy);

fig3d=plot(tempx,tempy,'r'); set(fig3d,'Linewidth',2); fig3b=plot(x(N0),y(N0),'ro'); set(fig3b,'MarkerFaceColor','r');

fig3c=plot(x(neighs),y(neighs),'bo'); set(fig3c,'MarkerFaceColor','b');

N0sw=N0;

neighssw=neighs;

%fprintf('Press any key to check connections between neighbors\n');

%pause;

% ------------------------------ show common neighbors in random lattice --------------------------------------

subplot(1,3,1), hold on;

ncount=0;

neighs=neighsrand; N0=N0rand;

for i=1:length(neighs),

for j=1:length(neighs),

if (i~=j) & Arand(neighs(i),neighs(j))==1 & (neighs(i)~=N0) & (neighs(j)~=N0),

fig1e=plot([x(neighs(i)) x(neighs(j))],[y(neighs(i)) y(neighs(j))],'b-');set(fig1e,'Linewidth',2);

ncount=ncount+1;

end;

ncount=ncount/2;

st=sprintf('Random network: %d pairs common neighbors',ncount);

title(st);

% ------------------------------ show common neighbors in regular lattice----------------------------------------

subplot(1,3,2), hold on;

ncount=0;

neighs=neighsreg; N0=N0reg;

for i=1:length(neighs),

for j=1:length(neighs),

if (i~=j) & A0(neighs(i),neighs(j))==1,

fig2e=plot([x(neighs(i)) x(neighs(j))],[y(neighs(i)) y(neighs(j))],'b-'); set(fig2e,'Linewidth',2);

ncount=ncount+1;

end;

ncount=ncount/2;

st=sprintf('Ordered network: %d pairs common neighbors',ncount);

title(st);

% ----------------------------- show common neighbords in small-world lattice --------------------------------------

subplot(1,3,3), hold on;

ncount=0;

neighs=neighssw; N0=N0sw;

for i=1:length(neighs),

for j=1:length(neighs),

if (i~=j) & A(neighs(i),neighs(j))==1,

fig3e=plot([x(neighs(i)) x(neighs(j))],[y(neighs(i)) y(neighs(j))],'b-'); set(fig3e,'Linewidth',3);

ncount=ncount+1;

end;

ncount=ncount/2;

st=sprintf('Small-world network: %d pairs common neighbors',ncount);

title(st);

end

fprintf('\nThis shows that random networks are not very clustered - the probability of finding\n');

fprintf('connections between neighbors of a node is low. On the other hand, ordered and small-world\n');

fprintf('networks show high degree of clustering.\n');

fprintf('\n');

fprintf('Based on the previous examples, one can conclude that small-world networks share properties\n');

fprintf('with random networks (short distances) and ordered networks (clustering). They can thus be\n');

fprintf('viewed to lie between these two extremes,\n');

fprintf('\n');

fprintf('Next, a new class of complex networks - the scale-free network.\n');

pause;

% ------------------------------ show a scale-free network onscreen ---------------------------------------------------

subplot(1,1,1);

load sfA.mat; load Acoords.txt; % load network adjancency matrix & coordinates calculated using the Pajek graph software

[xplot yplot]=gplot(sfA,Acoords);

fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k');

subplot(1,1,1); hold off;

load sfA.mat; load Acoords.txt; % load network adjancency matrix & coordinates calculated using the Pajek graph software

N=length(Acoords);

[xplot yplot]=gplot(sfA,Acoords);

fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); title('Scale-free network'); hold on;

fprintf('\nDisplayed is a scale-free network with 150 nodes, average 4 links per node.\n');

fprintf('One can see that unlike in the previous networks, scale-free networks have\n');

fprintf('more variation in the amounts of links per node. In the middle of the picture,\n');

fprintf('you can see some nodes with a high amount of connections.\n');

fprintf('\n');

fprintf('Next we will simulate spreading on such networks, to find out about the node-to-node\n');

fprintf('distances.\n');

fprintf('\nPress any key to start spreading in SF network\n');

pause,

% ------------------------------- spreading on the scale-free network -----------------------------------------

for kk=1:2,

infected=zeros(1,N); startpt=ceil(rand(1,1)*N);

infected(startpt)=1; %infected=1 if infected

inf_index=find(infected);

[xplot yplot]=gplot(sfA,Acoords);

subplot(1,2,1), fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); hold on; drawnow;

title('Spreading in scale-free network');

subplot(1,2,1), fig1b=plot(Acoords(startpt,1),Acoords(startpt,2),'mo-'); set(fig1b,'MarkerFaceColor','r');

subplot(1,2,2), fig2=plot(1,1,'m-'); st=sprintf('Amount of infected vs time'); hold on;

fig2b=plot(1:reg_countmax,reg_inf(1:reg_countmax),'b'); fig2c=plot(1:rand_countmax,rand_inf(1:rand_countmax),'r'); fig2d=plot(1:sw_countmax,sw_inf(1:sw_countmax),'g');

fig2label=title(st);

tempA=sfA*diag(infected);

counter=1;

inf_count=zeros(1,N);

inf_count(1,1)=1;

while (sum(infected)<N), % repeat infection until everyone infected

new_infected=sfA*infected';

infected=or(infected,new_infected'); infected=and(infected,infected);% <--- keep ones, don't need to know how long infected

counter=counter+1;

inf_count(1,counter)=sum(infected);

inf_index=find(infected);

[xplot yplot]=gplot(tempA,Acoords);

tempA=sfA*diag(infected);

set(fig1b,'XData',xplot,'YData',yplot);

set(fig2,'XData',1:counter,'YData',inf_count(1,1:counter));

st=sprintf('Amount of infected vs time: %d',inf_count(counter));

set(fig2label,'String',st);

drawnow;

pause(0.5);

end;

sfinf=inf_count(1:counter); %save for later use

sf_countmax=counter;

if kk==1

fprintf('Press any key to do again...\n');

pause;

end;

fprintf('\nSpreading is rapid, thus distances are short in scale-free networks .\n');

fprintf('Next, we will check the clustering properties.\n');

fprintf('\nPress any key...\n');

pause;

fprintf('\nBlue nodes are neighbors of red nodes.\n');

fprintf('Blue lines show connections between neighbors of red nodes.\n');

fprintf('(To check ordered & small-world nets, zoom in)\n');

% -------------------------------- check clustering, show common neighbors -----------------------------------

hold off; subplot(1,1,1), hold off;

fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k','Color',[0.7 0.7 0.7]); title('Scale-free network'); hold on;

totncount=0;

for kk=1:5

N0=ceil(rand(1,1)*N);

neighs=find(sfA(N0,:));

tempxy=Acoords(neighs,:); tempxy(length(tempxy)+1,:)=Acoords(N0,:); tempA=zeros(length(tempxy),length(tempxy)); tempA(length(tempxy),:)=1;

[tempx tempy]=gplot(tempA,tempxy);

fig3d=plot(tempx,tempy,'r'); set(fig3d,'Linewidth',2); fig3b=plot(Acoords(N0,1),Acoords(N0,2),'ro'); set(fig3b,'MarkerFaceColor','r');

fig3c=plot(Acoords(neighs,1),Acoords(neighs,2),'bo'); set(fig3c,'MarkerFaceColor','b');

ncount=0;

for i=1:length(neighs),

for j=1:length(neighs),

if (i~=j) & sfA(neighs(i),neighs(j))==1,

fig3e=plot([Acoords(neighs(i),1) Acoords(neighs(j),1)],[Acoords(neighs(i),2) Acoords(neighs(j),2)],'b-');

set(fig3e,'Linewidth',2);

ncount=ncount+1;

end;

ncount=ncount/2;

totncount=totncount+ncount;

st=sprintf('Pairs of common neighbors: %d',totncount); title(st);

fprintf(st); fprintf('\n');

fprintf('Press any key\n');

pause;

end;

fprintf('\nYou probably saw some connected neighbors, depending a bit on the randomly chosen nodes.\n');

fprintf('(Although, it is also possible that the choices were such that none were seen.)\n');

fprintf('Actually, scale-free networks can exhibit varying degrees of clustering - the original\n');

fprintf('so-called Barabasi-Albert networks lower, some others higher.\n');

fprintf('\n');

fprintf('Thus, SF networks resemble small worlds & random nets in terms of distances, and small worlds\n');

fprintf('and ordered networks in terms of clustering, although with sometimes lower degrees of clustering.\n');

fprintf('\n');

fprintf('Next, we analyze the numbers of links. To do this, we calculate distribution of links,\n');

fprintf('i.e. what is the probability of finding a node with k links.\n');

fprintf('\nPress any key\n');

pause;

% ------------------------------------------------------------------ plot degree distribution ---------------------------------------

hold off; subplot(1,1,1);

kmax=max(max(full(sum(sfA,2))));

pk=zeros(1,kmax);

for i=1:N,

k=full(sum(sfA(i,:)));

pk(k)=pk(k)+1;

end;

pk=pk/N;

loglog(1:kmax,pk,'ro-');

xlabel('k'); ylabel('p(k)'); title('Degree distribution on logarithmic scale'); hold on;

fprintf('\nThis is our example network. You can see that there are a few nodes with large number of links,\n');

fprintf('but the graph is a bit messy - but we used only one example network with small N.\n');

fprintf('Now, a pre-calculated degree distribution with N=150,000, averaged over 100 networks\n');

fprintf('will be shown.\n');

fprintf('\nPress any key\n');

pause;

% ---------------------------------------------- show pre-calculated distribution for large nets

load example_pk.mat;

loglog(pk150(2,:),pk150(1,:),'k');

fprintf('\nThe distribution is quite linear on log-log scale, except at the end where there is noise\n');

fprintf('due to finiteness effects. This means that there is a power law, p(k) depends on k^{-gamma},\n');

fprintf('where in this (and most cases) gamma=3.\n');

fprintf('\nThe same law is valid for all scale-free networks generated using the preferential attachment rule\n');

fprintf('explained below, regardless of size, average number of links per node, or clustering.\n');

fprintf('\n');

fprintf('Actually, these networks are not "static" - the distribution results from self-organization during\n');

fprintf('network growth. The growth process with preferential attachment rule is very simple:\n');

fprintf('When new nodes join the network, they choose to attach to nodes who already have \n');

fprintf('a large number of links with higher probability. Thus, "fit get fitter". See:\n');

fprintf('\nPress any key\n');

pause;

% ------------------------------------------------------------------ show generative mechanism

subplot(1,1,1), hold off;

fig1a=plot(Acoords(1,1),Acoords(1,2),'ko-'); set(fig1a,'MarkerFaceColor','k'); hold on; axis([0 1 0 1]);

fig1b=plot(Acoords(1,1),Acoords(1,2),'ro'); set(fig1b,'MarkerFaceColor','r');

joined=zeros(1,N);

for i=1:N,

tempA=sfA(1:i,1:i);

tempxy=Acoords(1:i,:);

[xplot yplot]=gplot(tempA,tempxy);

set(fig1a,'XData',xplot,'YData',yplot);

set(fig1b,'XData',Acoords(i,1),'YData',Acoords(i,2)); drawnow;

if i<10

plen=2;

else

if i<25 plen=1;

else

plen=0.25;

end;

pause(plen);

end;

fprintf('\nAs the final example in this demo, we will analyze the robustness of scale-free networks.\n');

fprintf('We do this by knocking out 20 percent of nodes, and again applying the spreading algorithm.\n');

fprintf('First, we knock out randomly selected 20 percent of nodes.\n');

fprintf('\nPress any key\n');

pause;

% ------------------------------------------- SF nets part II: error and attack tolerance ----------------------------

load sfA.mat; load Acoords.txt;

% load network adjancency matrix & coordinates calculated using the Pajek graph software

N=length(Acoords);

% -------------------------- take random 10% out, do spreading

howmany=ceil(N/5);

knockout=ceil(rand(1,howmany)*N);

pA=sfA; % matrix for perturbed A

for i=1:length(knockout),

pA(knockout(i),:)=0;

pA(:,knockout(i))=0;

end;

[xplot yplot]=gplot(sfA,Acoords); subplot(1,1,1), hold off;

fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); title('Full scale-free network'); hold on;

fprintf('\nThe original network.\n');

fprintf('Press any key...');

pause;

knockout_list=zeros(1,N); knockout_list(knockout)=1;

tempA=sfA*diag(knockout_list);

[xplotk yplotk]=gplot(tempA,Acoords);

%set(fig1a,'MarkerFaceColor','k','Linewidth',0.5);

title('Red nodes will be knocked out');

fig1b=plot(xplotk,yplotk,'r-'); set(fig1b,'XData',xplotk,'YData',yplotk,'Color',[1 0 0],'Linewidth',2);drawnow;

fig1c=plot(Acoords(knockout,1),Acoords(knockout,2),'ro'); set(fig1c,'MarkerFaceColor','r');

fprintf('\nThe red nodes and links will be knocked out.\n');

fprintf('Press any key...\n');

pause;

hold off;

[xplot yplot]=gplot(pA,Acoords);

fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); title('SF network with 20 percent nodes knocked out'); drawnow;

fprintf('This is what is left of the network.\n');

fprintf('Press any key to start spreading...\n');

pause;

% ------------------------------------------------ do spreading in what is left of the networks

infected=zeros(1,N);

startpt=ceil(rand(1,1)*N);

while (sum(find(knockout==startpt))>0) | (sum(full(pA(startpt,:)))==0), startpt=ceil(rand(1,1)*N); end;

infected(startpt)=1; %infected=1 if infected

inf_index=find(infected);

[xplot yplot]=gplot(pA,Acoords);

subplot(1,2,1), fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); hold on; drawnow;

title('Spreading in scale-free network');

subplot(1,2,1), fig1b=plot(Acoords(startpt,1),Acoords(startpt,2),'mo-'); set(fig1b,'MarkerFaceColor','r');

subplot(1,2,2), fig2=plot(1,1,'m-'); st=sprintf('Amount of infected vs time'); hold on;

fig2label=title(st);

tempA=pA*diag(infected);

counter=1;

inf_count=zeros(1,N);

inf_count(1,1)=1;

endsign=0;

while (endsign==0), % repeat infection until everyone infected

prev_infected=infected;

new_infected=pA*infected';

infected=or(infected,new_infected'); infected=and(infected,infected);% <--- keep ones, don't need to know how long infected

counter=counter+1;

inf_count(1,counter)=sum(infected);

inf_index=find(infected);

[xplot yplot]=gplot(tempA,Acoords);

tempA=pA*diag(infected);

set(fig1b,'XData',xplot,'YData',yplot);

set(fig2,'XData',1:counter,'YData',inf_count(1,1:counter)/(N-length(knockout)));

st=sprintf('Fraction of infected vs time: %1.2f',inf_count(counter)/(N-length(knockout)));

set(fig2label,'String',st);

drawnow;

pause(0.5);

if isequal(prev_infected,infected), endsign=1; end;

end;

ko1_inf=inf_count(1:counter)/(N-length(knockout));

ko1_countmax=counter;

fprintf('\nAlthough a large number of nodes was removed, the spreading still probably proceeded rapidly.\n');

fprintf('Also, most likely almost all nodes were eventually reached. Thus, SF networks are\n');

fprintf('very robust against random failures - a very useful property for biological and\n');

fprintf('electronic networks. If the spread failed, you were extremely unlucky.\n');

fprintf('\nNext, we will take out 20 percent of nodes, starting from the most connected node,\n');

fprintf('proceeding along the list of nodes ordered according to number of connections.\n');

fprintf('\nPress any key\n');

pause;

% ------------------------------------------------ knockout first 20 percent of nodes

k=sum(full(sfA));

[ks index]=sort(k);

index=fliplr(index); % largest first

pA=sfA;

knockout=index(1:20);

for i=1:length(knockout),

pA(index(i),:)=0;

pA(:,index(i))=0;

end;

[xplot yplot]=gplot(sfA,Acoords); subplot(1,1,1), hold off;

fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); title('Full scale-free network'); hold on;

fprintf('\nThe original network again\n');

fprintf('Press any key...\n');

pause;

knockout_list=zeros(1,N); knockout_list(knockout)=1;

tempA=sfA*diag(knockout_list);

[xplotk yplotk]=gplot(tempA,Acoords);

%set(fig1a,'MarkerFaceColor','k','Linewidth',0.5);

title('Red nodes will be knocked out');

fig1b=plot(xplotk,yplotk,'r-'); set(fig1b,'XData',xplotk,'YData',yplotk,'Color',[1 0 0],'Linewidth',2);drawnow;

fig1c=plot(Acoords(knockout,1),Acoords(knockout,2),'ro'); set(fig1c,'MarkerFaceColor','r');

fprintf('Red nodes and links will go...\n');

fprintf('Press any key...\n');

pause;

hold off;

[xplot yplot]=gplot(pA,Acoords);

fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); title('SF network with highest-degree nodes knocked out'); drawnow;

fprintf('And the damage is done.\n');

fprintf('Press any key to start spreading...\n');

pause;

% ------------------------------------------------ do spreading in what is left of the networks

infected=zeros(1,N);

startpt=ceil(rand(1,1)*N);

while (sum(find(knockout==startpt))>0) | (sum(full(pA(startpt,:)))==0), startpt=ceil(rand(1,1)*N); end;

infected(startpt)=1; %infected=1 if infected

inf_index=find(infected);

[xplot yplot]=gplot(pA,Acoords);

subplot(1,2,1), fig1a=plot(xplot,yplot,'ko-'); set(fig1a,'MarkerFaceColor','k'); hold on; drawnow;

title('Spreading in scale-free network');

subplot(1,2,1), fig1b=plot(Acoords(startpt,1),Acoords(startpt,2),'mo-'); set(fig1b,'MarkerFaceColor','r');

subplot(1,2,2), fig2=plot(1,1,'m-'); st=sprintf('Amount of infected vs time'); hold on;

fig2b=plot(1:ko1_countmax,ko1_inf(1:ko1_countmax),'k--');

fig2label=title(st);

tempA=pA*diag(infected);

counter=1;

inf_count=zeros(1,N);

inf_count(1,1)=1;

endsign=0;

while (endsign==0), % repeat infection until everyone infected

prev_infected=infected;

new_infected=pA*infected';

infected=or(infected,new_infected'); infected=and(infected,infected);% <--- keep ones, don't need to know how long infected

counter=counter+1;

inf_count(1,counter)=sum(infected);

inf_index=find(infected);

[xplot yplot]=gplot(tempA,Acoords);

tempA=pA*diag(infected);

set(fig1b,'XData',xplot,'YData',yplot);

set(fig2,'XData',1:counter,'YData',inf_count(1,1:counter)/(N-length(knockout)));

st=sprintf('Fraction of infected vs time: %1.2f',inf_count(counter)/(N-length(knockout)));

set(fig2label,'String',st);

drawnow;

pause(0.5);

if isequal(prev_infected,infected), endsign=1; end;

end;

fprintf('\nThe spreading failed to reach all nodes, and was quite slow.\n');

fprintf('The network had been broken to disconnected pieces.\n');

fprintf('Hence, one can conclude that SF networks are robust against random failures,\n');

fprintf('but much more vulnerable against targeted attacks.\n');

fprintf('\n');

fprintf('This concludes this demonstration.\n');