4.2.1.3 Construire la nouvelle matrice d'adjacence
Comme nous avons citédans les chapitres
précédents, les algorithmes de prédiction des liens
calculent des scores selon un paramètre topologique entre chaque deux
noeuds non connecté, un score élevéindique une
probabilitéélevéque cette paire soit connectédans
le futur, en se basant sur ce principe, nous avons construit une liste contient
toutes les valeurs de similaritétrouvéaprès
l'exécution d'un tel algorithme, cette liste est ordonnée de
manière décroissante, ensuite la spécification
Chapitre 4. Implémentation et Expérimentations
47
des nouveaux liens prédit dépend seulement de
l'utilisateur, donc il a le choix sur les K premiers liens dans la
liste qui ont les valeurs de similaritéles plus élevé,
à la fin il nous reste qu'àrécupérer les indices
des ces valeurs choisi ( c'est-à-dire le pair (i, j) ) en
mettant un 1 dans la nouvelle matrice d'adjacence et ainsi de suite, nous
notons aussi que nous avons gardétous les liens qu'ils existent dans la
matrice d'adjacence en leurs mettant dans la nouvelle matrice d'adjacence[3]
:
Algorithm 3 Construction de la nouvelle matrice
d'adjacence
1: Input matrice : ancien,
similarite
2: entier K, N +-
ancien.length
3: Output matrice : nouvelle
· Stocker toutes les valeurs (6= 0) de
similarités calculés dans une liste.
· Trier la liste en ordre décroissant selon les
valeurs de similarités.
4: for i +- 1 to
N do
5: for j +- 1 to
N do
6: if ancien(i,j) = 1
then
7: nouvelle(i,j) +- 1
8: else
9:
fork+-1toKdo
10: if i = indice
i de kiéme
élément dans la liste ?
j = indice j de
kiéme élément
dans la liste then
11: nouvelle(i,j) +- 1,
nouvelle(j,i) +- 1
12: end if
13: end for
14: end if
15: end for
16: end for
4.2.1.4 Calculer les mesures de performance
Cette étape consiste à voir les
différences entre la matrice d'adjacence calculés en lui
comparant avec une nouvelle matrice d'adjacence qui représente une
capture de ce même réseau social, pour cela nous avons
utiliséles mesures que nous avons définit dans le chapitre 3 : Le
rappel, la précision et la F-mesure, pour le rappel nous avons
calculéla quantitédes liens prédit correctement sur le
nombre de tous les nouveaux liens qui sont apparut dans la nouvelle capture, la
précision indique seulement le nombre des liens prédit
correctement sur les K liens spécifiés par l'utilisateur,
finalement la F-mesure est une moyenne entre la précision et le
rappel[4] :
Chapitre 4. Implémentation et Expérimentations
48
Algorithm 4 Précision, Rappel et F-mesure
1: function
PR'EcIsIoN(avant,apres,snapshot)
2: Output : double precision
3: entier tp +- 0
4: entier fp +- 0
5: entier N +- avant.length
6: for i +- 1 to N do
7: for j +- i + 1 to N do
8: if avant(i, j) = 0 ? apres(i,
j) = 1 ? snapshot(i, j) = 1 then
9: tp +- tp + 1
10: end if
11: if avant(i, j) = 0 ? apres(i,
j) = 1 ? snapshot(i, j) = 0 then
12: fp+-fp+1
13: end if
14: end for
15: end for
16: return precision +- tp
tp+fp
17: end function
18: function
RAPPEL(avant,apres,snapshot)
19: Output : double rappel
20: entier tp +- 0
21: entier fn +- 0
22: entier N +- avant.length
23: for i +- 1 to N do
24: for j +- i + 1 to N do
25: if avant(i, j) = 0 ? apres(i,
j) = 1 ? snapshot(i, j) = 1 then
26: tp +- tp + 1
27: end if
28: if avant(i, j) = 0 ? apres(i,
j) = 0 ? snapshot(i, j) = 1 then
29: fn+-fn+1
30: end if
31: end for
32: end for
33: return rappel+- tp
tp+fn
34: end function
35: function F-MEsuRE(Precision, Rappel)
36: Output : double fmesure
37: fmesure +-
2×PR'EcIsIoN(avant,apres,snapshot)×RAPPEL(avant,apres,snapshot)
PR'EcIsIoN(avant,apres,snapshot)+RAPPEL(avant,apres,snapshot)
38: return fmesure
39: end function
Chapitre 4. Implémentation et Expérimentations
49
| 
