Raphaël Fournier-S’niehotta

vendredi 21 décembre 2012 à 12h, salle 25-26/105

L’objectif de cette thèse est d’utiliser de grands ensembles de requêtes collectés sur des systèmes P2P pour étudier l’activité pédophile au sein de ces réseaux. En effet, malgré l’importance de ce problème pour la société, il existe peu de connaissances fiables en la matière. Nous procédons dans un premier temps à la mise au point d’un outil capable de détecter les requêtes qui ciblent des contenus à caractère pédopornographique, en assez faible quantité dans l’ensemble des requêtes. Après avoir identifié quatre catégories de requêtes pédophiles, nous établissons les listes de mots-clefs et tests lexicaux requis pour les distinguer. Nous faisons ensuite classer des requêtes à un ensemble d’experts, afin d’évaluer les performances de notre outil. Celui-ci disposant d’une précision élevée et d’un bon rappel, nous l’utilisons pour estimer de façon fiable la fraction de requêtes pédophiles, proche de 0,25%. Nous abordons ensuite la quantification des utilisateurs entrant ces requêtes. Dans un tel contexte, où l’on ne dispose que de l’adresse IP et éventuellement d’un port de communication, identifier des utilisateurs est difficile. Nous proposons plusieurs méthodes pour ne pas mélanger les requêtes d’utilisateurs différents. La fraction d’utilisateurs pédophiles est proche de 0,22%. Nous analysons ensuite la dynamique temporelle de l’activité pédophile. La fraction de requêtes pédophiles a significativement augmenté entre 2009 et 2012. Nous examinons également l’intégration sociale des utilisateurs pédophiles et constatons qu’ils privilégient la fin de la nuit pour effectuer ce type de requêtes, ce en quoi ils diffèrent des autres utilisateurs, notamment ceux soumettant des requêtes pornographiques. Enfin, nous confrontons les résultats obtenus sur le réseau eDonkey avec ceux du réseau KAD, après avoir défini une méthodologie permettant d’obtenir des données comparables. Nous supposons initialement que le niveau d’anonymat offert par KAD, complètement décentralisé, permet aux utilisateurs de participer à davantage d’échanges pédopornographiques. Nous constatons au contraire que l’activité pédophile est plus importante sur eDonkey et estimons que la fraction de requêtes pédophiles sur KAD est proche de 0.1%.

Emilie Coupechoux

lundi 10 décembre 2012 à 10h30, salle du Conseil (4ème étage), antenne parisienne de l’INRIA, 23 avenue d’Italie, 75013 Paris

Plusieurs types de réseaux du monde réel peuvent être représentés par des graphes dont les sommets représentent des individus (dans le cas des réseaux sociaux) ou des pages Web (dans le cas du World Wide Web), pour ne citer que ces exemples. Chaque arête du graphe correspond à une interaction entre sommets: dans les réseaux sociaux, une arête est présente entre deux sommets si les individus quils représentent sont amis; dans le World Wide Web, les arêtes représentent les liens hypertextes entre les pages Web. Comme il sagit de réseaux de très grande taille, leur topologie détaillée est généralement inconnue, et nous les modélisons par de grands graphes aléatoires ayant les mêmes propriétés statistiques locales que celles des réseaux observés. Un exemple de telle propriété est la présence de regroupements dans les réseaux réels: si deux individus ont un ami en commun, ils ont également tendance à être amis entre eux. tudier des modèles de graphes aléatoires qui soient à la fois appropriés et faciles à aborder dun point de vue mathématique représente un challenge, cest pourquoi nous considérons plusieurs modèles de graphes aléatoires possédant ces propriétés. La propagation dépidémies dans les graphes aléatoires peut être utilisée pour modéliser plusieurs types de phénomènes présents dans les réseaux réels, comme la propagation de maladies, ou la diffusion dune nouvelle technologie. Le modèle épidémique que nous considérons dépend du phénomène que nous voulons représenter : un individu peut contracter une maladie par un simple contact avec un de ses amis (ces contacts étant indépendants), mais une nouvelle technologie est susceptible dêtre adoptée par un individu lorsque beaucoup de ses amis ont déjà la technologie en question. Nous étudions essentiellement ces deux différents cas de figure. Dans chaque cas, nous cherchons à savoir si une faible proportion de la population initialement atteinte (ou ayant la technologie en question) peut propager lépidémie à une grande partie de la population: si cest le cas, on dit quune cascade est possible. La transition de phase de ce phénomène est étroitement liée à lapparition dune composante géante dans un graphe aléatoire (il y a une composante géante dans un graphe aléatoire si la taille de sa plus grande composante connexe augmente de façon linéaire avec la taille totale du graphe). Létude des graphes aléatoires permet notamment la prédiction de propriétés globales (savoir dans quel cas une cascade est possible ou non) pour des grands réseaux sur lesquels nous ne disposons que de données locales.

Jean-Loup Guillaume

lundi 19 novembre 2012 à 14h, salle 25-26/105

De nombreux systèmes, tels que des réseaux sociaux ou des réseaux informatiques, peuvent être modélisés par des graphes, que lon appelle alors graphes de terrain. Un certain nombre de travaux ont montré que ces graphes, bien que différents par bien des aspects, sont aussi semblables par beaucoup dautres et notamment ils possèdent tous une structure communautaire assez forte, cest-à-dire quils sont formés de sous-ensembles de sommets densément connectés. Si lon se restreint à une partition en communautés, on dispose de méthodes efficaces pour calculer cette structure, notamment la méthode de Louvain que jai contribué à créer et qui est la plus efficace dans le domaine. Or, la plupart de ces réseaux réels sont dynamiques et évoluent au cours du temps par lajout ou la suppression de sommets et de liens. Cette dynamique touche naturellement les communautés et il faut donc proposer de nouvelles méthodes pour les calculer et les analyser. Nous nous sommes intéressés dans ce mémoire à lapproche naturelle qui consiste à considérer un graphe dynamique comme une succession de graphes statiques, puis à calculer une partition en communautés à chaque instant et, enfin, à essayer de faire le lien entre les communautés à différents instants. Nous avons montré que cette approche nest pas utilisable directement car une modification mineure de la topologie peut engendrer des modifications très importantes de la structure communautaire, doù un phénomène dinstabilité. Nous avons alors proposé deux approches pour tenter de résoudre ce problème. La première approche considère que si le graphe évolue peu, ses communautés devraient rester globalement stables. Nous avons donc tout dabord tenté de stabiliser un algorithme existant en gardant la mémoire des calculs passés, ce qui a donné des résultats bien meilleurs mais avec toujours une instabilité résiduelle. Puis, nous avons étendu cette solution en calculant des partitions multi-pas de bonne qualité sur plusieurs instants de temps. Nous avons couplé cela avec une méthode de décomposition hiérarchique du temps afin de calculer des plages temporelles sur lesquelles ces partitions multi-pas ont un sens. Cette méthode à été appliquée avec succès à des données réelles. La seconde approche considère que même sil y a de nombreuses partitions de qualité, elles ne sont pas complètement différentes. Nous avons donc proposé une méthode pour calculer en pratique ces similitudes, qui permettent de définir des coeurs de communautés. Nous avons montré que les coeurs sont pertinents dans les graphes de terrain et permettent de les distinguer des graphes sans réelle structure communautaire (comme les graphes aléatoires par exemple). Nous avons également entamé des travaux pour montrer que les coeurs peuvent être utilisés dans le cas dynamique et quils sont naturellement stables et que les modifications quils peuvent subir sont cette fois très corrélées aux modifications topologiques.

Christophe Crespelle

Jeudi 22 novembre 2012 à 11h, salle 25-26/101

Nous étudions un procédé itératif de factorisation de bicliques dans un graphe multiparti, venant de la modélisation des graphes de terrain. Ce procédé itératif, qui prend en entrée le biparti d’incidence cliques-sommets d’un graphe, ne termine pas pour tous les graphes. Et dans les cas où il ne termine pas, il ne fournit pas un objet adéquat de modélisation. Ici, nous cherchons donc à contraindre ce procédé, aussi légèrement que possible, pour obtenir sa terminaison sur tout graphe. Nous définissons trois variantes de ce procédé. Pour deux d’entre elles, appelées facteur propre et facteur fort, nous montrons qu’elles terminent toujours. Pour la troisième de ces variantes, appelée facteur faible, nous exhibons un graphe sur laquelle elle ne termine pas. Nous montrons également que le graphe multiparti sur lequel termine la série des facteurs propres a une propriété remarquable: ses sommets sont en bijection avec les éléments du demi-treillis inférieur des intersections des cliques maximales du graphe de départ.

Franck Delaplace

Jeudi 18 octobre 2012 à 10h30, salle 25-26/101

Slides

In this talk, we investigate the questions related to modularity in biological interaction networks. We develop a discrete theoretical framework based on the analysis of the asymptotic dynamics of biological interaction networks. More precisely, we exhibit formal conditions under which agents of interaction networks can be grouped into modules, forming a modular organisation. Our main result is that the conventional decomposition into strongly connected components fulfills the formal conditions of being a modular organisation. We also propose a modular and incremental algorithm for an efficient equilibria computation.

Alain Barrat

Vendredi 21 septembre 2012 à 14h, salle 25-26/101

Slides

Dans la dernière décennie, une importante activité de recherche s’est développée au sujet des réseaux complexes, en grande partie motivée par le fait que de nombreux systèmes peuvent être représentés par des réseaux, c’est-à-dire un ensemble de sites ou sommets reliés par des liens. Je présenterai ici la problématique concernant les réseaux complexes dynamiques, via divers exemples : les réseaux d’infrastructure et les réseaux sociaux. Dans ce dernier cadre, je présenterai en particulier le projet SocioPatterns (http://www.sociopatterns.org/), qui a développé dans les dernières années une infrastructure capable de mesurer les interactions sociales en temps réel dans un espace limité, comme une conférence, des bureaux, un hôpital…, et étudie les réseaux sociaux dynamiques correspondants. Je présenterai les résultats obtenus par les déploiements de cette infrastructure, qui révèlent des régularités inattendues dans les interactions sociales. Je présenterai également un modèle de dynamiques sociales qui reproduit un certain nombre de faits observés empiriquement, et je discuterai quelques conséquences de la dynamique du réseau sur les processus qui s’y déroulent. Je conclurai par les perspectives qu’offre le domaine des réseaux dynamiques.

Pierre Latouche

Jeudi 14 Juin 2012 à 11h, salle 26-00/101

Slides

Les réseaux sont largement utilisés en sciences sociales afin de décrire les intéractions entre individus. Dans ce contexte, de nombreuses méthodes non-supervisées de clustering ont été développées afin d’extraire des informations, à partir de la topologie des réseaux. La plupart d’entre elles partitionne les noeuds dans des classes disjointes, en fonction de leurs profils de connection. Récemment, des études ont mis en évidence les limites de ces techniques. En effet, elles ont montré qu’un grand nombre de réseaux « réels » contenaient des noeuds connus pour appartenir à plusieurs groupes simultanément. Pour répondre à ce problème, nous proposons le modèle à blocs stochastiques chevauchants, Overlapping Stochastic Block Model (OSBM) en anglais. Cette approche autorise les noeuds à appartenir à plus d’une classe et généralise le très connu Stochastic Block Model, sous certaines hypothèses. Nous proposons un algorithme d’inférence permettant de classer les nouds d’un réseau, ainsi qu’un critère de sélection de modèles pour estimer le nombre de classes. Nous utilisons ces travaux pour analyser la blogosphère politique française.

Laura Hernandez

Jeudi 24 mai 2012 à 11h, salle 25-26/101

Mutualistic ecosystems are usually groups of animals and plants, helping each other to fulfil essential biological functions such as feeding or reproduction as in seed dispersal or pollination networks. Such systems may be described in terms of a complex network, where the nodes represent the animal or plant species and the links represent the existence of a contact between a plant and an animal species. As only contacts between nodes belonging to different guilds are allowed, the corresponding network is bipartite. Coding this information in a bipartite adjacency matrix, it is observed that real ecosystems are not a random collection of interacting species, but they display instead, a high degree of internal organization. Different hypothesis are discussed in the ecological literature to explain this particular order. It is fairly obvious that a detailed explanation of the interaction behaviour of individual species can be of little help to understand the generalized pattern that is found across ecological systems of very different sizes and types, that involve plants of different nature and animals that range from insects to birds. The tools commonly used by ecologists to study these systems are based on the statistical analysis of observed data. In this talk I will present an alternative way to study this problem, by introducing an algorithm that allows us to try different supposed hypothesis in the form of a Contact Preference Rule (CPR) that governs the dynamics of the system. Starting from a random configuration the system is evolved under the studied CPR and the comparison of the order state reached by this artificial system with the order observed in real systems allows us to decide whether a CPR may be considered or not as responsible for the observed order. In particular, I will introduce a new way to measure the order of mutualistic ecosystems and I will discuss about the relationship between the phylogenetic proximity of the members of each guild and the observed order.

Aline Carneiro Viana

Lundi 14 mai 2012 à 11h, salle 25-26/101

Slides

The constant advancement of information systems has allowed more data to be generated and stored from the most diverse situations. It is fascinating that, behind these records, we see the reflection of the environment itself, since every record represents a decision made by some entity. In this work, we modeled real-world scenarios of mobility from using temporal complex networks. The analysis assumes that these systems are composed of entities able to interact in a rational manner, reflecting their interests and activity dynamic. In this direction, we propose a technique for analyzing mobility scenarios from random graphs. This technique examines how the real system would evolve if the agents decisions were random, and from there, you can check, for example, which edges are random and which are derived from social relationships, such as friendship or professional.