Phénomènes de diffusion dans les réseaux sociaux dynamiques

Télécharger le fichier pdf d’un mémoire de fin d’études

Structures et modèles de génération

L’étude détaillée des propriétés structurelles de très grands réseaux a permis de mettre en évidence les structures topologiques particulières communes aux réseaux du monde réel. De nombreux travaux récents ont en eﬀet montré qu’au-delà de leur diﬀérence sémantique, la plupart des réseaux issus du monde réel sont caractérisés par des propriétés topologiques analogues telles qu’une distribution des degrés qui suit une loi de puissance, une distance moyenne relativement faible ou la présence de communautés. Ces caractéristiques sont radi-calement diﬀérentes des celles observées classiquement sur des réseaux réguliers ou aléatoires étudiés traditionnellement dans le domaine de la théorie des graphes.
Intéressons-nous aux quatre types de structure identifiés et aux modèles permettant leur génération.
Réseaux réguliers
Les structures régulières sont les structures de réseau les plus simples, souvent utilisées dans des modèles d’automates cellulaires. Dans un réseau régulier, chaque noeud possède un nombre identique de liaisons. La densité du réseau est souvent faible, alors que le coeﬃcient de clustering est, lui, relativement élevé. Il est d’ailleurs intéressant d’observer que comme la structure est régulière, le coeﬃcient de clustering ne varie pas avec la taille du réseau. Enfin, la distance moyenne dans ces réseaux est souvent élevée, puisque la structure ne présente pas de « ponts » permettant de relier des individus fortement éloignés.
Il y a plusieurs façons d’obtenir de tels réseaux. L’une des plus simples consiste à disposer les noeuds équitablement sur un cercle et à créer, pour chaque noeud, des connexions avec les x premiers noeuds situés à gauche et à droite de sa position. Naturellement, pour garantir une structure régulière, x doit être identique pour tous les noeuds vi du réseau. Ainsi, ∀vi ∈ V , kvi = 2 × x.
Dans un tel réseau, la distribution des degrés est donc définie en un seul point k = 2 × x, tel que P (k) = 1.
Bien que ce type de structure s’observe en réalité très peu dans la nature, elle est en revanche souvent utilisée comme base pour la formation de réseaux plus réalistes.
Réseaux aléatoires
Le terme de réseaux aléatoires fait référence à des structures au sein desquelles l’exis-tence d’un lien entre deux noeuds est le résultat d’un processus aléatoire. Un réseau aléatoire se caractérise par une distribution des degrés dite « homogène », c’est-à-dire une loi de pois-son en forme de cloche. Cela traduit le fait que dans le réseau, une forte proportion de noeuds est moyennement connectée, alors qu’une plus faible proportion est fortement et faiblement connectée. On observe également que les réseaux aléatoires ont des distances moyennes relativement faibles. Cela s’explique par le fait que quand des liens sont créés aléatoirement entre des noeuds, la probabilité qu’un noeud se retrouve isolé des autres est plutôt faible.
Le modèle de génération de réseaux aléatoires le plus connu est celui proposé par Erdos et Rényi [Erdos 1960]. Dans le modèle Erdos-Rényi, chaque lien potentiel du réseau est créé avec une probabilité p, indépendante de l’existence des autres liens. Autrement dit, chaque couple de noeuds (vi, vj ) a une probabilité p d’exister dans le réseau.
Une variante de ce modèle consiste à choisir uniformément au hasard un réseau G dans l’ensemble de tous les réseaux possibles contenant N noeuds.
Bien que les réseaux aléatoires aient été l’objet de recherches intensives, ce type de structure ne reproduit pas totalement les caractéristiques observées dans les réseaux du monde réel. Barabasi et Bonabeau [Barabasi 2003] expliquent par exemple que « malgré le placement aléatoire des liens, la plupart des noeuds ont environ le même nombre de connexions. En eﬀet, dans un réseau aléatoire, les degrés suivent une distribution de Poisson avec une forme de cloche et il est extrêmement rare de trouver des noeuds qui ont, de manière significative, plus ou moins de liens que la moyenne ».
Réseaux petit-monde
Un réseau petit-monde désigne à l’origine une structure dans laquelle les chemins entre deux noeuds quelconques sont généralement très courts, c’est-à-dire que la distance moyenne dans le réseau est relativement faible. Ce concept a notamment été mis en évidence par la célèbre expérience de Milgram [Milgram 1967] (détaillée dans la section suivante), qui montra que le nombre d’intermédiaires nécessaires pour atteindre deux individus dans un réseau était d’environ 6. Aujourd’hui un réseau de type petit-monde est caractérisé par deux propriétés : une distance moyenne relativement faible dans le réseau et un coeﬃcient de clustering élevé.
Les premiers travaux à s’intéresser à la génération de réseaux petit-monde sont ceux de Watts et Strogatz [Watts 1998], qui ont proposé un modèle de génération simple, connu sous le nom de modèle Watts-Strogatz et basé sur l’extension d’un réseau régulier.
Comme illustrée sur la Figure 2.4, la procédure est la suivante. (1) Un réseau régulier est généré selon la méthode présentée précédemment. (2) Chaque lien subit ensuite un processus de réécriture selon une probabilité pr. La procédure de réécriture consiste à remplacer un lien (vi, vj ) par (vi, vk) avec k choisi aléatoirement, tel que k = i et (vi, vk) E.

Réseaux complexes et réseaux sociaux

Comme nous l’avons expliqué précédemment, les réseaux du monde réel peuvent être caractérisés par diﬀérents types de structure. D’une façon générale, le terme de réseau com-plexe [Albert 2002, Boccaletti 2006] est utilisé pour faire référence aux réseaux dont l’évolu-tion conduit à l’émergence de propriétés structurelles non-triviales, telles qu’une structure petit-monde, scale-free, ou même les deux à la fois.
Les réseaux complexes sont généralement identifiés comme une sous-classe des systèmes complexes. En eﬀet, un système complexe est en particulier un système dans lequel les interactions d’un ensemble d’entités conduisent à l’émergence d’un comportement global qui ne peut pas être déduit de leur comportement individuel. Ainsi, la « complexité » des réseaux ne tient pas tant de la structure en elle-même (nous avons d’ailleurs pu observer que la génération des telles structures était relativement aisée), mais vient plutôt des diﬃcultés qu’on rencontre à expliquer l’émergence de ces structures particulières quand on s’intéresse uniquement aux comportements individuels.
De notre point de vue, l’une des notions les plus ambiguës aujourd’hui dans la littéra-ture sur les réseaux concerne le terme de réseau social.
D’un côté, l’intuition voudrait qu’un réseau social ne fasse référence qu’à un réseau possé-dant une sémantique sociale, c’est-à-dire des réseaux d’individus ou d’animaux liés entre eux par un ensemble de relations de natures sociales : amitiés, travail, activité commune, échange et partage, relations intimes, lien de parenté, etc.
D’un autre côté, on observe que par abus de langage, ce terme est aujourd’hui associé aux sites communautaires tels que Facebook, Twitter ou Google+.
Enfin, dans le domaine de la recherche, ce terme semble parfois être utilisé en lieu et place de « réseaux complexes », comme en témoigne par exemple le domaine dit de « l’analyse des réseaux sociaux « , mais qui trouve en réalité des applications sur des réseaux de natures très diﬀérentes tels que des infrastructures matérielles de communication [Daly 2007].
Revenons sur l’évolution de la notion de « réseau social « . Ce terme a été introduit pour la première fois en 1954, dans le domaine des sciences sociales, par un article de l’anthropologue J. A. Barnes [Barnes 1954] pour désigner un ensemble de relations entre des individus. L’objectif de Barnes était de rendre compte de l’organisation sociale d’une petite communauté, à travers l’analyse de l’ensemble des relations que ses membres entretenaient les uns avec les autres : connaissances, amis, voisins ou parents. Cette notion s’est ensuite largement répandue à l’intérieur des sciences sociales telles que l’anthropologie, la sociologie, la psychologie sociale ou l’économie, en trouvant une interprétation mathématique à travers la théorie des graphes et en donnant ainsi naissance au domaine de l’analyse des réseaux sociaux, domaine précurseur de la science des réseaux actuelle.
Aujourd’hui, il est couramment observé que de nombreux réseaux sociaux (réseaux d’amitiés, réseau technologique, réseau de collaboration, réseaux professionnels, etc.) sont également des réseaux complexes [Albert 2002, Newman 2003, Borner 2007].
Dans ce mémoire, les réseaux auxquels nous nous intéressons sont toujours des réseaux sociaux, dans le sens où, qu’ils soient générés ou non, ils sont assimilables à un ensemble d’interactions sociales entre des agents et présentent pour la plupart des propriétés struc-turelles caractéristiques.

Exploitation des données : Analyse et fouille de don-nées sociales

Les données sociales font référence à toutes les données qui représentent l’activité sur un réseau social. Deux grandes familles de méthodes d’analyse de ces données peuvent être distinguées. Les méthodes traditionnelles, qui s’appuient uniquement sur des propriétés structurelles locales ou globales pour caractériser les noeuds et la structure, et les méthodes d’extraction de connaissances qui appliquent les principes de la fouille de données aux réseaux sociaux.
La Section 2.2.1 s’intéresse aux méthodes d’analyse traditionnelle et la Section 2.2.2 présente le domaine de la fouille de données sociales, ou « social mining », ainsi que les tâches associées.

Premières approches

L’analyse traditionnelle des réseaux sociaux a eu recours aux méthodes qui exploitent uniquement les propriétés structurelles des réseaux, obtenues à partir des indicateurs pré-sentés en Section 2.1.3, pour hiérarchiser ou classifier les noeuds, identifier leur position et leur rôle, détecter des situations ou des configurations particulières, étudier la struc-ture dans laquelle évolue les noeuds, etc. Parmi les travaux les plus populaires, qui ont suscité l’engouement pour l’analyse des réseaux sociaux, nous pouvons citer des exemples relativement anciens comme (i) l’analyse menée par Bott [Bott 1957] sur les familles/
(ii) l’expérience conduite par Milgram [Milgram 1967] sur l’eﬀet petit-monde, que nous présentons ci-dessous.
(i) Répartition des tâches domestiques. Élizabeth Bott est une psychologue canadienne qui a publié en 1957 une étude sur les relations au sein de diﬀérentes fa-milles [Bott 1957]. Elle a proposé une “approche relationnelle” de la famille, selon laquelle toute famille s’insère dans un réseau social qui comprend à la fois des relations entre ses diﬀérents membres, et des relations avec des personnes extérieures. L’objectif était d’établir une corrélation entre la structure du réseau interne, et celle du réseau externe.
Dans son étude, elle s’est intéressée à un échantillon d’une vingtaine de familles londo-niennes, dont elle décrit les relations entre époux, entre parents et enfants, et entre les membres de la famille et des personnes extérieures. Elle a distingué ainsi deux catégories de famille : soit le couple assume des tâches domestiques séparées, soit les activités sont eﬀectuées ensemble par les conjoints. En étudiant la densité des réseaux impliqués, elle a mis en évidence une corrélation directe entre les relations avec l’extérieur et la répartition des tâches domestiques. En eﬀet, Bott observe que les familles qui ont des réseaux de re-lations avec l’extérieur les plus denses sont celles qui adoptent le plus souvent des tâches domestiques distinctes. De cette observation naîtra la célèbre hypothèse de Bott « le degré de séparation des tâches entre mari et femme varie dans le même sens que la densité du réseau ».
En somme, cette étude a pu montrer que le taux de répartition des activités domestiques croît avec la densité du réseau externe. Ce travail est particulièrement intéressant, car des comportements individuels ont pu être mis en évidence à partir de mesures très simples.
(ii) Expérience du petit monde. Plus populaire cette fois, l’expérience dite du “petit monde” [Milgram 1967] proposée par le psycho-sociologue Stanley Milgram en 1967, a pour objectif d’étudier l’hypothèse “des six degrés de séparation”, selon laquelle toute personne sur la planète peut être en contact avec n’importe quelle autre, au travers d’une chaine relationnelle comprenant au plus six individus.
Pour étudier cette hypothèse, Milgram a élaboré une expérience qui visait à calculer le nombre moyen de liens qui séparent une personne de n’importe quelle autre. L’expérience suggère que deux personnes, choisies au hasard parmi les citoyens américains, sont reliées en moyenne par une chaîne de six relations (voir Figure 2.6). Milgram a ainsi envoyé 60 lettres à des recrues de la ville d’Omaha dans le Nebraska. L’expérience consistait pour chacun des participants à faire passer la lettre à des connaissances personnelles, qu’il pensait être capables de faire parvenir directement ou indirectement la lettre à son destinataire.
Bien que de nombreux facteurs soient en mesure de modifier les résultats de l’expérience (groupes ethniques, statut social, catégorie socio-professionnelle, etc.), Milgram confirma l’hypothèse des six degrés de séparation en constatant qu’en moyenne cinq à sept intermé-diaires furent nécessaires pour acheminer correctement les lettres. Milgram montra donc que la distance moyenne séparant deux individus était d’environ 6.
L’eﬀet petit-monde est aujourd’hui couramment observé sur les réseaux du monde réel. Les travaux plus récents sont basés sur ce même principe, c’est-à-dire le calcul de diverses propriétés structurelles pour mettre en évidence des caractéristiques des noeuds ou de la structure. Typiquement, l’une des tâches les plus couramment abordées est celle qui consiste
à classer les noeuds d’un réseau selon leur importance ou leur centralité. Par exemple, la méthode PageRank [Brin 1998] utilisée par le moteur de recherche Google, permet de classer les sites web en mesurant leur popularité.
D’autres mesures ont également été proposées, telles que le degré de centralité, qui permet d’identifier les noeuds les plus actifs, la centralité d’intermédiarité, qui mesure combien de fois un noeud se trouve sur les chemins géodésiques de tous les autres couples de noeuds, ou la centralité de proximité, qui identifie les noeuds les plus rapidement joignables.
Des travaux similaires ont également trouvé des applications dans le domaine de la diﬀusion de maladies. Par exemple, Christley et al. [Christley 2005] comparent plusieurs mesures pour déterminer celles qui caractérisent le mieux les individus à risque.

Fouille de données sociales

Les méthodes traditionnelles de fouille de données reposent sur l’hypothèse implicite selon laquelle les données sont indépendantes et identiquement distribuées (IID). En eﬀet, les jeux de données classiques correspondent le plus souvent à des collections de n-uplets mutuellement indépendants. Pourtant, si cette restriction s’avère être cohérente au regard du problème classique d’inférence statistique, elle ignore toutefois l’influence des interac-tions entre entités dans les phénomènes étudiés.
Ainsi, l’un des défis de la recherche dans le domaine de l’étude des réseaux est de propo-ser de nouveaux algorithmes, ou adaptations d’algorithmes existants, capables d’extraire eﬃcacement de la connaissance à partir de données sociales.
Getoor et Diehl [Getoor 2005] définissent la fouille de réseaux sociaux, comme « l’en-semble des techniques de data mining qui considèrent explicitement les liens lors de la construction de modèles descriptifs ou prédictifs à partir de données relationnelles ». Ainsi, la fouille de données sociales aborde quatre grandes tâches que nous détaillons ci-après :
(i) la classification des noeuds, (ii) l’identification de groupes, (iii) la prédiction de liens et
(iv) la recherche de motifs fréquents.
(i) La classification basée sur les liens regroupe les méthodes qui se donnent pour objectif d’aﬀecter à chaque noeud du réseau une classe. Contrairement aux méthodes traditionnelles qui se basent uniquement sur les valeurs des attributs, les méthodes de classification basées sur les liens prédisent la classe d’un noeud en intégrant les informations connues sur les noeuds, mais également sur la structure du réseau [Lu 2003]. La diﬃculté vient ici du fait que les classes des noeuds connectés tendent souvent à être corrélées. Les algorithmes doivent pouvoir tenir compte de ces corrélations.
La classification de pages WEB est un des exemples les plus représentatif de ce problème. L’objectif est de prédire la catégorie d’une page selon la fréquence des mots présents sur la page et celle des autres pages liées. La structure de ce réseau est aisément obtenue en analysant les liens hypertextes.
(ii) L’identification de groupes, ou clustering sur les noeuds, fait référence à une famille de méthodes qui a pour objectif d’identifier des groupes de noeuds qui partagent des caractéristiques communes. Dans le contexte des réseaux, les groupes sont souvent définis comme des amas de noeuds densément connectés ; on parle également de commu-nautés [Fortunato 2009, Combe 2012]. Nous revenons sur ces méthodes au Chapitre 5, car elles sont en relation avec la problématique que nous abordons.
D’un point de vue pratique, ces méthodes apportent des informations pertinentes sur l’or-ganisation de la structure du réseau. Typiquement, sur des réseaux sociaux en ligne, ces méthodes permettent d’identifier les diﬀérentes communautés d’utilisateurs. Cette informa-tion peut ensuite être utilisée pour rechercher des corrélations entre l’appartenance à une communauté et les comportements observés (opinions, achats, activités, etc.).
(iii) La prédiction de liens est un problème étroitement lié à la dynamique des réseaux. L’objectif est de prédire, entre deux états du réseau, la formation de liens entre deux noeuds [Liben-Nowell 2007]. Les algorithmes peuvent se baser uniquement sur la structure du réseau, ou prendre également en compte les attributs des noeuds. Ces méthodes peuvent aussi être utilisées pour prédire l’existence d’un lien, c’est-à-dire un lien qui n’est pas présent dans le jeu de données, mais qui existe dans la réalité.
Ces méthodes trouvent des applications dans le domaine du marketing par exemple, où la formation d’un lien entre un utilisateur et un produit peut être prédite de façon à mener des actions ciblées.
(iv) La recherche de motifs fréquents. Dans le contexte des réseaux, un motif est traditionnellement défini comme un sous-graphe. Les méthodes de recherche de motifs fréquents identifient donc les sous-réseaux qui se retrouvent fréquemment soit dans un en-semble de réseaux, ou au sein d’un unique réseau très large [Cheng 2010]. Une présentation détaillée de ces méthodes est faite dans le Chapitre 5.
Une application classique de ces méthodes concerne les réseaux de produits achetés conjoin-tement, où les méthodes d’extraction de motifs fréquents dans les réseaux permettent de mettre en évidence les sous-ensembles de produits fréquemment achetés ensemble.

Modélisation des phénomènes de propagation

Des phénomènes de propagation peuvent être observés partout : maladie infectieuse, virus informatique, phénomène de mode, rumeur, ou plus généralement information. Pour-tant, bien que ces phénomènes puissent sembler de prime abord très diﬀérents, ils sont tous des exemples types de processus qui ont pour support un réseau d’interactions entre des entités.
Ainsi, en raison de leur intérêt dans de nombreux domaines, les phénomènes de propagation ont fait l’objet de recherches actives et ont été étudiés à travers deux problèmes duaux :
(i) celui de la percolation, qui s’intéresse à la structure du support et à sa capacité à « inon-der » un maximum d’entités, et (ii) celui de la diﬀusion qui se focalise sur l’évolution du processus en tentant de comprendre les diﬀérentes phases de son évolution.
Cette section présente ces deux types de problème. La Section 2.3.1 expose le problème de la percolation et la Section 2.3.2 est consacrée aux modèles de diﬀusion.

Percolation dans les réseaux

La théorie de la percolation a été introduite en 1957 par Broadbent et Hammers-ley [Broadbent 1957], pour analyser la pénétration d’un gaz dans un labyrinthe formé de passages ouverts ou fermés. À l’origine, l’objectif était de comprendre comment les masques
à gaz des soldats devenaient ineﬃcaces. Ces masques sont en eﬀet constitués de petites par-ticules de carbone poreuses qui forment un réseau aléatoire de tunnels interconnectés. Si les pores sont assez larges et suﬃsamment connectés, le gaz passe à travers les particules. En revanche, si les pores sont trop petits ou s’ils sont imparfaitement connectés, les émanations ne peuvent plus traverser le filtre. L’eﬃcacité de la solution dépend donc d’un seuil critique qui est caractéristique du phénomène de percolation.
D’une façon générale, l’étude de la percolation vise à mettre en évidence les phases de transitions sur des structures aléatoires. Ces transitions sont généralement liées à la valeur critique d’un paramètre clé, appelé seuil de transition ou seuil de percolation, à partir duquel un système subit un changement brutal d’état qui permet la pénétration d’un élément.
Des cas d’études classiques sont fournis par les réseaux de communica-tion [Hammersley 1980]. Supposons par exemple que dans un réseau téléphonique, où toutes les stations sont connectées de proche en proche, des liens soient détruits de manière aléatoire, soit à cause d’un mauvais entretien, soit par l’action d’un « saboteur stochastique ». Au fur et à mesure de la suppression, il devient de plus en plus diﬃcile de maintenir un chemin dans le réseau capable de relier deux stations données, et ce, jusqu’à ce qu’un seuil critique de suppression soit atteint qui éclaterait le réseau en plusieurs composantes. La valeur pc, associée au pourcentage critique de liaisons actives nécessaires pour que deux points quelconques soient reliés définit le seuil de percolation. Dans le contexte de l’étude des phénomènes de propagation sur les réseaux, la théo-rie de percolation a été utilisée pour répondre à des questions telles que : la structure du réseau permet-elle une propagation du phénomène ? ou quel pourcentage d’individus peut potentiellement être aﬀecté ?
Il s’agit d’évaluer la probabilité d’existence d’un ensemble de liens, permettant la connexion directe ou indirecte entre deux entités du réseau. Plus précisément, on s’intéresse au seuil de paramètres critiques qui garantissent la connexité de la structure, c’est-à-dire le maintien d’une composante principale géante capable de supporter un phénomène de propagation et d’aﬀecter un maximum de noeuds. Quand une telle composante est maintenue, on dit que le réseau « percole ».
Soit G = (V, E) un réseau aléatoire dans lequel chaque lien du réseau existe selon une proba-bilité p. La probabilité que ce graphe admette une unique composante connexe est appelée probabilité de percolation et est notée θ(p). Les travaux menés par Kesten [Kesten 1982] montrent qu’il existe un seuil critique pc = 0.5, tel que :
θ(p) = 0 si p < pc
θ(p) > 0 si p > pc
Un des résultats les plus intéressants de la littérature sur la percolation est apporté par Cohen et al. [Cohen 2000], qui s’intéressent au pourcentage critique de noeuds pc à supprimer aléatoirement pour déconnecter des réseaux scale-free. Ils montrent que pour des distributions de degrés suivant une loi de puissance de la forme P (k) ≈ c × k−λ, avec λ ≤ 3, la transition n’a jamais lieu, suggérant ainsi que le réseau possède toujours une unique composante ; autrement dit, le réseau percole toujours. Ces résultats viennent confirmer ceux obtenus par Albert et al. [Albert 2000] qui démontraient également la forte robustesse de ce type de réseau face à la suppression aléatoire de noeuds.
D’autres résultats sont en revanche venus compléter ces travaux, en montrant que si la suppression cible uniquement les noeuds les plus connectés du réseau, le pourcentage de noeuds fortement connectés à supprimer pour éclater la composante s’exprime comme une fonction de l’exposant λ. Cohen et al. [Cohen 2001] montrent par exemple que dans la plupart des configurations, le pourcentage de noeuds à supprimer est inférieur à 3%. Quand λ > 3, celui-ci s’abaisse à moins de 1%. Ils montrent ainsi que la plupart des réseaux du monde réel sont vulnérables à ce type d’attaques ciblées.
La percolation a souvent été définie comme le problème dual de celui de la diﬀu-sion [Newman 2003, Pajot 2001]. En eﬀet dans le cas de la percolation, le mécanisme sto-chastique tient du milieu à travers lequel le processus évolue et non du processus lui-même. À l’inverse, les travaux menés sur les problèmes de diﬀusion s’intéressent à l’évolution aléa-toire du phénomène dans un milieu, cette fois, déterministe. Le tableau de la Figure 2.7 résume ces observations.

Collecte automatique de données sociales

La collecte de données sociales fait référence à toutes les méthodes qui se donnent pour objectif de collecter des interactions sociales entre des entités. Comme nous l’avons présenté dans le Chapitre 1, ce problème est un axe fondamental de la recherche sur les réseaux. En eﬀet, en raison des diﬃcultés que rencontrent les scientifiques à obtenir et à exploiter des données réelles, les travaux ont souvent eu recours à des modélisations pour aborder les phénomènes portés par les réseaux. La collecte de données réelles constitue aujourd’hui un enjeu majeur pour la confrontation, la validation ou l’amélioration des modèles existants.
Cependant, collecter les données qui témoignent d’interactions survenant entre des en-tités dans la réalité n’est pas une tâche facile. Le type d’interaction à collecter dépend du type d’entités, de leur environnement, et du phénomène que l’on souhaite étudier. La col-lecte de données soulève donc des problèmes variés touchant à la fois à la complexité des méthodes à mettre en place, et aux types d’interaction qu’elles sont en mesure de collecter.
Dans cette section, nous nous intéressons aux méthodes de collecte, et plus particu-lièrement aux méthodes récentes qui tirent parti de l’amélioration des performances des microcontrôleurs pour une collecte automatique des données sociales.

Collecte à partir de données en ligne

Avec le développement du WEB 2.0 et la multiplication des sites d’échanges et de partages tels que les forums, les blogs, les sites communautaires ou les sites de e-commerce, divers jeux de données ont pu être générés à partir des interactions crées via ces médias et de l’activité des entités concernées. Les diﬀérents réseaux pouvant être obtenus à partir de ces sites sont les suivants :
• Réseaux d’intérêt : Réseaux bipartis créés à partir de forums et impliquant les utilisateurs et leurs sujets d’intérêt. Par projection, ce réseau peut ensuite être utilisé pour générer un réseau d’utilisateurs, dans lequel deux utilisateurs sont connectés s’ils partagent les mêmes sujets d’intérêt.
• Réseaux de blogs : Les articles publiés sur les blogs font souvent référence à d’autres blogs par le biais des liens hypertextes. Ces informations peuvent être utilisées pour générer des réseaux de blogs connectant deux blogs quand l’un fait référence à l’autre.
• Réseaux d’amitié/intérêt : À l’origine, les sites communautaires tels que Face-book, Twitter ou Google +, permettaient d’obtenir des informations sur les liens d’amitié ou de connaissance entretenus par les individus. Aujourd’hui, face à la di-versité d’information présente sur ces sites (individu, entreprise, parti politique, ar-tiste, produit, évènement, etc.), nous observons que la sémantique du lien s’assimile désormais à « porter un intérêt à ».
• Réseaux d’achats : Trois types de réseaux peuvent être obtenus à partir des sites de commerce en ligne. (i) Des réseaux bipartis, impliquant les consommateurs aux produits qu’ils achètent. (ii) Des réseaux de consommateurs, connectant deux consomma-teurs quand ils ont acheté un même produit. (iii) Des réseaux de produits, connectant deux produits quand ils sont achetés conjointement par un même consommateur.
• Réseaux de co-auteurs : Le cas le plus répandu concerne les bases de données d’articles scientifiques. Par exemple, en utilisant les données issues de DBLP 2, un réseau de co-auteurs peut être obtenu, dans lequel deux auteurs sont connectés s’ils sont co-signé un même article.
Le principal inconvénient de ces approches réside dans le fait qu’elles ne permettent d’obtenir qu’un type particulier d’interactions, sémantiquement lié au média utilisé. Les réseaux extraits de ces sources d’informations sont par exemple diﬃcilement exploitables dans le cadre de l’étude de la diﬀusion d’une épidémie ou d’une information. Dans le cas de la diﬀusion de certaines maladies infectieuses telles que la grippe, les contacts de proximité géographique entretenus par les individus lors de leurs déplacements ou dans les lieux qu’ils fréquentent ne peuvent être extraits à partir d’aucune source d’information connue. C’est la raison pour laquelle des méthodes de collecte alternatives ont été proposées.

Microcontrôleurs pour la collecte de données sociales

Aujourd’hui, l’évolution des moyens techniques et notamment le fort développement que connaissent les micro-dispositifs, capables de capturer des données sonores, visuelles ou spatio-temporelles, a récemment permis d’entrevoir de nouvelles possibilités dans la collecte de données sociales. Les microcontrôleurs sont composés de circuits intégrés, qui rassemblent les éléments fondamentaux d’un ordinateur : un processeur, une mémoire morte pour le pro-gramme, une mémoire vive pour les données et des interfaces d’entrées-sorties permettant l’interaction avec l’extérieur. Les microcontrôleurs présentent des capacités limitées en mé-moire et en calcul et sont fréquemment utilisés pour la conception de périphériques divers : capteurs (voir Figure 2.15), téléphones portables, tablettes, dispositifs de localisation (GPS) ou puces RFID.
Malgré leurs limitations, ils ont depuis quelques années connu un succès grandissant qui s’explique par diﬀérents facteurs. Tout d’abord, la miniaturisation extrême des composants permet d’obtenir des dispositifs de plus en plus petits. Leur coût de fabrication peu élevé et leur capacité à communiquer entre eux facilitent leur utilisation à grande échelle lors d’expériences scientifiques d’envergure ou dans des domaines pour lesquels une observation humaine permanente est requise.
Ainsi, les perspectives intéressantes oﬀertes par les microcontrôleurs ont permis leur utilisation récente pour la collecte de données sociales. Des travaux récents ont en eﬀet eu recours à ces dispositifs pour collecter les traces de diﬀérents types d’interactions so-ciales entre des humains ou des animaux. Nous distinguons essentiellement deux types de dispositifs de collecte.
Dispositifs mobiles
Les dispositifs mobiles sont les plus répandus dans le domaine de la collecte de données sociales. Ils font référence à des dispositifs placés sur les agents et pouvant se déplacer dans l’espace : capteurs mobiles, téléphones portables, tablettes, collier GPS ou puces RFID. Les données collectées sont souvent des données sur la position géographique et les dispo-sitifs situés à proximité. Deux types de configurations peuvent être envisagés. (i) Soit les dispositifs sont capables d’envoyer directement leur information à un serveur central. C’est par exemple le cas des téléphones portables, des tablettes, ou des colliers GPS qui peuvent utiliser le réseau Internet, et plus particulièrement la technologie 3G, pour acheminer les données collectées. (ii) Soit les dispositifs sont organisés en réseau (capteur sans-fils ou puce RFID) et communiquent leurs informations à des antennes relais, chargées d’acheminer les données collectées vers le serveur (voir Figure 2.16).
Cette méthode présente l’avantage de fournir directement des données individuelles, puisque le dispositif est rattaché à un individu unique, le « porteur du capteur « .

Dynamique des réseaux et phénomènes de diﬀusion

Ces dernières années, l’étude de l’évolution des réseaux a été un domaine de recherche très actif [Barabasi 1999, Dorogovtsev 2002, Boguna 2003, Toivonen 2009]. En eﬀet, de nombreuses études ont été menées pour comprendre comment des mécanismes d’évolu-tion pouvaient conduire aux caractéristiques topologiques particulières observées sur de nombreux réseaux du monde réel. Pourtant, bien que des avancées aient été faites sur la compréhension de ces mécanismes, on peut s’étonner d’observer que peu de travaux menés sur la dynamique des réseaux ont contribué à l’étude des phénomènes de diﬀusion. C’est ce qu’observent également Gross et al. [Gross 2006], qui expliquent que les études sur « la dynamique du réseau et la dynamique sur le réseau » ont été menées séparément, détachant ainsi deux aspects fondamentaux et intrinsèquement liés de nombreux phénomènes surve-nant sur les réseaux du monde réel.
Dans cette Section, nous présentons les diﬀérents travaux menés sur ce sujet.
L’étude des phénomènes de diﬀusion sur des réseaux en évolution est un domaine re-lativement récent. Nous pouvons par exemple citer l’approche mathématique de Gross et al. [Gross 2006] qui s’intéresse au phénomène de diﬀusion sur un réseau dont la dynamique est liée à un comportement « adaptatif » des noeuds, c’est-à-dire qu’à chaque itération, les individus susceptibles, connectés à un individu infecté, ont la possibilité de casser leur lien avec l’individu infecté et d’en recréer un nouveau avec un individu susceptible choisi aléatoi-rement selon une probabilité w. Gross et al. étudient cette stratégie d’évolution selon deux points de vue. Ils montrent tout d’abord qu’au niveau de la structure, la stratégie tend à produire deux clusters composés respectivement des individus susceptibles et des infectés. En ce qui concerne la diﬀusion, ils observent que l’augmentation de la probabilité w tend à réduire la taille de l’épidémie.
De façon très similaire, Volz et Meyers [Volz 2007] s’intéressent à la diﬀusion dans un ré-seau évoluant selon le modèle N E (Neighbour Exchange), basé sur la permutation de noeuds dans deux liens. Dans ces deux approches, le nombre de noeuds et de contacts reste figé, seule la composition des contacts est modifiée.
Par simulation, Li et al. [Li 2004] étudient la diﬀusion sur un réseau petit-monde dyna-mique. Pour cela, ils étendent le modèle de Watts et Strogatz [Watts 1998] en y ajoutant une probabilité de mouvement des noeuds notée pmove. Ce processus peut être vu comme une décision de reconnecter un lien. La reconnexion s’eﬀectue exactement comme dans le modèle de Watts et Strogatz. Leurs résultats montrent que le temps caractéristique de la diﬀusion diminue quand pmove augmente ; autrement dit, plus il y a de l’activité sur le réseau et plus l’épidémie survient précocement et croît vite dans le temps.
Dans leurs travaux, Read et al. [Read 2008] étudient comment la fréquence des rencontres entre les individus peut influencer le processus de diﬀusion. Pour ce faire, ils étudient un groupe de 49 volontaires pour lesquels ils collectent les interactions durant 14 jours. Les données obtenues leur permettent de générer un réseau contenant 8661 contacts et 3528 in-dividus diﬀérents. Sur ces contacts, ils identifient deux catégories ainsi que leurs fréquences :
(a) les contacts basés sur les conversations et (b) les contacts physiques. Pour comprendre l’impact de la fréquence des rencontres sur le processus de diﬀusion, ils utilisent un modèle SIR et simule une diﬀusion sur le réseau pondéré avec les fréquences des rencontres. Il est intéressant d’observer que contrairement aux travaux précédents, qui modifient à chaque itération des éléments du réseau, ce travail résume d’une certaine manière la dynamique du réseau par une pondération des liens.
Très récemment, la disponibilité de données réelles sur des phénomènes de diﬀusion pre-nant place sur le réseau Internet a permis de mesurer l’impact de la dynamique du réseau sur ces processus. Nous pouvons par exemple citer les travaux de Albano [Albano 2012], qui utilise des données issues de la transmission réelle de fichiers dans un réseau pair-à-pair et montre que lorsque la dynamique est prise en compte, le phénomène semble connaitre une décroissance avec le temps. Elle introduit ainsi un modèle de diﬀusion basé sur une probabilité d’infection décroissante avec le temps qui permet une meilleure approximation de la diﬀusion réelle sur ce type de réseau.
Toujours basée sur des données réelles, l’étude menée par Guille et Hacid [Guille 2012] s’appuie sur des données issues du site communautaire Twitter pour proposer un modèle de diﬀusion basé sur les comportements individuels. Leur approche repose sur l’appren-tissage automatique sur des attributs extraits de trois dimensions (sociale, sémantique et temporelle) pour calculer la probabilité qu’un utilisateur u1 transmette une information à un utilisateur u2 à chaque instant t.
Des outils de simulation ont également été conçus pour simuler diﬀérents types de scé-narios d’infection sur des populations. Christensen et al. [Christensen 2010] proposent par exemple un outil capable de générer des réseaux construits par diﬀérents types de relation : famille, travail, école, etc. La dynamique du réseau est abordée ici selon une combinaison de changements démographiques et topologiques, dus à des évènements tels que des naissances, des mariages, des mouvements d’immigration, des situations dans lesquelles des individus quittent ou rejoignent un école, un emploi, etc. La fréquence de ce type d’évènement est déterminée à partir de données statistiques.
De même, Barrett et al. [Barrett 2008] ont proposé l’outil EpiSimdemics, capable de re-produire les déplacements d’individus dans la ville de Portland. Cet outil, qui s’intéresse essentiellement aux contacts induits par la proximité géographique, est par exemple ca-pable de prendre en compte les activités des individus, leur profession, leur âge, les axes de circulation et de communication.

Dynamique sur le réseau et dynamique du réseau : Vers un modèle unifié

Les phénomènes de diﬀusion peuvent être de natures très diﬀérentes : épidémie, virus informatique, diﬀusion de fichiers, rumeurs, informations, etc. Pourtant, il est intéressant de constater que bien que ces processus aient été étudiés par des communautés scientifiques diverses (sociologie [Wallace 1991], biologie [Meyers 2005], physique [Rhodes 1996], mathé-matiques [Kermack 1927] ou informatique [Eubank 2005]), les principes de modélisation de ces phénomènes s’avèrent être très similaires quel que soit le type de diﬀusion considéré.
C’est ce point de convergence que nous analysons dans la Section 3.2.1 et qui est au coeur du modèle unifié que nous proposons. Ce modèle est détaillé dans la Section 3.2.2 et nous le discutons dans la Section 3.2.3.

Modèles de diﬀusion : états et transitions

Quel que soit le phénomène de diﬀusion considéré, nous observons que les principes de modélisation sont basés sur un même concept : une transition d’état chez les entités étudiées (humains, animaux ou machines). En eﬀet, les modèles standards de diﬀusion représentent les individus comme pouvant prendre plusieurs états. Nous trouvons généralement un état initial, qui représente le fait que l’individu ne soit pas atteint par le phénomène, puis des états intermédiaires qui modélisent l’évolution du processus selon la perception que l’individu a du phénomène, ou l’eﬀet qu’il a sur lui.
Typiquement en épidémiologie, les individus sont généralement catégorisés selon qu’ils soient « Susceptible », « Infected » ou « Recovered » [Christley 2005, Christakis 2010]. Un indi-vidu susceptible est un individu qui n’est pas encore infecté par la maladie, mais qui peut le devenir s’il entre en contact avec un individu infecté. Les individus dans l’état Infected désignent ceux qui transmettent la maladie en infectant les individus Susceptible. Enfin, les Recovered sont les individus qui ont guéri de la maladie et qui ne peuvent plus ni la contracter, ni la diﬀuser.
Dans le contexte de la diﬀusion de rumeurs, la plupart des modèles considèrent également trois états : Ignorant pour ceux qui ignorent la rumeur, Spreader pour ceux qui la propagent et Stiﬄer pour ceux qui tentent de l’étouﬀer [Daley 1965, Nekovee 2007].
Pour la diﬀusion de connaissances ou d’innovations, on retrouve les états : Interested, et Adopted [Granovetter 1978, Gruhl 2004].
Ainsi, bien que tous les modèles tendent à représenter au niveau individuel l’évolution du processus par un ensemble d’états, des divergences peuvent être observées dans (i) les mécanismes de transitions, qui peuvent être liés à la nature du phénomène, l’environnement des noeuds, le temps passé d’un état et même à la connaissance actuelle que l’on a du phé-nomène et (ii) l’objectif de la modélisation, qui est souvent dépendant de la sémantique du problème.
Pour (i) par exemple, la probabilité qu’un individu dans l’état Susceptible passe à l’état Infected croît avec son nombre de voisins infectés. De même, un individu dans l’état dans Infected passe à l’état Recovered selon une certaine probabilité. Cet état traduit le fait que la maladie ne sera plus transmise par cet individu soit par l’application de soins, la mise en quarantaine ou le décès de l’individu. En revanche, quand il s’agit de rumeurs, un Spreader peut devenir Stiﬄer de deux façons : quand il est en contact avec un autre Spreader, ou quand il a un contact avec un Stiﬄer.
En ce qui concerne le point (ii), les objectifs peuvent être radicalement diﬀérents selon le type de phénomène considéré. Par exemple, les modèles de diﬀusion d’épidémies ou de virus informatique, tentent souvent de reproduire l’évolution réelle de l’infection, dans le but de mesurer l’eﬀet de stratégies d’intervention visant à limiter, voire même idéale-ment éradiquer complètement le processus [Salathe 2010b]. Dans le contexte de la diﬀusion de rumeurs, d’opinions, ou plus généralement de connaissances, l’objectif est au contraire de diﬀuser aussi vite et eﬃcacement que possible sans entraves à l’évolution du phéno-mène [Zanette 2001]. Les interventions visent dans ce cas à maximiser le nombre d’individus aﬀectés par le phénomène.
Le tableau de la Figure 3.3, présente une comparaison des principaux modèles utilisés dans chaque type de diﬀusion.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1 Introduction
2 Analyse, propagation, collecte : un état de l’art des approches « réseau »
2.1 Fondements théoriques
2.1.1 Origines
2.1.2 Définitions et notations
2.1.3 Mesures
2.1.4 Structures et modèles de génération
2.1.5 Réseaux complexes et réseaux sociaux
2.2 Exploitation des données : Analyse et fouille de données sociales
2.2.1 Premières approches
2.2.2 Fouille de données sociales
2.3 Modélisation des phénomènes de propagation
2.3.1 Percolation dans les réseaux
2.3.2 Approche réseau des problèmes de diffusion
2.4 Collecte automatique de données sociales
2.4.1 Collecte à partir de données en ligne
2.4.2 Microcontrôleurs pour la collecte de données sociales
2.5 Conclusion
3 Phénomènes de diffusion dans les réseaux sociaux dynamiques
3.1 Dynamique des réseaux et phénomènes de diffusion
3.2 Dynamique sur le réseau et dynamique du réseau : Vers un modèle unifié
3.2.1 Modèles de diffusion : états et transitions
3.2.2 Le modèle unifié D2SNet
3.2.3 Discussion
3.3 Mécanismes de formation de liens élémentaires
3.3.1 Objectifs, méthode et environnement
3.3.2 Résultats expérimentaux
3.4 Stratégie avancée d’évolution du réseau
3.4.1 Le modèle spatial dynamique DynBPDA
3.4.2 Résultats expérimentaux
3.5 L’outil graphique DynSpread
3.6 Conclusion
4 Mobilité humaine et phénomènes de diffusion : une approche multi-agents
4.1 Modélisation de la mobilité humaine : un état de l’art
4.2 Modèle de mobilité « Eternal-Return »
4.2.1 Mobilité des agents
4.2.2 Implémentation
4.3 Réseau de proximité basé sur la mobilité
4.3.1 Comment la mobilité induit-elle un réseau social dynamique ?
4.3.2 Distribution des agents dans l’espace
4.3.3 Répartition des contacts par agent
4.4 Mobilité et phénomènes de diffusion
4.4.1 Étude des seuils de percolation
4.4.2 Mobilité et diffusion
4.5 L’outil de simulation ER-Net
4.6 Conclusion
5 Fouille de données sociales : vers une analyse conceptuelle des réseaux sociaux
5.1 Extraction de motifs dans les données sociales
5.1.1 Motifs fréquents
5.1.2 Clustering basé sur les liens
5.1.3 Analyse conceptuelle
5.1.4 Notion de liens conceptuels
5.2 Liens et Vues conceptuels : définitions
5.3 Extraction des liens conceptuels fréquents maximaux
5.3.1 L’algorithme MFCL-Min
5.3.2 Discussion
5.3.3 Mesures d’intérêt sur les liens conceptuels
5.4 Génération de vues conceptuelles
5.5 Résultats expérimentaux
5.5.1 Environnement de test
5.5.2 Étude qualitative
5.5.3 Étude quantitative
5.5.4 Vues conceptuelles : exemples et évolution
5.6 L’outil GT-FCLMin
5.7 Conclusion
6 Réseaux de capteurs sans fil pour la collecte d’interactions sociales
6.1 Collecte d’interactions sociales en milieu sauvage : un état de l’art
6.1.1 Méthode manuelle d’observation
6.1.2 Dispositifs mobiles
6.1.3 Capteurs fixes
6.1.4 Bilan
6.2 Stratégie de collecte
6.2.1 Question initiale
6.2.2 Architecture de collecte
6.2.3 Identification des individus
6.3 Réseau social
6.3.1 Organisation et construction
6.3.2 Visualisation
6.4 Expérimentations
6.4.1 Simulateur Lypus
6.4.2 Environnement de test
6.4.3 Résultats expérimentaux
6.5 Conclusion
7 Conclusion et perspectives
Bibliographie 169Table des