% Classical PageRank in Octave - R. Perry, August 2019
%
% Connectivity: L{from} = to
%
% Fig. 7 from Paparo (DOI:10.1038/srep00444 2012)
%      1  2  3  4  5  6  7
L = { [], 1, 1, 2, 2, 3, 3 };
%
% Fig. 8 from Paparo, same as Fig. 1 from Chawla (arXiv:1905.06575 2019)
%       1,         2,  3,       4,       5, 6, 7
% L = { [2,5,6,7], [], [1,2,7], [3,5,6], 7, 3, 5 };
%
N = length(L); E = C = zeros(N,N);

% C = connectivity matrix
%
for i = 1:N
  v = L{i}; C(v,i) = 1;
end

% E = patched connectivity matrix, column sums = 1
%
for i = 1:N
  v = L{i}; s = length(v);
  if( s == 0); E(:,i) = 1/N; else; E(v,i) = 1/s; end
end

alpha = 0.85;

% Google matrix
%
G = alpha*E + ((1-alpha)/N)*ones(N,N);

% power method to find eigenvector R
%
T = rand(N,1); T /= sum(T); R = G*T; count = 1;

while (norm(R-T) > 1e-6 && count < 200); ++count; T = R; R = G*R; end

if count >= 200
  disp('did not converge')
end

R