TP - PageRank

Le but de cette séance est d’implémenter l’algorithme de puissance itérée pour pouvoir ensuite calculer la centralité de vecteur propre dans le cas des graphes non orientés et également dans le des graphes orientés (Page Rank). Nous utiliserons le module networksx de Python.

Pour l'ensemble des graphes que nous allons manipuler dans ce TP, il faut que les sommets soient obligatoirement numéroté de $0$ à $n-1$.

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import scipy as sp
import time
import math

Quelques fonctions utiles

# Return the adjacency matrix of G as list of lists
def adjacencyMatrix(G):
    return nx.to_numpy_array(G, nodelist=range(len(G))) #nx.adjacency_matrix(G).todense()

# Return the matrix product of A and B
def multMatrix(A,B):
    return A.dot(B)

# Return the same graph as G whose vertices are relabeled from 0 to n-1
# and the mapping (old:new) names
def relabelGraph(G):
    mapping = dict(zip(G, range(0, len(G))))
    return nx.relabel_nodes(G, mapping), mapping 

# Return original name of the vertex from new name
def getOriginalName(mapping, v):
    return [k for k,u in mapping.items() if u == v][0]

# Draw the graph G. If a centrality measure is given in C, label the vertices. 
# Different layouts can be used: neato (default), fdp, patchwork, circo, ... List of layout : https://graphviz.org/docs/layouts/
def drawGraph(G,C=None,prog="neato"):
    pos=nx.nx_agraph.pygraphviz_layout(G,prog=prog) # Position of vertices
    node_size=[300 for _ in G] # default size of nodes
    with_labels=True
    if C is not None: # if a centrality measure is given, label the vertices
        with_labels=False
        labels_nodes = {v:C[v][0] for v in G}
        max_C=max(C)[0]
        node_size=[math.exp(labels_nodes[v]*7/max_C) for v in labels_nodes] # size the vertices depending on the centrality measure
        nx.draw_networkx_labels(G,pos,labels_nodes,font_size=12,font_color="black") # draw labels
    nx.draw(G,pos=pos,node_size=node_size,with_labels = with_labels) # draw graph
    plt.show() 

Quelques graphes pour faire des tests

1. Un premier exemple de graphe non orienté à 4 sommets :

G1=nx.Graph()
G1.add_edge(0,1); G1.add_edge(0,3); G1.add_edge(1,2); G1.add_edge(2,0)
print("Matrice d'adjacence du graphe G1: \n", adjacencyMatrix(G1))
drawGraph(G1)

Matrice d'adjacence du graphe G1: 
 [[0. 1. 1. 1.]
 [1. 0. 1. 0.]
 [1. 1. 0. 0.]
 [1. 0. 0. 0.]]

2. Un deuxième exemple de graphe généré aléatoirement sur le modèle Erdös-Rényi :

Rappel : Le graphe aléatoire $G_{n,p}$ construit sur le modèle Erdos-Rényi est un graphe à $n$ sommets dans lequel il existe une arête entre chaque paire de sommets avec une probabilité $p$.

Dans l'exemple suivant : $n=20$ et $p=\frac15$.

n=20; p=1/5
oriented=False
G2 = nx.generators.random_graphs.fast_gnp_random_graph(n,p,directed=oriented)
drawGraph(G2,prog="neato")

3. Un plus gros graphe : Gcit

Il s'agit d'un graphe de citations qui contient 27770 sommets et de 352807 arcs. Chaque sommet représente un article scientifique et les arcs représentent les citations : si l'article A cite l'article B, alors il y aura un arc de A vers B.

file_name="cit-HepTh.txt"
Gcit = nx.DiGraph()
with open(file_name, 'r') as data:
        for line in data:
            p = line.split(" ")       
            Gcit.add_edge(int(p[0]),int(p[1]))
Gcit,mappingGcit = relabelGraph(Gcit) 

Exercice 1

Écrire une fonction powerIteration implémentant l’algorithme de puissance itérée. Cette fonction prend en paramètre une matrice, un nombre d'itérations maximum et un réel epsilon permettant de décider de l’arrêt. Cette fonction retourne un vecteur-colonne.

À chaque étape de calcul (y compris à l'étape initiale), faites en sorte que la somme des valeurs du vecteur-colonne soit égale à 1.

Pour info : un vecteur-colonne peut être obtenu avec np.ndarray(shape=(n,1)) où $n$ est la taille du vecteur.

Exercice 2 :

Utilisez la fonction powerIteration écrite à l'exercice 1 pour calculer la centralité de vecteur propre dans le cas non orienté (utilisez le graphe G1 défini plus haut). Vous fixerez un réel epsilon permettant d’indiquer la précision du calcul. Faites appel à la fonction drawGraph pour voir le résultat de vos calculs s’afficher sur les sommets du graphe.

Exercice 3

1. Écrire une fonction matrixPageRank permettant de construire la matrice de passage du Page Rank qui nous permettra de calculer la centralité de vecteur propre dans le cas orienté . Cette fonction prend en paramètre un graphe orienté et un réel alpha correspondant au facteur de zap (dumping factor).

2. Uilisez la fonction matrixPageRank pour calculer la matrice de passage du graphe suivant (que vous devez construire auparavant), puis calculez la valeur du Page Rank de chaque sommet à l'aide de la fonction powerIteration.

La valeur du Page Rank de chaque sommet est la suivante :

[[0.31] [0.21] [0.26] [0.21]]

3. Testez votre fonction sur le graphe de citations scientifiques GCit. Quel noeud est le plus important ?

Exercice 4

Tentez d'accélérer le calcul de la matrice de passage pour accélérer le calcul du Page Rank. Pour se faire, il est possible de minimiser le nombre de multiplication de matrices (opérations qui sont très couteuses en temps de calcul) pour construire la matrice de passage.