explication pagerank

pagerank.jl

# PageRank
# Le graphe en exemple est celui de la Q4 de l'exam 09/2015:
#
#   1 -----→ 4
#   ↑ \      ↑
#   |  `---↘ |
#   2 -----→ 3
#
# Matrice d'adjacence:
A = [ 0 1 1 0;
      0 0 1 0;
      0 0 0 1;
      1 0 0 0]

# Matrice des degrés sortants:
W = [ 2 0 0 0;
      0 1 0 0;
      0 0 1 0;
      0 0 0 1]

# La matrice inverse de W^-1
# revient à simplement inverser les valeurs de la matrice, ex 2^-1 = 1/2 etc.
# ici, Winv =   0.5 0 0 0
#                 0 1 0 0
#                 0 0 1 0
#                 0 0 0 1
Winv = W^-1
# Matrice de probabilité de transition
# multiplication de la W^-1 et A
# pour multiplier deux matrices, par ex. dim3:
# x = 1 0 0   0 1 0   (1 * 0 + 0 * 1 + 0 * 1) (1 * 1 + 0 * 1 + 0 * 0) (1 * 0 + 0 * 1 + 0 * 0)
#     0 0 1 * 1 1 1 = (0 * 0 + 0 * 1 + 1 * 1) (0 * 1 + 0 * 1 + 1 * 0) (0 * 0 + 0 * 1 + 1 * 0)
#     1 0 1   1 0 0   (1 * 0 + 0 * 1 + 1 * 1) (1 * 1 + 0 * 1 + 1 * 0) (1 * 0 + 0 * 1 + 1 * 0)
# = 0 1 0
#   1 0 0
#   1 1 0
# (voir https://commons.wikimedia.org/wiki/File:Matrix_multiplication_diagram.svg?uselang=fr)
# ici, P = 0 0.5 0.5  0
#          0   0   1  0
#          0   0   0  1
#          1   0   0  0
# donc, la probabilité de passer du noeud 1 au noeud 3 est de 0.5, celle de
# passer du noeud 4 au noeud 1 est de 1, etc.
P = Winv * A

# Il faut résoudre le système
# |P^Tx = x
# |e^Tx = 1
# P^T est la transposée de P, qui revient à faire une rotation de 90 degrés vers
# la gauche. ici, la transposée de P est  0  0  0  1
#                                       0.5  0  0  0
#                                       0.5  1  0  0
# En julia,                               0  0  1  0
PT = P' # la transposée de P

# Ici, P^Tx = x s'écrit comme ceci:
#    x1 x2 x3 x4
# |   0  0  0  1 |   | x1 |   | x1 |
# | 0.5  0  0  0 |   | x2 |   | x2 |
# | 0.5  1  0  0 | x | x3 | = | x3 |
# |   0  0  1  0 |   | x4 |   | x4 |
# On a donc le système suivant:
# / x4 = x1
# | (x1)/2 = x2
# | (x1)/2 + x2 = x3
# \ x3 = x4
# On résoud: x3 = x1 = x4 = x, x2 = y.
# / x = x
# | x/2 = y       => x = 2y
# | x/2 + y = x
# \ x = x
# Et, E^Tx = 1 s'écrit comme ceci:
# 1 = x1 + x2 + x3 + x4
# Donc, en remplaçant les variables avec l'équivalence trouvée dans le système
# précédent (y = x2 et x = x1 = x3 = x4 et x = 2y), on a:
# 3x + y = 1 => y = 1/7 et x = 2/7
# Donc, le vecteur de scores PageRank est le suivant:
# | x1 |   | 2/7 |
# | x2 |   | 1/7 |
# | x3 | = | 2/7 |
# | x4 |   | 2/7 |
# Le noeud 2 à le moins de popularité

# Pour résoudre le système en Julia:
# flemme.