import numpy as np
from numpy.linalg import det
P = np.matrix ( [[ 0,0.5,0,0.5],[0.5,0,0.5,0],[1./3,1./3,0,1./3],[0.1,0.9,0,0]])
P

c = 0.15
I = np.identity(4)
e = np.matrix( [[ 0., 1., 0., 0. ]]).T
pi = ((I-P.T*(1-c))).I * e * c
pi

"""
Explanation: 3A.mr - Random Walk with Restart (système de recommandations)
Si la méthode de factorisation de matrices est la méthode la plus connue pour faire des recommandations, ce n'est pas la seule. L'algorithme Random Walk with Restart s'appuie sur l'exploration locale des noeuds d'un graphe et produit des résultats plus facile à intepréter.
Une des façons d'expliquer le PageRank est de modéliser Internet comme une immense chaîne de Markov. Le score PageRank correspond alors à la probabilité de rester dans un état ou un site Internet dans ce cas-là. Ce score est relié à la probabilité d'atterrir sur un site en suivant une marche aléatoire à travers les hyperliens. Et pour éviter les problèmes numériques lors du calcul, la formule fait apparaître un terme $d$ qui correspond à la probabilité qu'un surfer a de continuer son chemin ou d'aller voir ailleurs sur un site qui n'a rien à voir : il fait un bond avec une probabilité $(1-d)$. Je ne réécris pas les formules, elles sont disponibles sur Wikipedia.
Maintenant, si on considère qu'un surfeur se ballade sur Internet de façon aléatoire mais qu'au lieu d'arrêter sa marche et d'aller n'importe ou ailleurs, il revient à son point de départ. Cela revient à étudier toutes les marches aléatoires partant du même noeud. On obtient alors des probabilités de rester dans des états qui dépendent de ce point de départ qu'on utilise pour faire des recommandations Fast Random Walk with Restart and Its Applications).
Je suppose qu'on a un graphe $(G,V,E)$, $V$ pour les noeuds, $E$ pour les arcs. $P$ représente la matrice de transition d'un noeud à l'autre. La somme des coefficients sur la même ligne fait 1 : $\sum_j P_{ij}=1$. $e$ est un vecteur avec que des 0 sauf pour une coordonnées $i$ où $i$ est le noeud de départ. $c$ est la probabilité de revenir au point de départ. L'objectif est de trouver le régime transition $\pi$ qui vérifie l'équation suivante :
$$\pi=(1-c)P'\pi+ce  \Longleftrightarrow \pi = c(I-(1-c)P')^{-1}e$$
Le vecteur $\pi$ qui en résulte donne un poids à chaque noeud du graphe et c'est ce poids dont on se sert pour ordonner les recommandations. Autrement dit, si un surfeur est sur un site $i$, on lui recommandera comme autre site ceux dont le poids est le plus fort dans le vecteur $\pi$. Le tout est savoir de le calculer. Exemple, on choisit pour $P$ :
End of explanation
"""


pi = e
for i in range(0,10):
    pi = P.T * pi * (1-c) + e * c
pi

"""
Explanation: Une autre de procéder est de considérer que le vecteur $\pi$ est un point fixe de la suite : $\pi^t = (1-c)P \pi^{t-1} +ce$.
End of explanation
"""


import random
from numpy.random import multinomial

def marche_alea(P,c,i):
    marche = [ i ]
    while True:
        r = random.random()
        if r <= c: return marche
        vect = P[i,:].tolist()[0]
        i = multinomial(1,vect,size=1).tolist()[0].index(1)
        marche.append(i)

def aggregation(marches):
    count = {}
    for marche in marches:
        for i in marche : count[i] = count.get(i,0)+1.0
    s = sum( _ for _ in count.values())*1.0
    for i in count: count[i] /= s
    return [ count.get(i,0) for i in range(0,max(_ for _ in count.keys())+1) ]

marches = [ marche_alea(P,c,1) for k in range(0,1000) ]
count = aggregation(marches)
count 

"""
Explanation: On retrouve sensiblement la même chose. Une dernière façon est d'utiliser des marches aléatoires avec restart ou <i>Random Walk with Restart</i>. Mais pour ce faire, on doit générer des marches aléatoires partant de $i$ avec la probabilité de revenir au début égale à $c$.
End of explanation
"""


