%              GOOGLE.M
%
%  Berechnung des PageRanks
%  
%
% J. Lunze
%
% 29.12.2016
% für 3. Auflage: 5.1.2017
% für 4. Auflage: 12.1.2025
%
%  A = Adjazenzmatrix des Graphen
%  G = Matrix der Zustandsübergangswahrscheinlichkeiten der Markovkette
%  ("lonely surfer model")
%
clear
close all
A1=[0 1 1 0 1;
    1 0 0 0 0
    1 0 0 1 0
    0 0 1 0 0
    1 0 0 0 0];
G1=A1*inv(diag(sum(A1')));
%
[V, D]=eig(G1-eye(size(G1)));
[M,imax]=max(diag(D));
v=V(:,imax);
pquer=v/sum(v)
%
A2=[0 1 1 0 1;
    1 0 0 0 0
    1 0 0 1 0
    0 0 1 0 1
    1 0 0 0 0];
G2=A2*inv(diag(sum(A2')));
%
[V, D]=eig(G2-eye(size(G2)));
[M,imax]=max(diag(D));
v=V(:,imax);
pquer=v/sum(v)
%
A3=[0 1 1 0 1;
    1 0 0 0 0
    1 0 0 1 0
    0 1 1 0 1
    1 0 0 0 0];
G3=A3*inv(diag(sum(A3')));
%
[V, D]=eig(G3-eye(size(G3)));
[M,imax]=max(diag(D));
v=V(:,imax);
pquer=v/sum(v)
%
A4=[0 0 1 0 0 0 0 0
    0 0 1 0 0 0 0 0
    1 1 0 1 0 0 0 0
    0 0 1 0 1 1 1 1
    0 0 0 1 0 0 0 0
    0 0 0 1 0 0 0 0
    0 0 0 1 0 0 0 0
    0 0 0 1 0 0 0 0];
G4=A4*inv(diag(sum(A4')));
alpha=0.02;
for k1=1:length(G4)
    for k2=1:length(G4)
        G4(k1,k2)=G4(k1,k2)-G4(k1,k2)*alpha;
    end
end
G4=G4+diag(alpha*ones(8,1));
%
[V, D]=eig(G4-eye(size(G4)));
[M,imax]=max(diag(D));
v=V(:,imax);
pquer=v/sum(v)


%%   ... mit zufälligen Sprüngen auf andere Seiten  (Prob=m)
%
figure(1)
subplot(2,1,1);
m=0.15
N1=length(G4);
M4=(1-m)*G4+m/N1*ones(N1,N1);
[V, D]=eig(M4-eye(N1,N1));
[M,imax]=max(diag(D));
v=V(:,imax);
pquer=v/sum(v)
%
k1=0;
P=[];
Prob=[0:0.051:1, 1];   % bei Schritteweise 0.05 entsteht falsches Ergebnis für m=0.15
for m=Prob
    M4=(1-m)*G4+m/N1*ones(N1,N1);
    [V, D]=eig(M4-eye(N1,N1));
    [M,imax]=max(diag(D));
    v=V(:,imax);
    k1=k1+1;
    P(k1,:)=v/sum(v);
end
for k2=1:length(M4)
    plot(Prob, P(:,k2),'b')
    hold on
end
plot([0.15 0.15],[1 0],'k:');
latexxlabel('$$m$$');
xticks([0 0.15 0.5 1]);
latexylabel('$$\bar{p}_i$$');
rotateY;
yticks([0.1 0.3]);
axis([0, 1, 0, 0.37]);

%%
epsfigc('Google');