Détection et suivi de l'évolution de communautés ego-centrées dans les réseaux sociaux dynamiques

Résumé

Le développement des réseaux sociaux en ligne a donné naissance à plusieurs opportunités permettant de communiquer, d'accéder et de partager de l'information de n'importe où et à n'importe quel moment. Par exemple, les applications sociales telles que Facebook, Viber, WhatsApp, Imo, Line, entre autres, permettent de faire connaissance avec des amis et de discuter avec eux via des photos, des vidéos ou encore par messagerie instantanée. Les données collectées à partir de ces applications intègrent le temps et la position géographique à partir desquels les messages ont été envoyés et/ou reçus. De ce fait, il serait intéressant de construire à partir de ces données un graphe social dont les nœuds représentent les individus et les liens leur relations. L'expansion des réseaux sociaux en ligne s'est accompagnée d'un développement remarquable de l'Analyse des Réseaux Sociaux (ARS), qui est un processus d'exploration de réseaux visant à identifier des caractéristiques et d'en exploiter les informations. La détection de communautés est l'une des thématiques principales de l'ARS qui attirent de plus en plus l'attention de nombreux chercheurs. Les premiers travaux relatifs à la détection de communautés se limitaient aux communautés statiques. Avec le temps, la dimension temporelle qui désigne l'évolution de communautés a été ajoutée pour pouvoir gérer l'aspect dynamique des réseaux sociaux actuels. En effet, la majorité des travaux existants cherchent à partitionner un réseau en plusieurs communautés « globales » et suivre leur évolution au fil du temps. L'inconvénient principale de cette approche est qu'elle nécessite l'état global du réseau. Or, il est souvent difficile d'obtenir un réseau dynamique dans sa globalité. Une autre approche consiste à détecter les communautés « locales » qui sont construites à partir de certains nœuds spécifiques, appelés « nœuds d'intérêt ». Une extension de communautés locales est appelée « communautés ego-centrées » et constitue le contexte d'étude de cette thèse. En effet, contrairement aux communautés locales, celles ego-centrées sont construites sur la base d'un voisinage direct ou indirect du nœud d'intérêt. Ainsi, elles permettent, entre autres, de mieux comprendre les relations établies entre le nœud d'intérêt et ses voisins directs et indirects. Même si la longueur du voisinage constitue un atout de communautés ego-centrées, les travaux existants se limitent encore au voisinage direct lors de la détection de communautés. De plus, les solutions existantes ne prennent pas en compte les communautés ego-centrées dynamiques. L'objectif de cette thèse est de pallier à ces manquements dans l'étude des communautés égo-centrées. Pour ce faire, nous avons proposé une solution de détection de communautés dynamiques qui fonctionne en trois étapes, à savoir : 1.Faire plusieurs captures du réseau dynamique à des instants précis. Chaque capture représente l'état du réseau dynamique au cours d'une période donnée ; 2.Proposer et appliquer un algorithme de détection de communautés statiques sur chaque capture en vue de découvrir des communautés égo-centrées ; 3.Prendre la structure d'une communauté égo-centrée sur deux instantanés successifs et vérifier s'il y a eu des changements majeurs. Pour interpréter la nature des changements possibles, nous avons défini des règles de correspondance. Ainsi, au fil du temps nous établissons la manière d'évolution des différentes communautés. Nous avons implémenté notre solution avec une pile d'outils dédiés à l'ARS et nous avons utilisé trois jeux de données. Les résultats d'expérimentation ont montré la faisabilité de notre solution, ses gains et son efficacité.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 3

Téléchargements : 0