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

Résumé

E mémoire présente une étude comparative entre deux algorithmes de prédictions Cdes liens dans les réseaux sociaux en se basant sur les motifs topologiques d'un réseau social.

Nous commençons ce mémoire par une petite introduction sur les réseaux sociaux, ensuite nous présentons une vision globale sur le domaine de l'analyse des réseaux sociaux. Enfin nous présentons un état de l'art sur les différentes techniques proposées pour résoudre le problème de prédiction des liens.

Nous nous focalisons dans ce travail sur les mesures de similarités topologique. nous avons choisi d'expérimenter les deux mesures : Adamic/Adar et voisins communs.

Nous avons implémenté, comparéet mesuréles performances de chacun de ces deux algorithmes.

Mots-clés : Analyse des réseaux sociaux, prédiction des liens dans les réseaux sociaux, mesure de similaritétopologique, Adamic/Adar, Voisins communs.

Abstract

HIS dissertation presents a comparative study between two algorithms of link Tprediction in social networks based on topological motifs of social network.

We begin this dissertation by a small introduction about social networks, then we present a global vision about social network analysis domain's. We present a state of art for different technics proposed to resolve the link prediction problem.

We focus in this work on topological mesures of similarity, we chose to experiment two mesures of simiarity : Adamic/Adar and Commons Neighbors.

We implemented, compared, mesured, the preformances of each of these two functions.

Keywords : social networks analysis, link prediction in social networks, topological mesures of similarity, Adamic/Adar, Commons Neighbors.

iii

Table des matières

Résuméi Abstract Introduction 1 Généralités sur les réseaux sociaux 1.1 Historique des réseaux sociaux 1.1.1 Panorama des réseaux sociaux 1.1.1.1 1997-2001 :les réseaux sociaux foisonnent 1.1.1.2 2002-2003 :Les réseaux sociaux envahissent la toile 1.1.1.3 Myspace 1.1.1.4 Facebook 1.2 Types des réseaux sociaux			ii ix 1 1 2 2 3 3 4 4
	1.2.1	Réseaux sociaux professionnelles	5
		1.2.1.1 LinkedIn	5
		1.2.1.2 Viadeo	6
	1.2.2	Les réseaux sociaux grands publics	7
		1.2.2.1 Facebook	7
		1.2.2.2 Twitter	7
		1.2.2.3 Google+	8
2	État de l'art		10
	2.1 Analyse des réseaux sociaux		10
	2.1.1	Définition	10
	2.1.2	Représentation d'un réseau social	11
	2.1.3	Indicateurs d'un réseau social	13
		2.1.3.1 Densité	13
		2.1.3.2 Centralité	13
	2.1.4	Caractéristiques d'un réseau social	14
		2.1.4.1 Six degrés de séparation (petit monde)	14
		2.1.4.2 Coefficient de Clustering élevé	15
		2.1.4.3 Structure en communautés	16
		2.1.4.4 Distribution de degréen loi de puissance	16
	2.2 Prédiction des liens		17
	2.2.1 Problématique		17

Table des matières iv

Bibliographie 58

2.2.2 Domaines d'applications 18

2.3 Techniques de prédiction des liens 18

2.3.1 Les approches non supervisé 19

2.3.1.1 Mesures basées sur le contenu d'un noeud 19

2.3.1.2 Mesures basées sur les motifs topologiques 20

· Mesures de similaritélocales 21

· Mesures de similaritéglobales 24

· Mesures basées sur les marches aléatoires 25

2.3.1.3 Mesures basées sur la théorie social 25

2.3.2 Méthodes basées sur l'apprentissage supervisé 26

2.3.2.1 Classification binaire 26

3 Les fonctions : Adamic/Adar et voisins communs 28

3.1 La fonction de similarité: Adamic/Adar 28

3.1.1 Origine de la méthode 28

3.1.2 Principe de la méthode 29

3.1.2.1 Calcul de la matrice de similarité 29

3.1.3 Exemple pratique 29

3.2 La fonction de similarité: Voisins communs 34

3.2.1 Origine de la méthode 34

3.2.2 Principe de la méthode 34

3.2.2.1 Calcul de la matrice de similarité 34

3.3 Mesures de performances 37

3.3.1 Le rappel 38

3.3.2 La précision 39

3.3.3 La F-mesure 39

4 Implémentation et Expérimentations 40

4.1 Environnement de travail 40

4.2 Description de l'application 42

4.2.1 Algorithmes et explications 42

4.2.1.1 Construire la matrice de Adamic et Adar 44

4.2.1.2 Construire la matrice de Commons Neighbors . . 46

4.2.1.3 Construire la nouvelle matrice d'adjacence 46

4.2.1.4 Calculer les mesures de performance 47

4.2.2 Représentation de l'application 49

4.3 Expérimentations et résultats 50

4.3.1 Interprétation des résultats 55

4.3.1.1 Point de vue temps d'exécution 55

4.3.1.2 Point de vue Rappel 55

4.3.1.3 Point de vue Précision 55

4.3.1.4 Point de vue F-mesure 56

Conclusion 57

v