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
# 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()
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.]]
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")
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)
É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.
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.
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).
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]]
GCit
. Quel noeud est le plus important ?
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.