3.1.3 Exemple pratique
Supposons que nous avons une capture d'un réseau social
constituéde 15 noeuds et 15 liens à l'instant t, tel que les
noeuds sont des personnes et les liens indiquent qu'il existe une relation
d'amitiéentre eux, comme il est illustrédans la figure 3.1 :
Chapitre 3. Les mesures : Adamic/Adar et voisins communs
30
FIGURE 3.1 - Exemple d'une capture d'un reseau social
Sur cette figure, nous cherchons à inférer les
nouveaux liens qui peuvent être apparaissent à l'instant
t' > t , pour cela nous allons calculer la
similaritéentre chaque paire non connecté, premièrement
par l'algorithme de Adamic/Adar. Les étapes d'exécution de
l'algorithme de Adamic/Adar est illustrédans la figure suivante, nous
allons détailler par la suite chaque étape :
· Etape 1 : nous construisons la matrice d'adjacence de
ce petit réseau social, tel que les lignes et les colonnes sont des
personnes et leurs intersections indiquent s'il existe une relation
d'amitiéentre eux ou non, la valeur 1 indique que ces deux personnes
sont des amis, 0 sinon. 3.1
Chapitre 3. Les mesures : Adamic/Adar et voisins communs
31
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
N
|
O
|
A
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
B
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
C
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
D
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
E
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
F
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
G
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
H
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
I
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
J
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
K
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
L
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
M
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
N
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
O
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
|
TABLE 3.1 - Représentation du réseau social par
une matrice d'adjacence
· Etape 2 : En utilisant la formule de
Adamic/Adar, on peut facilement calculer la matrice de similarité, les
intersections entre des lignes et des colonnes indiquent la
similaritéentre les deux personnes(x, y) qui ne sont pas des amis
3.2.
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
N
|
O
|
A
|
0.0
|
0.0
|
1.34
|
0.0
|
0.0
|
0.0
|
0.72
|
0.72
|
0.62
|
0.0
|
0.62
|
0.62
|
0.0
|
0.0
|
0.0
|
B
|
0.0
|
0.0
|
0.0
|
1.44
|
0.72
|
0.72
|
0.0
|
0.0
|
0.0
|
0.72
|
0.0
|
0.0
|
0.72
|
0.91
|
0.91
|
C
|
1.34
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.72
|
0.72
|
0.62
|
0.0
|
0.62
|
0.62
|
0.0
|
0.0
|
0.0
|
D
|
0.0
|
1.44
|
0.0
|
0.0
|
0.72
|
0.72
|
0.0
|
0.0
|
0.0
|
0.72
|
0.0
|
0.0
|
0.72
|
0.0
|
0.0
|
E
|
0.0
|
0.72
|
0.0
|
0.72
|
0.0
|
0.72
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
F
|
0.0
|
0.72
|
0.0
|
0.72
|
0.72
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
G
|
0.72
|
0.0
|
0.72
|
0.0
|
0.0
|
0.0
|
0.0
|
0.72
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
H
|
0.72
|
0.0
|
0.72
|
0.0
|
0.0
|
0.0
|
0.72
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
I
|
0.62
|
0.0
|
0.62
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.62
|
0.62
|
0.0
|
0.0
|
0.0
|
J
|
0.0
|
0.72
|
0.0
|
0.72
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.72
|
0.0
|
0.0
|
K
|
0.62
|
0.0
|
0.62
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.62
|
0.0
|
0.0
|
0.62
|
0.0
|
0.0
|
0.0
|
L
|
0.62
|
0.0
|
0.62
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.62
|
0.0
|
0.62
|
0.0
|
0.0
|
0.0
|
0.0
|
M
|
0.0
|
0.72
|
0.0
|
0.72
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.72
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
N
|
0.0
|
0.91
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.91
|
O
|
0.0
|
0.91
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.91
|
0.0
|
|
TABLE 3.2 - Matrice de similarité: Adamic/Adar
·
Chapitre 3. Les mesures : Adamic/Adar et voisins communs
32
Etape 3 : Nous stockons dans une liste
ordonnée de manière décroissante toutes les valeurs de
similarités obtenus à travers la matrice de
similaritéAda-mic/Adar. Puis en se basant sur le principe que plus la
similaritéest élevée plus il y a de chance pour que les
paires de noeuds soient connectés dans le futur, pour cela nous
choisissons les k premiers pairs qui ont des valeurs de similarités les
plus élevés. pour notre exemple, nous avons choisi les 5
premières paires qui ont des valeurs de similaritéles plus
élevés 3.3 :
(x,y)
|
Similarité(x,y)
|
(1,3)
|
1.44
|
(0,2)
|
1.34
|
(1,13)
|
0.91
|
(1,14)
|
0.91
|
(13,14)
|
0.91
|
(0,6)
|
0.72
|
(0,7)
|
0.72
|
(1,4)
|
0.72
|
. . .
|
. . .
|
(0,8)
|
0.62
|
. . .
|
. . .
|
(10,11)
|
0.62
|
|
TABLE 3.3 - Liste de similaritéde Adamic/Adar
· Etape 4 : nous construisons la
nouvelle matrice d'adjacence tout simplement à travers l'ancienne
matrice en ajoutant les 5 nouveaux liens choisi comme il est indiquédans
la matrice 3.4 :
Chapitre 3. Les mesures : Adamic/Adar et voisins communs
33
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
N
|
O
|
A
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
B
|
1
|
0
|
1
|
|
100
|
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
C
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
D
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
E
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
F
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
G
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
H
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
I
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
J
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
K
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
L
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
M
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
N
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
O
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
|
TABLE 3.4 - Nouvelle matrice d'adjacence aprés
l'exécution de Adamic/Adar
· Finalement, nous pouvons visualiser notre nouveau
réseau social après la prédiction sur cette figure3.2 :
FIGURE 3.2 - L'état du réseau aprés
l'exécution de Adamic/Adar
3.2 Chapitre 3. Les mesures : Adamic/Adar et voisins communs
34
La fonction de similarité: Voisins
communs
|