3.2.1 Origine de la méthode
[New01] a étudiéles réseaux de
collaboration scientifique en physique et en biologie, pour cela, il a
utilisédeux bases de données bibliographiques :
1. The Los Alamos E-print Archive : est une
base de données bibliographique contient les prépublications
soumis par leurs co-auteurs.
2. Medline : est une base de donnes des
articles publiéen biologie et en médecine.
Ainsi, dans un premier temps, l'auteur démontre que le
graphe formépar la structure des noeuds qui l'ont
considérécomme des co-auteurs et les liens indiquent s'ils ont
publiéau moins un article ensemble, cette structure a les
propriétés des réseaux sociaux : »small world»,
distribution des degrés en loi de puissance, et un taux de clustering
élevé. Ensuite, son contribution est que la
probabilitéd'apparition des nouvelles collaborations entre les auteurs
qui n'ont pas encore publiéensemble augmente en fonction du nombre de
collaborateurs qu'ils ont en communs.
3.2.2 Principe de la méthode
Au lieu de considérer les réseaux de
collaboration scientifique, nous pouvons appliquer la mesure de voisins communs
sur la relation d'amitiédans notre réseau social, pour chaque
paire de noeuds (x, y) non connecté, la similaritéentre deux
personnes est tout simplement le nombre de leurs voisins communs. La fonction
CommonsNeighbors utilise une matrice d'adjacence qui représente une
capture d'un réseau social à une instant donnée ou les
lignes et les colonnes représentent des personnes. Après avoir
calculéles similarités entre toutes les paires de noeuds non
connectés de ce petit réseau social. Le résultat de la
prédiction sera tout simplement les K premières paires qui ont
les valeurs de similarités les plus élevés.
3.2.2.1 Calcul de la matrice de similarité
Cette mesure consiste à calculer le
nombre des voisins communs pour chaque pair non connectéet qui partage
un ensemble de voisins comme il est indiquédans la formule suivante :
Avec le même exemple, nous calculons la similaritéentre les
personnes à partir la matrice d'adjacence de notre réseau social,
comme nous avons indiquéprécédemment, nous avons
résumél'exécution de cette algorithme en seulement 3
étapes comme il est indiquédans la figure suivante :
·
Chapitre 3. Les mesures : Adamic/Adar et voisins communs
35
Etape 1 : c'est tout simplement la
création de la matrice d'adjacence de notre réseau social
· Etape 2 : Cette étape consiste
à calculer la similaritétopologique entre chaque paire non
connecté, la similaritédans ce cas est le nombre de voisins
communs de ce pair 3.5
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
N
|
O
|
A
|
0
|
0
|
2
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
B
|
0
|
0
|
0
|
2
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
C
|
2
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
D
|
0
|
2
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
E
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
F
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
G
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
H
|
1
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
I
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
J
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
K
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
L
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
M
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
N
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
O
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
|
TABLE 3.5 - Matrice de similarité: common Neighbors
· Etape 3 : de la même
manière, nous avons construit une liste qui contient toutes les valeurs
de similaritétrouvé, nous allons trier cette dernière en
ordre décroissant, ensuite nous choisissons les k
premières paires qui ont des valeurs de similaritémaximum,
puisque l'idée c'est plus la similaritéest
élevéentre un pair non connectéplus nous allons une forte
probabilitéque ce pairs liée dans le futur, par exemple, nous
allons choisi k = 5, c'est le même nombre des pair choisi pour
l'algorithme précédent afin de voir les différences entre
les deux algorithmes 3.6 :
Chapitre 3. Les mesures : Adamic/Adar et voisins communs
36
TABLE 3.7 - Nouvelle matrice d'adjacence aprés
l'exécution de Common Neigh-
bors
(x,y)
|
Similarité(x,y)
|
(0,2)
|
2
|
(1,3)
|
2
|
(0,6)
|
1
|
(0,7)
|
1
|
(0,8)
|
1
|
(0,10)
|
1
|
(0,11)
|
1
|
(1,4)
|
1
|
. . .
|
. . .
|
(3,12)
|
1
|
. . .
|
. . .
|
(13,14)
|
1
|
|
TABLE 3.6 - Liste de similaritéde Common Neighbors
· voici la nouvelle matrice d'adjacence de ce réseau
social 3.7 :
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
N
|
O
|
A
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
B
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
0
|
0
|
0
|
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
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
H
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
I
|
1
|
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
|
|
·
Chapitre 3. Les mesures : Adamic/Adar et voisins communs
37
Finalement, nous pouvons visualiser notre nouvelle état du
réseau social après la prédiction sur cette figure 3.3
:
FIGURE 3.3 - L'état de réseau social aprés
l'exécution de Common Neighbors
| 
