Cette thèse s’intéresse à l’analyse du réseau dirigé extrait de la structure des hyperliens deWikipédia. Notre objectif est de mesurer les interactions liant un sous-ensemble de pages duréseau Wikipédia. Par conséquent, nous proposons de tirer parti d’une nouvelle représentationmatricielle appelée matrice réduite de Google ou "reduced Google Matrix". Cette matrice réduitede Google (GR) est définie pour un sous-ensemble de pages donné (c-à-d un réseau réduit).Comme pour la matrice de Google standard, un composant de GR capture la probabilité que deuxnoeuds du réseau réduit soient directement connectés dans le réseau complet. Une desparticularités de GR est l’existence d’un autre composant qui explique la probabilité d’avoir deuxnoeuds indirectement connectés à travers tous les chemins possibles du réseau entier. Dans cettethèse, les résultats de notre étude de cas nous montrent que GR offre une représentation fiabledes liens directs et indirects (cachés). Nous montrons que l’analyse de GR est complémentaire àl’analyse de "PageRank" et peut être exploitée pour étudier l’influence d’une variation de lien surle reste de la structure du réseau. Les études de cas sont basées sur des réseaux Wikipédiaprovenant de différentes éditions linguistiques. Les interactions entre plusieurs groupes d’intérêtont été étudiées en détail : peintres, pays et groupes terroristes. Pour chaque étude, un réseauréduit a été construit. Les interactions directes et indirectes ont été analysées et confrontées à desfaits historiques, géopolitiques ou scientifiques. Une analyse de sensibilité est réalisée afin decomprendre l’influence des liens dans chaque groupe sur d’autres noeuds (ex : les pays dansnotre cas). Notre analyse montre qu’il est possible d’extraire des interactions précieuses entre lespeintres, les pays et les groupes terroristes. On retrouve par exemple, dans le réseau de peintresissu de GR, un regroupement des artistes par grand mouvement de l’histoire de la peinture. Lesinteractions bien connues entre les grands pays de l’UE ou dans le monde entier sont égalementsoulignées/mentionnées dans nos résultats. De même, le réseau de groupes terroristes présentedes liens pertinents en ligne avec leur idéologie ou leurs relations historiques ou géopolitiques.Nous concluons cette étude en montrant que l’analyse réduite de la matrice de Google est unenouvelle méthode d’analyse puissante pour les grands réseaux dirigés. Nous affirmons que cetteapproche pourra aussi bien s’appliquer à des données représentées sous la forme de graphesdynamiques. Cette approche offre de nouvelles possibilités permettant une analyse efficace desinteractions d’un groupe de noeuds enfoui dans un grand réseau dirigé

Le principal but de notre recherche a été de caractériser les individus connectés dans un réseau social en analysant la structure locale du réseau. Pour cela, nous avons proposé une méthode qui décrit la façon dont un noeud (correspondant à un individu) est intégré dans le réseau. Notre méthode est liée à l'analyse de réseaux égocentrés en sociologie et à l'approche locale dans l'étude des grands graphes de terrain. Elle peut être appliquée à des petits réseaux, à des fractions de réseaux et aussi à des grands réseaux, grâce à sa petite complexité. Nous avons appliqué la méthode proposée à deux grands réseaux sociaux, un modélisant des activités enligne sur MySpace, l'autre modélisant des communications par téléphone mobile. Dans le premier cas nous nous sommes intéressés à l'analyse de la popularité enligne des artistes sur MySpace. Dans le deuxième cas, nous avons proposé et avons utilisé une méthode pour regrouper les noeuds qui sont connectés au réseau de façon similaire. Nous avons constaté que la distribution des utilisateurs de téléphone mobile dans des groupes était corrélée à d'autres caractéristiques des individus (intensité de communication et 'âge). Bien que dans cette thèse nous ayons appliqué les deux méthodes seulement aux réseaux sociaux, elles peuvent être appliquées de la même manière à tout autre graphe, peu importe son origine.

La dissémination d'informations (broadcast) est essentielle pour de nombreuses applications réparties. Celle-ci doit être efficace, c'est à dire limiter la redondance des messages, et assurer forte fiabilité et faible latence. Nous considérons ici les algorithmes répartis profitant des propriétés des topologies sous-jacentes. Cependant, ces propriétés et les paramètres dans les algorithmes sont hétérogènes. Ainsi, nous devons trouver une manière pour les comparer équitablement. D'abord, nous étudions les protocoles probabilistes de dissémination d'informations (gossip) exécutées sur trois graphes aléatoires. Les trois graphes représentent les topologies typiques des réseaux à grande-échelle : le graphe de Bernoulli, le graphe géométrique aléatoire et le graphe scale-free. Afin de comparer équitablement leurs performances, nous proposons un nouveau paramètre générique : le fanout effectif. Pour une topologie et un algorithme donnés, le fanout effectif caractérise la puissance moyenne de la dissémination des sites infectés. De plus, il simplifie la comparaison théorique des différents algorithmes sur une topologie. Après avoir compris l'impact des topologies et les algorithmes sur les performances , nous proposons un algorithme fiable et efficace pour la topologie scale-free.

Un flot de liens représente une trace de l'activité d'un système complexe au cours du temps, où un lien apparaît lorsque deux entités du système entrent en interaction ; l'ensemble des entités et des liens forme un graphe. Ces traces constituent depuis quelques années des jeux de données stratégiques dans l'analyse de l'activité de systèmes complexes à grande échelle, impliquant des millions d'entités : réseaux de téléphone mobiles, réseaux sociaux, ou encore Internet. Cette thèse porte sur l'analyse exploratoire des flots de liens, en particulier sur la caractérisation de leur dynamique et l'identification d'anomalies au cours du temps (événements). Nous proposons un cadre exploratoire sans hypothèse sur les données, faisant appel à l'analyse statistique et à la visualisation. Les événements détectés sont statistiquement significatifs et nous proposons une méthode pour valider leur pertinence. Nous illustrons enfin notre méthodologie sur l'évolution du réseau social en ligne Github, où des centaines de milliers de développeurs collaborent sur des projets de logiciel.

Cette thèse s'organise en deux parties : une première partie s'intéresse aux mesures de similarité (ou de proximité) définies entre les sommets d'un graphe, une seconde aux méthodes de clustering de graphe biparti. Une nouvelle mesure de similarité entre sommets basée sur des marches aléatoires en temps courts est introduite. Cette méthode a l'avantage, en particulier, d'être insensible à la densité du graphe. Il est ensuite proposé un large état de l'art des similarités entre sommets, ainsi qu'une comparaison expérimentale de ces différentes mesures. Cette première partie se poursuit par la proposition d'une méthode robuste de comparaison de graphes partageant le même ensemble de sommets. Cette méthode est mise en application pour comparer et fusionner des graphes de synonymie. Enfin une application d'aide à la construction de ressources lexicales est présentée. Elle consiste à proposer de nouvelles relations de synonymie à partir de l'ensemble des relations de synonymie déjà existantes. Dans une seconde partie, un parallèle entre l'analyse formelle de concepts et le clustering de graphe biparti est établi. Ce parallèle conduit à l'étude d'un cas particulier pour lequel une partition d'un des groupes de sommets d'un graphe biparti peut-être déterminée alors qu'il n'existe pas de partitionnement correspondant sur l'autre type de sommets. Une méthode simple qui répond à ce problème est proposée et évaluée. Enfin Kodex, un système de classification automatique des résultats d'une recherche d'information est présenté. Ce système est une application en RI des méthodes de clustering vues précédemment. Une évaluation sur une collection de deux millions de pages web montre les avantages de l'approche et permet en outre de mieux comprendre certaines différences entre méthodes de clustering.