Admin CliCours
Analyse des réseaux sociaux : contributions à la détection des semences dans la maximisation de l’influence
Introduction générale
Dans ces dernières décennies, le réseau internet devient de plus en plus indispensable dans nos activités quotidiennes. L’explosion des réseaux sociaux, tels que Facebook, Twitter, Viadeo, Linkedin, etc. offre de nouvelles opportunités d’établir de nouveaux contacts et de partager plusieurs types d’information. Ils peuvent changer donc la nature de la communication et de l’information. On se pose un certain nombre de questions telles que : à quels contacts envoyer un message sachant que la plupart des utilisateurs ont plusieurs centaines d’amis ? Quelles pages Wikipédia faut-il lire en priorité pour en apprendre le plus possible sur un sujet donné ? Comment prévenir la propagation d’une rumeur (influence négative) ? Comment propager le plus loin possible une information (influence positive) ? Dans tous ces contextes, la propagation de l’information entre le entités et leur évolution permet de mieux appréhender le fonctionnement global des systèmes. Par la suite, des outils méthodologiques et/ou algorithmiques adaptés aux problèmes rencontrés sont proposés. La science des réseaux sociaux tient ses origines en sociologie avec des travaux datant du début du vingtième siècle mais a pris un essor nouveau ces quinze dernières années et touche la plupart des disciplines. Ainsi l’Analyse des Réseaux Sociaux (ARS) 3 attire beaucoup d’attention grâce à ses domaines d’applications variés tels que minimiser/maximiser la diffusion d’une information, identifier des acteurs centraux d’un réseau, extraire de la connaissance des réseaux (apprentissage), détecter des groupes de personnes qui partagent le même centre d’intérêt etc. Dans ces dernières décennies, le réseau 3. Social Networks Analysis Social Networks Analysis (SNA) en anglais internet devient de plus en plus indispensable dans nos activités quotidiennes. L’explosion des réseaux sociaux, tels que Facebook, Twitter, Viadeo, Linkedin, etc. offre de nouvelles opportunités d’établir de nouveaux contacts et de partager plusieurs types d’information. Ils peuvent changer donc la nature de la communication et de l’information. On se pose un certain nombre de questions telles que : à quels contacts envoyer un message sachant que la plupart des utilisateurs ont plusieurs centaines d’amis ? Quelles pages Wikipédia faut-il lire en priorité pour en apprendre le plus possible sur un sujet donné ? Comment prévenir la propagation d’un rumeur (influence négative) ? Comment propager le plus loins possible une information (influence positive) ? Dans tous ces contextes que l’information sur les relations entre entités et leur évolution permettent de mieux appréhender le fonctionnement global des systèmes. Par la suite, des outils méthodologiques et/ou algorithmiques adaptés aux problèmes rencontrés sont proposés. La science des réseaux sociaux tient ses origines en sociologie avec des travaux datant du début du vingtième siècle mais a pris un essor nouveau ces quinze dernières années et touche la plupart des disciplines. Ainsi l’ARS 4 attire beaucoup d’attention grâce à ses domaines d’applications variés tels que minimiser/maximiser la diffusion, identifier des acteurs centraux d’un réseau, extraire de la connaissance des réseaux (apprentissage), détecter des groupes de personnes qui partagent le même centre d’intérêt etc. De nombreux acteurs de la société (exemple : les entreprises, les services gouvernementaux, les journalistes et d’autres) cherchent à exploiter et analyser les réseaux sociaux à des fins diverses (exemple : analyser la réaction des consommateurs à propos de certains produits et les promouvoir, rendre visible un programme lors d’une campagne électoral, etc.). Depuis longtemps, la diffusion de l’information est observée et étudiée dans de nombreux domaines de la science : propagation des maladies [1] ou des virus informatiques [2], diffusion des innovations technologiques [3], déplacements humains [4], etc. Le phénomène de diffusion de l’information peut être défini comme l’action de propager des éléments d’information auprès d’un public, suscite depuis plusieurs années un grand intérêt au sein de la communauté scientifique. Nos travaux portent sur la maximisation de l’influence dans les réseaux sociaux. Étudier se problème revient à bien sélectionner les semences (les diffuseurs initiaux) et à avoir un modèle de diffusion optimal. Vu ces deux problématiques, nos travaux se focalisent particulièrement sur la détection des semences qui est un problème combinatoire stochastique. Il consiste à trouver un ensemble de k−individus dans le réseau social qui va maximiser l’influence sous un modèle de diffusion optimal. Il est connu sous l’expression de maximisation de l’influence. Actuellement, les thématiques dans les réseaux sociaux sont bien orientées, le nombre d’utilisateurs qui augmente exponentiellement et nous y trouvons les mêmes utilisateurs. Ces réseaux peuvent être vus comme une agrégation d’un seul réseau appelé réseau social multicouche et chacun d’eux est vu comme une couche. L’information peut circuler entre les couches via utilisateurs qui ont plusieurs comptes. Dans [5], Wang Wenjun et al. ont montré que l’influence circule facilement dans une communauté qui peuvent être vue comme une couche et toutes ces dernières comme un réseau multicouche. Le sexe, l’âge, etc [6], peuvent être des paramètres très important dans le problème de maximisation de l’influence. Chaque catégorie peut être vue comme une couche et l’ensemble forme un réseau multicouche. Dans la suite, nous parlons de réseaux sociaux monolex ou simplement réseaux sociaux. Si on a plusieurs couches, nous parlerons de réseaux sociaux multicouches. Pour la représentation des réseaux sociaux (monoplex et multicouches), nous utilisons naturellement les graphes qui jouent un rôle très important dans la modélisation de beaucoup de problèmes pratiques et théoriques. Les graphes sont utilisés comme outil de representation pour les réseaux transports, les réseaux de communications, les architectures informatiques, les médias sociaux, etc. Dans le cas des réseaux sociaux multicouches, nous avons utilisé les graphes pour chaque couche et des matrices de mappages pour identifier les mêmes individus dans les différentes couches.
Graphes et réseaux sociaux
Dans cette section, nous représentons des réseaux sociaux (monoplex et multicouches) à l’aide des graphes après avoir rappelé quelques concepts de base sur ces derniers.
Concepts de base des graphe
Dans l’analyse des réseaux sociaux, les graphes jouent un rôle très important dans leurs représentations. Ils permettent de représenter les éléments et les relations qui les Page lient. Un graphe peut être non orienté ou orienté. Dans ce manuscrit, nous parlerons simplement de graphes sauf mention expresse, nous préciserons que c’est orienté. Un graphe G = (V, E) est défini par l’ensemble fini = {v1, v2, · · · , vn} dont les éléments sont appelés sommets ou nœuds et par l’ensemble fini E = {e1, e2, · · · , em} dont les éléments sont appelés arêtes. Une arête ei ∈ E est définie par une paire non-ordonnée de sommets, appelés extrémités de ei . Si l’arête ei relie les sommets a et b, on note ab et on dira que ces sommets sont adjacents, ou incidents avec ei ou encore que l’arête ei est incidente avec les sommets a et b. Les sommets a et b sont des voisins de niveau 1 (ou simplement des voisins) l’un de l’autre. L’ensemble des voisins d’un noeud a est appelé voisinage de niveau 1 (ou simplement voisinage) de a et noté par N(a) (ou N1 (a)). Le nombre de voisins d’un sommet a est le degré de a. On appelle ordre d’un graphe, ceque l’on note par n, le nombre de sommets de G. Le nombre d’arête du graphe est noté par m. Dans le cas des graphes orientés, on parle d’arcs au lieu d’arêtes. Si ab ∈E, alors nous avons un arc dirigé du sommet a vers le sommet b. a est le prédécesseur de b qui est le successeur de a. L’ensemble des successeurs du noeud a est appelé voisinage sortant du sommet a. Le nombre de voisins sortants est le degré sortant. L’ensemble des prédécesseurs du noeud a est appelé voisinage entrant. Le nombre de voisins entrants est le degré entrant du sommet a. On appelle chaîne de G = (V, E) toute suite C alternée de sommets et d’arêtes de G = (V, E) : C = (x0, a1, x1, · · · , an, xn) telle que ∀i ∈ {1, n}, ai = (xi−1, xi) C est une chaîne de longueur n (le nombre d’arêtes) joignant x0 à xn. Dans le cas d’un graphe simple, il est inutile de préciser les arêtes et nous noterons simplement : C = (x0, x1, · · · , xn). Un graphe non vide est connexe si pour toute paire de sommets quelconques du graphe, il existe une chaîne qui les relie. Un sous-graphe de G = (V, E) connexe est appelé une composante connexe ou simplement une composante. Soit k un entier naturel non nul. Un graphe G est k−connexe si |V | k et G − X est connexe pour tout sous-ensemble de sommets X de V vérifiant |X| ≺ k. Le graphe représenté dans la figure 1.1, est connexe. Pour chaque paire de sommets qu’on choisit, on peut trouver une chaîne qui les relie. Un graphe couvrant 1 d’un graphe G, qu’on notera par SG, est un sous-graphe obtenu par suppression de quelques arêtes. Autrement dit, c’est un sous-graphe dont l’ensemble de sommets est exactement celui du graphe G et l’ensemble des arêtes est une partie de celui de de G. Si S est l’ensemble des arêtes supprimées, ce sousgraphe de G est noté G\S. Un arbre couvrant 2 de G est un graphe couvant de G qui est connexe et qui n’a pas de cycle. La figure 1.2 est un graphe couvrant de G représenté par la figure 1.1. Comme ce graphe couvrant est connexe et n’a pas de cycle alors il est un arbre couvrant de G. Un graphe couvrant est dit forêt couvrante s’il n’est pas connexe et s’il n’a pas de cycle. Une forêt peut être vue aussi comme une réunion d’arbre couvrants. Tout graphe connexe admet au moins un arbre couvrant. Si le graphe n’est pas connexe, il admet des composantes connexes qui admettent chacune un arbre couvrant et la réunion de ces derniers donne la forêt couvrante. Dans la figure 1.2, nous avons un des graphes couvrants du graphe social de la figure 1.1.Figure 1.1: Un graphe social connexe G 1. spanning graph 2. spanning tree Figure 1.2: Un graphe couvrant de G Dans le cas des graphes orientés, on parle de forte connexité dans la théorie des graphes. Cette forte connexité est définie par de la façon suivante : pour deux sommets a et b donnés, on peut trouver un chemin de a vers b. Dans nos travaux, nous utilisons les définitions suivantes : Définition 1.1 Un graphe orienté connexe par rapport à un sommet Un graphe orienté est connexe par rapport à un sommet a si est seulement si, on peut accéder à tout sommet b ∈ V − {a} en respectant l’orientation. Définition 1.2 Un graphe orienté non connexe par rapport à un sommet Un graphe orienté est non connexe par rapport à un sommet a si est seulement si il existe un sommet b ∈ V −{a} non accessible à partir de a en respectant l’orientation. Après avoir donné quelques concepts et notations sur les graphes, nous allons voir comment représenter un réseau social monoplex ou multicouche à l’aide de ces derniers.
Graphes et réseaux sociaux
Les graphes sont utilisés pour représenter des problèmes réels. En 1736, le mathématicien suisse Leonhard Euler s’intéresse au problème des ponts de Konigsberg ( [7]) »existe-t-il une promenade dans la ville prussienne de Konigsberg passant une et une seule fois par les sept ponts de la ville ? ». Il représente chaque pont par une arête et les îles par des sommets. En 1856, le mathématicien irlandais William Hamilton utilise ce modèle ( [7]) pour chercher un chemin autour du monde en passant une et une seule fois dans chaque ville. Depuis, le recours à un graphe pour représenter un système réel est devenu un outil classique des mathématiques discrètes et les propriétés des graphes ont été largement étudiées. Ils permettent de représenter et d’étudier les ensembles structurés complexes, les relations entre objets, l’évolution de systèmes dans le temps, les réseaux (informatiques, les médias sociaux, etc.). Dans cette même lancée, les réseaux sociaux représentent des utilisateurs et une ou plusieurs inter-actions entre eux. Naturellement, les graphes sont utilisés pour les représenter. Réseau social monoplex Un réseaux social monoplex, que nous noterons par Réseau Sociau Monoplex (RSM), est composé d’utilisateurs et d’une seule nature de lien entre eux. Formellement, un réseau social monoplex est représenté par un graphe étiqueté, où les sommets correspondent aux utilisateurs du service et où les liens représentent les connexions entre utilisateurs. Ce graphe social peut être orienté si le mode de connexion entre les utilisateurs du réseau social monoplex est unilatéral. Par contre, il est non orienté si le mode de connexion est bilatéral. Les sommets sont étiquetés avec les messages publiés par l’utilisateur correspondant. Un message est décrit par son auteur, son contenu et sa date de publication. Réseau social multicouche Un réseau social multicouche est composé d’un ensemble d’utilisateurs et plusieurs natures de relations entre eux. Chaque nature de relations est un réseau social monoplex qui représente une couche 3 . L’agrégation de tous ces réseaux forme un réseau 3. Layer en anglais social multicouche RSMC 4 . Supposons un RSMC composé de η natures de relations et numérotés de de 1 à η, alors pour tout k ∈ [1, …, η], Lk = (Vk, Ek) est un graphe monoplex représentant la k-ième couche où Vk est l’ensemble des utilisateurs et Ek est l’ensemble de liens entre eux. Un réseau social multicouche est la réunion de toutes les couches. Pour identifier les mêmes utilisateurs dans les différentes couches, en plus des Lk pour tout k ∈ [1, …, η], comme dans les études menées+ par Gaye Ibrahima et al. [8] et par Magnani Matteo et al. [9], nous définissons des matrices de mappage entre les différentes couches. Le réseau social multicouche, noté par RSMC, est défini par RSMC=(L1, L2, L3, · · · , Lη, MM), où MM est la réunion des matrices de mappage entre les différentes couches. Dans la figure 1.3, nous avons un graphe qui représente un réseau social avec deux natures de relations (2 couches).
Introduction |
Mots-clés :
Analyse des réseaux sociaux, graphe couvrant de maximisation, maximisation de l’influence, mesure de centralité, modèle de diffusion, niveau de voisinage, probabilité de diffusion, rétroaction, réseau social monoplex, réseau social multicouche.
Télécharger le document complet
