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

Table des figures

1.1	Chronologie des réseaux sociaux	5
1.2	Logo de LinkedIn	6
1.3	Logo de Viadeo	6
1.4	Logo de Facebook	7
1.5	Logo de Twitter	8
1.6	Logo de Google+	9
2.1	Représentation d'un réseau social avec une matric d'adjacence . . .	13
2.2	Théorie de six degrés de séparation	15
2.3	Coefficient de clustering élevée	15
2.4	Structure en communautés	16
2.5	Distribution de degrés en loi de puissance	16
2.6	Problématique	17
3.1	Exemple d'une capture d'un reseau social	30
3.2	L'état du réseau aprés l'exécution de Adamic/Adar	33
3.3	L'état de réseau social aprés l'exécution de Common Neighbors. . .	37
3.4	Les différents types des liens : TP, FP, FN	38
4.1	L'interface de NodeXL	42
4.2	L'organigramme de l'application	43
4.3	L'interface globale de l'application	49
4.4	Capture du réseau de collaboration construite en 2011	50
4.5	Capture du réseau de collaboration construite en 2015	51

Liste des tableaux vi

4.6 Réseau social obtenu après l'exécution de la fonction : Adamic/Adar 52

4.7 Réseau social obtenu après l'exécution de la fonction : Commons

neighbors 53

4.8 Représentation graphique du rappel, précision, F-mesure et temps

d'exécution 54

vii

Liste des tableaux

2.1 Quelques caractéristiques des mesures de similaritélocale [Wp15] . 23

3.1 Représentation du réseau social par une matrice d'adjacence . . . . 31

3.2 Matrice de similarité: Adamic/Adar 31

3.3 Liste de similaritéde Adamic/Adar 32

3.4 Nouvelle matrice d'adjacence aprés l'exécution de Adamic/Adar . 33

3.5 Matrice de similarité: common Neighbors 35

3.6 Liste de similaritéde Common Neighbors 36

3.7 Nouvelle matrice d'adjacence aprés l'exécution de Common Neighbors 36

3.8 Matrice de confusion 38

4.1 Mesures de performances 54

viii

Liste des algorithmes

1	Algorithme de Adamic et Adar	45
2	Algorithme de Commons Neighbors	46
3	Construction de la nouvelle matrice d'adjacence	47
4	Précision, Rappel et F-mesure	48

ix

Introduction

ES réseaux sociaux sont omniprésents depuis l'avènement d'Internet. Ils per-Lmettent aux différents utilisateurs d'interagir en communautés et de se regrouper selon des critères qui leur sont importants.

Ces réseaux sociaux sont de différents types. Certains sont connus de tous et comptent des millions de membres. D'autres exploitent des niches moins connus et peuvent passer relativement inaperçus ou rester confidentiels, tels les réseaux d'entreprise.

Tous ces réseaux sociaux amassent de très nombreuses données : les amis, les messages, les images, la fréquence d'utilisation.. . tous ces échanges et informations sont soigneusement enregistrés. Dès lors se pose le problème de l'exploitation de cette masse d'informations.

L'analyse de ces réseaux et l'exploration de cette énorme quantitéde données peut permettre de chercher à détecter des groupes d'acteurs fortement connectés entre eux. On peut aussi prédire des caractéristiques des acteurs ou de liens entre eux. C'est ce sujet qui est au coeur de ce mémoire, oùnous nous intéressons à la prédiction des liens dans les réseaux sociaux.

Le problème de prédiction des liens dans les réseaux sociaux est un sujet central de la recherche pour l'ensemble de la théorie des réseaux sociaux. On s'intéresse souvent à la dynamique d'un réseau par rapport aux arêtes. Dans les réseaux sociaux, non seulement des nouveaux noeuds apparaissent mais aussi les interactions entre les personnes changent et il serait de savoir estimer l'état de ce réseau à un instant ultérieur.

INTRODUCTION x

L'objectif de ce travail est de présenter un état de l'art sur ce domaine et d'ef-fectuer une étude comparative entre deux algorithmes de prédiction des liens en présentant en détail les principes de chacune de ces algorithmes. Nous avons or-ganiséce mémoire en quatre chapitres, qui commenceront tous par quelques mots introductifs :

Dans LE PREMIER CHAPITRE, nous présentons des généralités sur les réseaux sociaux.

LE DEUXIÈME CHAPITRE sera consacréà un état de l'art sur l'analyse des réseaux sociaux, comment ils ont modélisé, leurs caractéristiques et indicateurs, une grande partie consacréau problème de prédiction des liens. Nous citons les différents travaux de recherches qui ont étémenés autour de ce problème, et surtout les algorithmes basésur la topologie d'un réseau social.

Dans LE TROISIÈME CHAPITRE, nous avons expérimentéles deux algorithmes qui sont basées sur la topologie d'un graphe : Adamic/Adar et Voisins Communs en donnant des exemples pour faciliter leurs compréhensions.

Dans LE QUATRIÈME CHAPITRE, nous présentons l'environnement de travail que nous avons choisi. Nous décrivons le réseau social que nous avons expérimenté, c'est un réseau de collaboration des chercheurs au sein de laboratoire de mathématiques et d'informatique de l'université»Amar Telidgi-Laghouat», ainsi l'application que nous avons développé. Puis nous présentons les résultats d'expérimentation. Nous essayons d'interpréter, comparer et juger la performance de chacune des algorithmes que nous avons abordés.

Nous concluons ce travail par une vision globale et synthétique sur le travail que nous avons fait en particulier et sur le domaine de prédiction des liens en général. Nous parlons de l'expérience que nous avons acquise à travers ce mémoire.

Nous pouvons remarquer finalement que dans ce travail, nous analysons l'effica-citédes méthodes de prédiction de liens en termes d'un ensemble de mesures. Nous n'effectuons pas une étude de complexitédes algorithmes et nous ne concentrons pas ce travail sur la meilleure façon pour implémenter ces méthodes. Les méthodes ont étéimplémentées en JAVA d'un point de vue pragmatique, sans optimiser les codes au point de vue de complexitéou de stockage des données...

1