Soutenance mémoire
Représentation et propriétés des réseaux de contacts
Avant tout travail d’analyse et de modélisation, la question de la structure de données à utiliser afin de proposer une représentation adéquate de réseaux de contacts est nécessaire. Plusieurs approches différentes sont étudiées dans la littérature. Un graphe dynamique, où les arêtes sont étiquetées par les temps discrets ou intervalles des moments d’activité du contact associé, permet de représenter sans pertes d’information ces réseaux. D’autres représentations plus proches des données expérimentales sont aussi étudiées, consistant généralement en une liste des contacts observés, soit de manière centralisée, soit distribuée relativement à chaque agent. Cette dernière représentation étant généralement peu adaptée à l’analyse des dynamiques et propriétés du réseau, mais pouvant être notamment utilisée pour effectuer des simulations.
Résultats sur les graphes dynamiques
Quelques rares travaux proposent des résultats théoriques sur des graphes dynamiques. Dans [8], la validité dans le cas dynamique de propriétés des graphes statiques est étudiée. Plus précisément les auteurs démontrent que le théorème de Menger, qui stipule que le nombre maximum de chemins qui ne se recoupent pas entre deux nœuds s et t est strictement égal au nombre minimal de nœuds à retirer du graphe pour déconnecter s et t, n’est plus valable. Les auteurs montrent que le nombre de chemins respectant l’ordre temporel entre deux nœuds, utilisant une séquence d’arêtes existant à des temps croissants, peut être strictement inférieur au nombre de nœuds à retirer pour les déconnecter.
Dans le même article est proposé un algorithme résolvant un problème d’inférence sur un graphe dynamique à information partielle. Plus précisément le problème résolu est de savoir si dans un graphe dynamique où le moment précis des contacts est méconnu (allant d’une date quelconque à une date restreinte à un intervalle), on peut déterminer si pour deux partitions données un scénario est possible dans lequel une source fixe peut joindre par un chemin respectant l’ordre causal l’ensemble des nœuds d’une partition mais aucun de l’autre. Ce problème de connectivité n’est pas posé dans les expériences décrites dans la section suivante. Ce problème est pertinent lors de cas de données avec des observations à information partielles afin de déterminer si un scénario précis de dissémination est possible. Des données de ce type sont fréquemment trouvées aussi bien pour des raisons techniques d’acquisition que dues à la représentation sous forme de séquence de graphes statiques, où une partie de l’information est perdue.
Représentation sous forme de séquence de graphes statiques
Dans de nombreux travaux, les réseaux de contacts sont représentés comme une séquence de graphes statiques. La dynamique étant représentée par cette série de graphes statiques. Chaque graphe représente une période de temps où sont agglomérés tous les contacts qui ont eu lieu. Cette représentation présente l’avantage de transformer l’analyse de graphes dynamique en une séquence d’analyse de graphes statiques, ce qui est bien documenté dans la littérature. Un des points épineux de cette représentation est le choix de la durée entre deux graphes successifs. En effet, un temps trop court et le graphe se retrouve presque sans observations de contacts, sans apporter d’informations pertinentes, et un temps trop long implique que la dynamique du réseau de contact est totalement perdue.
Une étude autour de la sélection appropriée de ce temps est proposée dans l’article [4] afin de limiter la perte d’informations pertinentes sur la dynamique de graphe. Les auteurs se servent des données produites par une expérience réalisée au sein du MIT pour effectuer leur analyse. Ils analysent les rythmes d’évolution des communautés au sein du réseau de contacts pour déterminer un temps caractéristique d’évolution du graphe. Afin de mesurer l’évolution du graphe trois mesures sont utilisées :
– le degré moyen des nœuds du graphe représentant la densité ;
– la valeur moyenne du coefficient de clustering mesurant l’importance des communautés au sein du graphe ;
– une mesure de corrélation des voisinages des nœuds mesurant les ressemblances des contacts actifs des différents nœuds.
Grâce à l’étude extensive des auto-corrélations de ces valeurs pour différents intervalles de temps entre deux états considérés du graphe, les auteurs arrivent à repérer des motifs de ressemblance de l’état du graphe tous les 8, 16 et 24 heures. Le motif journalier étant largement le plus évident. Ils proposent donc en conséquence une valeur d’environ 4 heures comme temps caractéristique de l’évolution du graphe à utiliser pour séquencer le graphe. Cette valeur permet de bien capturer les différentes phases d’évolutions et motifs journaliers.
Analyse simultanée poussée de deux expérimentations
A. Scherrer et Coll. présentent dans l’article [14] une analyse poussée prenant en compte de nombreux paramètres et propriétés des réseaux de contacts étudiés. Leur analyse est effectuée conjointement sur deux ensembles de données d’expériences, ceux de la conférence Infocom 2005 détaillée précédemment et sur du MIT Realty Mining [5] mentionné précédemment et résultant des traces des contacts d’une centaine de membres du département d’informatique de l’université pendant 9 mois. Lors de leur étude un très large spectre de propriétés est étudié ; les distributions des durées des contacts et inter-contacts ainsi que des coefficients de clustering mais aussi de manière originale des taux de suppression et d’apparition d’arêtes dans le réseaux ainsi que le nombre de triangles dans le graphe (trois personnes en contact simultané). Leur étude utilise une représentation sous forme de séquence de graphes statiques, mais pour être sûr de ne pas perdre d’information le temps d’échantillonnage est fixé à 1s afin de capturer de manière certaine toute évolution. L’étude sur les distributions des durées des contacts et inter-contacts vient confirmer les résultats existants stipulant que ces distributions suivent bien une loi de puissance.
Analyse statistique des propriétés structurelles
De manière similaire à l’étude effectuée dans [4], les auto-corrélations temporelles des différentes propriétés des graphes statiques sont calculées pour estimer leur temps moyen d’évolution. Des résultats similaires sont trouvés pour l’ensemble des mesures sauf en ce qui concerne la création et suppression d’arêtes qui évoluent de manière bien plus rapide. Ensuite des calculs des moyennes des corrélations croisées des différentes propriétés sont effectués et il en ressort une très forte corrélation des différentes propriétés avec des valeurs allant de 0.5 à 0.9, hors ajout et suppression d’arêtes qui sont totalement dé-corrélés. Cette étude montre que les ajouts et suppressions d’arêtes peuvent être considérés comme indépendants, mais qu’une telle hypothèse pour les autres propriétés serait fortement dommageable notamment pour effectuer une simulation. Les résultats obtenus relativement aux ajouts et suppressions d’arêtes montrent des temps caractéristiques d’évolution et des taux de corrélation tellement faibles qu’ils peuvent être considérés comme des processus aléatoires sans mémoire, et donc Markovien, sans perte significative d’information sur le réseau.
Enfin, une analyse sur l’évolution de différents paramètres de la structure du graphe représentant le réseau de contacts est effectuée. Dans un premier temps les auteurs caractérisent la stabilité temporelle des composantes connexes. Globalement, ils montrent que les trois quarts des ajouts et suppressions d’arêtes correspondent à des modifications de composantes connexes existantes. Le quart restant correspondant à une disparition d’une composante connexe ou à l’apparition d’une nouvelle composante connexe ; une autre possibilité étant aussi la séparation en deux d’une composante connexe ou la fusion de deux composantes connexes. Dans un second temps, la densité de triangles dans le graphe est étudiée. Les auteurs montrent que pour les réseaux de contacts étudiés l’ajout d’une arête a quatre fois plus de chances d’ajouter un triangle dans le graphe que pour un graphe aléatoire. Ce résultat caractérise bien le fait que deux personnes en contact, et donc à proximité d’une troisième, ont de fortes chances d’être en contact entre elles.
Émergence de communautés
Les auteurs s’intéressent aussi aux communautés présentes dans le graphe, une communauté étant un ensemble de personnes ayant plus d’interactions entre elles que la moyenne. Ces communautés ne sont pas capturées par l’étude des composantes connexes, bien que les membres d’une même communauté se retrouveront en général régulièrement au sein d’une même composante connexe. Trouver les communautés au sein du réseau de contacts n’est pas facile, trouver les communautés d’un graphe étant NP-difficile. Bien que la plupart des approches dans la littérature utilisent des heuristiques, une résolution exacte est privilégiée dans cet article. La méthode utilisée consiste à trier les couples de nœuds communiquant plus qu’une limite fixée et ensuite de les regrouper par composantes connexes, les composantes connexes n’ayant pas suffisamment d’interconnexions étant retirées ainsi que les composantes connexes qui ne sont pas assez denses. Ces communautés sont repérées pour de petits intervalles de temps, les résultats des différents intervalles étant ensuite réunis en regroupant les communautés qui diffèrent pour peu d’individus et plages temporelles. Les communautés trop peu représentées dans le temps ne sont pas retenues. Les résultats obtenus sur les expériences de réseaux de contacts étudiées repèrent une dizaine de communautés, certains individus pouvant faire partie de plusieurs communautés à la fois.
|
Table des matières
1 Introduction
2 État de l’art
2.1 Expériences en environnement réel
2.2 Représentation et propriétés des réseaux de contacts
2.2.1 Résultats sur les graphes dynamiques
2.2.2 Représentation sous forme de séquence de graphes statiques
2.2.3 Analyse simultanée poussée de deux expérimentations
2.3 Modélisations de réseaux de contacts
2.4 Évaluation de protocoles de routage pour réseaux de contacts
3 Analyse des propriétés générales des jeux de données utilisés
3.1 Rollernet
3.2 Infocom
3.3 Pnas
4 Étude de l’importance des nœuds dans la diffusion
4.1 Étude détaillée pour un temps de départ fixé
4.1.1 Résultats globaux des phénomènes de diffusion
4.1.2 Résultats obtenus par isolement des différentes sources
4.1.3 Résultats obtenus par isolement des différents destinataires
4.2 Étude généralisée à tous temps de départ
4.2.1 Algorithme développé
4.2.2 Évolution de l’importance des nœuds au cours du temps
4.3 Calcul du nombre de messages en transit au cours du temps
5 Analyse des résultats et discussion
5.1 Résultats pour différents jeux de données
5.1.1 Infocom
5.1.2 Pnas
5.2 Comparaison entre différentes mesures de centralités dynamiques
6 Conclusion
Télécharger le rapport complet
