On se donne un graphe qui représente les liens entre des pages web sur un ensemble de pages
données. Les noeuds du graphe sont les pages web et la présence d’un arc du noeud i au noeud j
indique que la page j est référencée par la page i. Soit n le nombre total de pages, le graphe est
donné par sa matrice d’adjacence Adj de taille nxn où Adj(i,j)==1 s’il existe un lien de la page i
vers la page j et Adj(i,j)==0 sinon.
Le degré d’un noeud deg(i) est le nombre d’acs partant de ce noeud.
En divisant chaque ligne de la matrice Adj par son degré on obtient une matrice sous
stochastique, Pss ou la somme en ligne vaut 0 pour les noeuds de degré nul et vaut 1 pour les
autres noeuds.
On se donne aussi un vecteur ligne, z de taille n, dont les composantes sont strictement
positives et dont la somme des composantes vaut 1.
On appelle P1 la matrice stochastique obtenue à partir de Pss en remplaçant les lignes nulles
par le vecteur ligne z. On appelle P la matrice stochatique αP1 + (1 −α)ez où α est un réel donné
0 < α < 1 et e est le vecteur colonne de taille n dont toutes les composantes valent
1.
On considère une chaîne de Markov de matrice de transition P.
Question 1Décrire le comportement de la chaîne (Xn)n∈ℕ. Pourquoi le vecteur z estappellé vecteur de téléportation.
2 Calcul du PageRank des états de la chaîne
Le PageRank des états de la chaîne de markov (qui sont les noeuds de notre graphe de pages web)
est donné par la mesure invariante π associée à la chaîne.
Question 2Que peut-on dire de π ? existence ? unicité ?
Construction et visualisation de matrices d’adjacences Adj aléatoires. Compléter le squelette de
programme qui suit:
n=10;// Nombre de pages functionshow_adj(Adj,diameters) [lhs,rhs]=argn(0); if rhs <2then diameters=30*ones(1,n);end graph=mat_2_graph(sparse(Adj),1,'node-node'); graph('node_x')=300*cos(2*%pi*(1:n)/(n+1)); graph('node_y')=300*sin(2*%pi*(1:n)/(n+1)); graph('node_name')=string([1:n]); graph('node_diam')=diameters; //graph('node_color')= 1:n; //show_graph(graph); rep=[1,1,1,1,2,2,2,2,2,2,2,2,2]; plot_graph(graph,rep); endfunction Adj=grand(n,n,'bin',1,0.2);show_adj(Adj); // Construction de la matrice de transition P // associéeà une matrice d'adjacence. // Pss: transition d'origine (Adj) // Pprim: Adj renormalizée pour les lignes renormalisables // et miseà z pour les lignes nulles. // P: matrice de google // z: vecteur de teleportation // d: vecteur vaut 1 si le degré vaut zero et 0 sinon function [P,Pss,Pprim,d,z,alpha]=google(Adj) // <A completer> endfunction [P,Pss,Pprim,d,z,alpha]=google(Adj); // verification que P est stochastique sum(P,'c')
Question 3La matrice P est stochastique mais présente le défaut d’être une matrice pleinealors que la matrice d’origine Pss était creuse. Montrer que le calcul de P′∗ x peut se faireen utilisant Pss′, d et z en préservant le caractère creux des opérations.
x=rand(n,1) y1=P'*x; y2=alpha*Pss'*x+ZZZ;// A completer ... y1-y2
Question 4Calculer le PageRank des pages du graphes en utilisant la fonction specdescicoslab. On redessine le graphe en tenant compte du PageRank pour choisir le diamètre ducercle représentant chaque noeud.
//... = spec(...) pi=ZZZ;// A completer ... xbasc();show_adj(Adj,int(300*pi));
Question 5Calculer π en utilisant la suite pk+1 = P′∗ pk.
function pi=pi_iterative() p=ones(n,1); while %tdo // A completer if norm(pn-p,%inf) <10*%epsthenbreak;end end pi=ZZZ;// A completer .... endfunction pi=pi_iterative(); clean(pi*P-pi)
Question 6Calculer π en utilisant la suite précédente mais en conservant Pss′, d et z.
function pi=pi_iterative_sparse() p=ones(n,1); // A completer ... pi=ZZZ;// A completer .... endfunction pi=pi_iterative_sparse(); clean(pi*P-pi)
3 Maximisation discrète du PageRank
On considère maintetant les m premiers états de la chaîne avec m = n∕2 et on cherche à
maximiser le PageRank des m-premières pages.
(1)
On suppose qu’on a accès aux p-premières pages (p ≤ m) et qu’on peut changer leurs liens vers les
pages m + 1,…,n. On peut donc choisir de changer la sous matrice Adj(1:p,m+1:$) de la matrice
Adj
Question 7Écrire un programme d’optimisation discret qui résoud le problème del’optimisation du pagerank (on choisira p = 2 et m = n∕2).
On cherche maintenant d’autres méthodes pour réaliser cette otpimisation de façon plus
efficace.
4 Problèmes ergodiques
On se donne un chaîne de Markov de matrice de transition P et une fonction coût r(x) on cherche
à vérifier le théorème ergodique pour une matrice P irréductible.
(2)
function y=r(x) y=x^2 endfunction n=4; P=rand(n,n) pr=sum(P,'c'); P=P ./(pr*ones(1,n)); // on suppose ici que les etats de la chaine sont 1:n
puis ergodique_markov(P)qui calcule∑xπ(x)r(x) et comparez.
function cerg=ergodique_markov_T(T,P) // A completer endfunction function [cerg,pi]=ergodique_markov(P) // A completer endfunction // test T=100000;CT=ergodique_markov_T(T,P); [c,pi]=ergodique_markov(P); c-CT
On veut vérifier maintenant que c = ∑xπ(x)r(x) s’obtient aussi en résolvant le système
linéaire:
On va vérifier en effet que c1 est un vecteur constant dont les composantes valent
c.
On verifie que (P − I) ∗ c = 0 impose à c d’être un vecteur constant.
// Le noyau de P-I est engendré par ones(n,1) [x0,K]=linsolve(P-eye(n,n),zeros(n,1));
Question 9Suivre les calculs suivants dans scicoslab et conclure.
// le projecteur spectral sur Espace propre associé a 1 Pr=ones(n,1)*pi;// [pi;pi;pi;....] A=P-eye(n,n);// A -Id S=Pr-inv(Pr-A),// Pr-A est inversible // vérifier que S*Pr et Pr*S sont nuls clean(S*Pr) clean(Pr*S) // A*w + R - c= 0 // A*c = 0 R=r((1:n)'); // vérifions que w=-S*R et c=Pr*R sont solution du systeme linaire w=-S*R; c=Pr*R; A*w+R-c A*c // Noter que w n'est pas unique, on peut rajouterà w les elts du noyau de A // Montrons inversement que c doitêtre egalà Pr*R // Pr*A est nul Pr*A // on doit donc avoir // Pr*R - Pr*c = 0 et A*c =0 // en sommant // Pr*R = (Pr-A)*c // c = (Pr-A)^-1 *Pr*R // c = (Pr-S)*Pr*R = Pr*Pr*R -S*Pr*R = Pr*R // car Pr est un projecteur Pr^2 = Pr et S*Pr = 0 clean(Pr^2-Pr) clean(S*Pr) // conclusion c doit valoir Pr*R // on le vérifie avec linsolve [x0,K]=linsolve([A,-eye(n,n);zeros(n,n),A],[R;zeros(n,1)]); // on vérifie bien que e = Pr*R
On peut donc résoudre le problème ergodique précédent en cherchant un couple (w,c) solution
de
w+c*ones(n,1)==Pw+R,
la composante c scalaire donnera la solution du problème ergodique.
On regarde un cas particulier ou la fonction coût pour un état i est donnée par
(4)
où P est la matrice de transition de la chaine et Rm est une matrice nxn donnée. On suppose aussi
que la matrice de transtion à la forme particulière d’une matrice Google.
Question 10Montrer que si w est un points fixe de l’opérateur w → αP1w + b oùbi = ∑jPi,jRmi,jalors (w,c) avec c = (1 − α) ∗ z ∗ w est solution de w + c = Pw + R.
// On le vérifie numeriquement // trouver la solution de // w = alpha*P1*w + sum(P.*Rm,'c') w=ZZZ;// A completer // calcul de c c=(1-alpha)*z*w // (w,c) solution du pb ergodique ? w+c-(P*w+sum(P .*R,'c')) // Maintenant on peut utiliser une méthode itérative
Question 11Que peut-on dire de l’opérateur w → αP1w + b ? en déduire une méthodenumérique pour calculer son point fixe.
function w=iterative_c(tol) // A completer ... endfunction w=iterative_c(10*%eps); // calcul de c c=(1-alpha)*z*w // (w,c) solution du pb ergodique ? w+c-(P*w+sum(P .*R,'c'))
5 Problèmes ergodiques et maximisation du PageRank
Soit Pν la matrice de transition obtenue pour un choix ν de redirections de liens au sein de la
matrice d’adjacence de graphe. Si on regarde un problème ergodique avec une fonction coût
r(x) = ∑jPi,jνRmi,j on sait que le coût ergidique devient
(6)
Pour un sous ensemble I de noeuds fixés et le choix Rmi,j = ξI(i) (où ξI(i) vaut 1 si i ∈ I et 0
sinon) le coût devient ∑i∈Iπiν.
Le choix Rmi,j = ξI(i) permet d’obtenir un coût ergodique qui est le pagerank de I et on a vu
dans la section précédente que le calcul du coût ergodique s’obtient aussi à partir de la solution
de
(7)
Si on cherche à maximiser le PageRank on va chercher à résoudre
(8)
On suppose qu’on a accès aux m-premières pages et qu’on peut changer leurs liens vers les
pages m + 1,…,n. On peut donc choisir de changer la sous matrice Adj(1:p,m+1:$) de la matrice
Adj.
On va implémenter un algorithme d’iterations sur les valeurs pour touver une solution à
l’équation (9).
on fixe un w0 initial
à l’étape k, on calcule le contrôle, νk qui maximise le membre droit de l’équation (9)
quand w est fixé à wk.
à l’étape k pour le controle fixé νk on cherche wk+1 solution de l’équation
(9)
On s’arrête quand l’écart entre wk+1 et wk devient sous une tolérance fixée.