Conclusion
Nous avons introduit dans ce chapitre l'analyse des
réseaux sociaux, parmi les méthodes d'analyse des réseaux
sociaux nous avons présentéun état de l'art qui
résume les principaux travaux qui ont étémenés
autour le problème de prédiction des liens qui est au coeur de ce
mémoire. Nous avons présentéles principales approches
existantes pour résoudre ce problème, en l'occurrence des
approches basée sur le contenu des noeuds, des approches exploitant des
propriétés topologiques du réseau et des méthodes
d'apprentissage supervisé.
Pour nos travaux, nous avons choisi deux mesures de
similaritéqui ont basésur les motifs topologique d'un
réseau social, la première mesure c'est la mesure de
Adamic et Adar et la deuxième c'est
voisins communs.
Dans le chapitre qui suit, nous allons expliquer en
détail les principes de fonctionnement de chacune de ces deux mesures de
similarité. Ensuite nous implémentons ces deux fonctions dans le
but est de faire une comparaison basée sur les résultats de cette
implémentation.
28
Chapitre 3
Les fonctions : Adamic/Adar et
voisins communs
Dans ce chapitre, nous allons présenter en
détail les principes des deux approches de prédiction des liens
que nous avons choisi, voire la mesure de similaritéAda-mic/Adar et
Voisins Communs, nous présentons des exemples simples pour bien
comprendre leur fonctionnement.
3.1 La fonction de similarité:
Adamic/Adar
3.1.1 Origine de la méthode
Cette mesure à étéproposépar
[Ada03], est une méthode d'extraction des réseaux d'amis des
universités de Stanford et du MIT, à partir des pages
personnelles des étudiants. Les étudiants de ces
universités, au moment de l'étude, avaient pour usage de mettre
des items textuels comme par exemple leurs intérêts, les groupes
ou ils appartiennent, leurs localisations géographiques, des hyperliens
de leur page personnelle vers les pages personnelles de leurs amis. Ainsi, dans
un premier temps, les auteurs démontrent que le graphe formépar
la structure en hyperliens de ces pages possède 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, un indice de simi-laritéentre les pages
personnelles est défini à partir de la co-occurrence
d'éléments textuels et de la présence d'hyperliens entre
les pages.
Les auteurs ont trouvéque deux étudiants plus
qu'ils mentionnent des items communs dans leurs pages web, plus ils sont
similaires dans leurs vie réel et donc, il existe une relation forte
entre eux. Ils ont prouvéaussi que par exemple un
Chapitre 3. Les mesures : Adamic/Adar et voisins communs
29
item commun mentionnépar deux étudiants
seulement à une similaritéplus élevéqu'un item
commun partagépar 5 étudiants, pour cela, ils ont choisi une
formule mathématique pour attribuer des poids aux items communs en
fonction du nombre de personne qu'ils les partagent, ils ont
utilisél'inverse de ln x pour attribuer des poids élevéau
items rarement partagé, par exemple un item partagépar deux
étudiants à un poids égal à 1
ln 2, un item partagépar 1000
étudiants sera égal à1
ln 1000.
| 
