% Illustrates the Google page rank example for the tiny web in NCM

clear all
close all
% Define the connectivity matrix G in sparse matrix format
i = [ 2 6 3 4 4 5 6 1 1];
j = [ 1 1 2 2 3 3 3 4 6];
n = 6;
G = sparse(i,j,1,n,n);
disp('The connectivity matrix G is:')
disp(full(G))

p = 0.85;   % probability to follow existing links
c = sum(G);   % column sums of G
k = find(c~=0);   % find indices of nonzero columns
D = sparse(k,k,1./c(k),n,n);   % to scale columns of G by their sum
G = p*G*D;   % connectivity matrix scaled by p and column sums
z = ((1-p)*(c~=0) + (c==0))/n;   % delta = (1-p)/n,  if c~=0,
                                 %       = 1/n,      if c=0
                                 % a row vector
e = ones(n,1);   % column vector of all ones
disp('The transition matrix A is:')
disp(G + e*z)

% Do power iteration to find eigenvector for largest eigenvalue (lambda=1)
x_old = e/n;   % initial guess for x
for l=1:50
    x = G*x_old + e*(z*x_old);    % for Ax = x <=> (G + e*z)*x = x
    x = x/sum(x);   % normalize so that sum(x) = 1
    if norm(x-x_old) < 0.0001 break; end   % stop if no significant change
    x_old = x;
    l = l+1;   % counter 
end
disp(sprintf('After %d iterations of the power method the Google page rank is',l))
disp(x)

% Use pagerank.m from NCM to display the Google statistics
disp('Press a key to get the Google statistics via pagerank.m:')
pause
% URLs of webpages in our tiny web
U = {'http://www.alpha.com'
'http://www.beta.com'
'http://www.gamma.com'
'http://www.delta.com'
'http://www.rho.com'
'http://www.sigma.com'};
pagerank(U,G);
