Prédiction des liens dans les réseaux sociaux.

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