WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

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

( Télécharger le fichier original )
par Oussama Rouane
Amar Telidgi - Laghouat - Master en systèmes dà¢â‚¬â„¢information et de décision 2015
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

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

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Tu supportes des injustices; Consoles-toi, le vrai malheur est d'en faire"   Démocrite