%creates a coincidence matrix for a large network of size N
%each node links to two random other notes
%we then compute the pagerank vector
%the second part studies how a site with low page rank can move up by buying deterministic links from k other sites

%size of network
N=10000;

%create random coincidence matrix
A=sparse(1,1,0);
%create random links from i to j(i,1) and from i to j(i,2)
i=[1:N]';
j=1+floor(N*rand(N,2));
%construct the corresponding coincidence matrix as a sparse NxN matrix
A=sparse(j(:,1),i,0.5,N,N)+sparse(j(:,2),i,0.5,N,N);

%the randomization constant: with probability eps, we jump to a random node in the markov process
eps=0.15;

%right hand side of inhomogeneous equation --- compare class notes/wikipedia: page rank
r=eps/N*ones(N,1);

%construct matrix with diffusion and subtract identity
S=((1-eps)*A-speye(N));
%compute page rank
pr=-S\r;


%now the sore loser convinces k other bought sites 'bs' to link to him

%loser has index I
[prmax,I]=min(pr);
I

%number of bought sites
k=30;
%select randomly indices of bought sites
bs=1+floor(N*rand(k,1));
%
%at bought sites, reduce probability to go to the random sites to 1/3; then add links with probability 1/3 to site I
for l=1:k
%    A(j(bs(l),1),bs(l))=A(j(bs(l),1),bs(l))-1/6;
%    A(j(bs(l),2),bs(l))=A(j(bs(l),2),bs(l))-1/6;
  A(:,bs(l))=2/3*A(:,bs(l)); 
  A(I,bs(l))=A(I,bs(l))+1/3;
end

%construct S for new matrix
S=((1-eps)*A-speye(N));
%compute page rank for new matrix
pr1=-S\r;

%now plot the difference between the two distributions:
%  just 30 additional links in a network of 10,000 sites make the difference
figure(1);
%plot both page rank matrices
plot(i,pr,i,pr1)
figure(2);
%plot the net change in page ranks: note location I
plot(pr1-pr);
