Programmation en python d'une promenade aléatoire dans un graphe

Surf aléatoire dans un graphe de pages web

Principe du "surfeur aléatoire" et référencement

Dans sa toute première version, l'algorithme de référencement (ou de classement) de pages web de Google était celle dite du "surfeur aléatoire".
Avec un ensemble de pages web, on peut former un graphe: chaque page web est un sommet, et les arêtes décrivent la relation "avoir un lien vers la page".
Ce graphe n'est pas symétrique: une page peut avoir un lien vers une autre sans que cette dernière ne possède un lien réciproque vers elle.

Un exemple simple de tel graphe est le suivant, avec seulement 4 pages:

$\psset{unit=1cm,linewidth=2pt,arrowsize=9pt} \begin{pspicture}(-.3,-.3)(4.3,4.3) %\psline(0,0)(4,0)(4,4)(0,4)(0,0)(4,4) \psline{->}(0,4)(3.4,4) \psline{<->}(.55,0)(3.55,0)(4,.55)(4,3.55) \psarc{->}(5.4,-1.4){5.4}{111}{159} \psarc{->}(-1.4,5.4){5.4}{291}{339} \psarc{->}(-5.1,2){5.4}{-15}{15} \psarc{->}(5,2){5.4}{165}{195} \pscircle[fillstyle=solid,fillcolor=blue](0,4){.55}\rput(0,4){\bf\white$P1$} \pscircle[fillstyle=solid,fillcolor=blue](4,4){.55}\rput(4,4){\bf\white$P2$} \pscircle[fillstyle=solid,fillcolor=blue](4,0){.55}\rput(4,0){\bf\white$P4$} \pscircle[fillstyle=solid,fillcolor=blue](0,0){.55}\rput(0,0){\bf\white$P3$} \end{pspicture}$

Le principe du "surfeur aléatoire" est le suivant: on part d'une page, P1 par exemple, puis on se déplace au hasard sur une des pages possibles à partir de P1, ici P2 ou P3.
On recommence ensuite à partir de cette nouvelle page, au hasard vers une des nouvelles pages accessibles (P3 si on était à P2, P1 ou P2 si on était à P3).
On recommence ceci un grand nombre de fois. En fin de compte, on compte le nombre de passage sur chaque page: le plus grand score est la 1ère page au classement, puis la 2ème, …

Surfeur aléatoire en python

On utilise dans la suite le graphe précédent.
Pour chacun des pages, P1, P2, P3 et P4, on peut donner la liste des pages adjacentes.
On utilise donc logiquement des listes en python:

P1=[2,3]
P2=[3]
P3=[1,2]
P4=[2,3]

À l'aide la fonction len (pour length, longueur), on peut créer 4 variables contenant le nombre de pages adacentes à chaque sommet:

NP1=len(P1)
NP2=len(P2)
NP3=len(P3)
NP4=len(P4)

Enfin, on va utiliser quatre compteurs: c'est-à-dire quatre variables, qui valent initialement 0, et qu'on va augmenter de 1 à chaque passage par la page concernée:

c1=0
c2=0
c3=0
c4=0

et on appelle N le nombre de "sauts" d'une page à une autre, ou encore le nombre total de pages vues. Par exemple, pour commencer:

N=10

On va utiliser de l'aléatoire, et il faut donc charger, en début de programme, la bibliothèque contenant la fonction randint:

from random import randint

qui permet de tirer un nombre entier (int) au hasard (rand).
On tire alors une page au hasard à l'aide de l'intruction:

P=randint(1,4)

Le programme en lui-même est maintenant:

for i in range(N):
    if P==1:
        c1=c1+1
        j=randint(0,NP1-1)
        P=P1[j]
    elif P==2:
        c2=c2+1
        j=randint(0,NP2-1)
        P=P2[j]
    elif P==3:
        c3=c3+1
        j=randint(0,NP3-1)
        P=P3[j]
    elif P==4:
        c4=c4+1
        j=randint(0,NP4-1)
        P=P4[j]

Exercice 1

Regrouper tous les éléments de code précédents dans un même programme et bien comprendre chaque élément.
Ajouter dans ce programme une, ou des, instructions pour afficher les valeurs des compteurs c1, c2, c3 et c4.
Que vaut la somme c1+c2+c3+c4 en fin de programme ?
Exécuter ensuite ce programme pour différentes valeurs du nombre N de "sauts" (par exemple N=10, puis N=100, puis N=1000, ...) et afficher les fréquences f1=c1/N, f2=c2/N, ...
Qu'observe-t'on ? Interpréter ces résultats obtenus.

Exercice 2

On considère maintenant le graphe suivant:

$\psset{unit=1cm,linewidth=2pt,arrowsize=9pt} \begin{pspicture}(-.3,-.3)(4.3,4.3) %\psline(0,0)(4,0)(4,4)(0,4)(0,0)(4,4) \psline{->}(0,4)(3.4,4) \psline{<-}(.6,-.2)(3.4,-1.8) \psline{->}(4,-1.4)(4,3.4) \psline{<-}(7.55,-.55)(4.35,3.45) \psline{->}(7.35,3.2)(4.6,4) \psarc{->}(7.2,-6.3){5.4}{88}{120} \psarc{->}(5.,3.4){5.4}{266}{298} \psarc{->}(3,1){5.4}{-15}{15} \psarc{->}(13,1){5.4}{165}{195} \psarc{->}(5.4,-1.4){5.4}{111}{159} \psarc{->}(-1.4,5.4){5.4}{291}{339} \psarc{->}(-5.1,2){5.4}{-15}{15} \psarc{->}(5,2){5.4}{165}{195} \pscircle[fillstyle=solid,fillcolor=blue](0,4){.55} \rput(0,4){\bf\white$P1$} \pscircle[fillstyle=solid,fillcolor=blue](4,4){.55} \rput(4,4){\bf\white$P2$} \pscircle[fillstyle=solid,fillcolor=blue](4,-2){.55} \rput(4,-2){\bf\white$P4$} \pscircle[fillstyle=solid,fillcolor=blue](0,0){.55} \rput(0,0){\bf\white$P3$} \pscircle[fillstyle=solid,fillcolor=blue](8,3){.55} \rput(8,3){\bf\white$P5$} \pscircle[fillstyle=solid,fillcolor=blue](8,-1){.55} \rput(8,-1){\bf\white$P6$} \end{pspicture}$

Modifier le programme précédent pour l'adapter à cette nouvelle situation.

Extraire les liens d'une page web

La partie précédente montre comment "classer" un ensemble de pages quand on connaît le graphe qu'elles composent. Il reste à construire ce graphe.

"Lire" automatiquement une page web

Un navigateur web permet de télécharger une page à partir de son adresse, c'est-à-dire plus précisément de télécharger le fichier ou les fichiers html, et les interpréte ensuite graphiquement (avec le css, mise en page, couleurs, ...).
Tout comme un navigateur, on peut facilement télécharger une page html, avec python par exemple:

import urllib.request

myurl='http://xymaths.free.fr'

response=urllib.request.urlopen(myurl)
texte = response.read();texte=str(texte)

La variable texte contient toute la page à l'adresse myurl. Pour l'afficher, tel qu'un moteur de recherche la "voit", il suffit de faire:

print(texte)

Ce qui s'affiche alors est, à peu de choses près, la source html de la page.
La page ainsi récupérée est un sommet du graphe. Pour "explorer" et construire ce graphe, il suffit de rechercher dans cette page tous les liens. Tous ces liens se trouvent dans une balise <a> ... </a>, plus exactement l'adresse liée est indiquée exactement dans l'attribut href="..." (voir, par exemple, Écrire et concevoir une première page web).

Il suffit donc de rechercher dans le texte précédent chaque occurence du terme href et l'adresse qui suit, qui est donc un sommet adjacent du graphe.

Recherche dans un texte

La fonction find de python permet de trouver une chaîne de caractères dans un texte. La fonction retourne la position de la chaîne recherchée dans le texte, par exemple

texte="Un exemple de texte, dans le but de donner un exemple d'utilisation de la fonction find"

a=texte.find("exemple")
print(a)
a=texte.find("dans")
print(a)

affiche 3 puis 21. La fonction find ne s'occupe que de la première occurence du mot recherché, il faut donc après recommencer la recherche après celle-ci.
Si le texte recherché n'est pas trouvé, la fonction find retourne la valeur -1. Le programme suivant permet ainsi de détecter la présence d'un mot

texte="Un autre exemple de texte, pour un nouvel exemple d'utilisation de la fonction find"

mot_recherche="utilisation"

if (texte.find(mot_recherche)):
     print("le mot ", mot_recherche , " est bien dans le texte")
else: 
     print("le mot ", mot_recherche , " n'est pas dans le texte")

Extraire du texte

Un texte, ou chaîne de caractères, est une liste de caractères. On peut accéder à chaque caractère voulu grâce à sa position:

texte='Un exemple de texte, juste un exemple'

T1=texte[3:10]
print(T1)

T2=texte[0:10]
print(T2)
# identique à 
T3=texte[:10]
print(T3)

# de même on peut sélectionner jusqu'à la fin
T4=texte[21:]
print(T4)

Extraire un lien href

En combinant la fonction find et l'extraction générale du texte:

texte='Un exemple de texte, avec href="http://adresse.fr", juste un exemple'
print(texte)

a=texte.find("href")

texte2=texte[a+6:]
print(texte[a+6:])

b=texte2.find('"')

print(texte[a+6:a+6+b])

"Robot explorateur" complet

Que fait le programme suivant ? (bien sûr, ne pas hésiter à changer l'adresse url utilisée dans ce programme...).

import urllib.request

myurl='http://xymaths.free.fr'

response=urllib.request.urlopen(myurl)
texte = response.read();texte=str(texte)

end=0
url=[]
while not(end==1):
    a=texte.find("href");
    if (a==-1):
        end=1
    else: 
        s=texte[a+6:].find('"')
        url.append(texte[a+6:a+6+s])
        texte=texte[a+6+s:]

print(url)
print("Nombre de liens trouvés:",len(url))

Exercice 3

Imaginer un programme (sans forcément chercher à l'écrire en python), à partir du programme précédent, qui permet de construire le graphe complet de toutes les pages web.

Voir aussi