Sharad Goel

Jeudi 20 mars 2014 à 14h, salle 25-26/101

New products, ideas, norms and behaviors are often thought to propagate through a person-to-person diffusion process analogous to the spread of an infectious disease. Until recently, however, it has been prohibitively difficult to directly observe this process, and thus to rigorously quantify or characterize the structure of information cascades. In one of the largest studies to date, we describe the diffusion structure of billions of events across several domains. We find that the vast majority of cascades are small, and are characterized by a handful of simple tree structures that terminate within one degree of an initial adopting « seed. » While large cascades are extremely rare, the scale of our data allows us to investigate even the one-in-a-million events. To study these rare, large cascades, we develop a formal measure of what we label « structural virality » that interpolates between two extremes: content that gains its popularity through a single, large broadcast, and that which grows via a multi-generational cascade where any one individual is directly responsible for only a fraction of the total adoption. We find that the very largest observed events nearly always exhibit high structural virality, providing some of the first direct evidence that many of the most popular products and ideas grow through person-to-person diffusion. However, medium-sized events — having thousands of adopters — exhibit surprising structural diversity, and are seen to grow both through broadcast and viral means. Finally, we show that our empirical results are largely consistent with an SIR model of contagion on a scale-free network, reminiscent of previous work on the long-term persistence of computer viruses.

Arnaud Casteigts

Vendredi 02 mai 2014 à 11h, salle 25-26/101

Slides

En partant de quelques problèmes de base en algorithmique distribuée (diffusion, élection, comptage, arbres couvrants), je discuterai de l’impact que peut avoir la dynamique du réseau sur ces problèmes en termes de redéfinition, conditions nécessaires, conditions suffisantes, etc. Cela nous permettra de passer en revue quelques classes de graphes dynamiques, qui seront ensuite resituées dans un contexte plus vaste comprenant une vingtaine de classes. La discussion sortira alors du cadre de l’algorithmique distribuée pour évoquer la dynamique des graphes en général.

Lionel Tabourier

Vendredi 11 avril 2014 à 11h, salle 25-26/101

Au cours de cet exposé, je présenterai une méthode d’apprentissage supervisé pour la prédiction de liens dans les réseaux sociaux, et plus précisément pour détecter des liens qui n’ont pas été collectés lors de l’acquisition des données. Pour illustrer l’utilisation de la méthode, nous utilisons un CDR (Call Detail Record) portant sur environ 1 million d’utilisateurs de téléphone portable et simulons la situation dans laquelle se trouve un opérateur téléphonique: celui-ci a connaissance des appels entre ses clients, et entre ses clients et des clients de concurrents. Mais avoir accès aux interactions existant entre les clients de ses concurrents serait aussi avantageux, car le taux d’attrition est étroitement lié à la structure du réseau social d’un utilisateur. Cependant, cette tâche est difficile: il s’agit de prédire des relations non-observées, dans un contexte où les classes de prédiction sont fortement asymétriques: alors que beaucoup de liens sont possibles, peu existent. C’est pourquoi les méthodes non-supervisées classiques, qui utilisent différentes caractéristiques structurelles du réseau pour classer les paires de noeuds, sont peu performantes dans ce contexte. Je décrirai RankMerging, une méthode d’apprentissage supervisée simple et peu coûteuse computationnellement, qui agrège les classements issus de différentes sources d’information pour améliorer les performances de prédiction. L’opérateur apprend les paramètres en utilisant les données de ses propres clients et les utilise ensuite sur les clients de ses concurrents. La méthode est adaptée à la situation dans laquelle nous nous trouvons: nous ne cherchons pas à obtenir une très bonne précision sur un petit nombre de prédictions, mais plutôt un bon compromis sur une bonne partie de l’espace Precision-Recall, permettant à l’opérateur d’ajuster sa stratégie. Ensuite, je discuterai du cas des réseaux ego-centrés, pour lesquels l’utilisation de cet outil est pertinente. En effet, dans le cas où l’on n’a accès qu’aux interactions d’un noeud avec ses voisins immédiats, l’information structurelle est très pauvre et nous devrons donc chercher d’autres sources d’information puis les agréger. Ici, nous discuterons comment la temporalité des interactions peut être exploitée comme source d’information pour améliorer les performances de la prédiction.

Bertrand Ducourthial

Jeudi 17 avril 2014 à 11h, salle 25-26/101

Slides

Dans cet exposé, nous présentons des travaux récents portant sur la conception d’algorithmes répartis dans les réseaux dynamiques. Ces réseaux présentent des connexions éphémères et des voisinages instables. Les réseaux véhiculaires en sont un exemple emblématique. Dans ces réseaux, les algorithmes et protocoles classiques sont généralement inadaptés. Notre travail porte sur la conception d’applications réparties embarquées. Nous aborderons les études de cas suivantes : communication entre deux noeuds mobiles, entre un mobile et l’infrastructure, collecte de données, fusion distribuée de données. Nous présenterons les algorithmes, les expériences réalisées avec des véhicules sur route ainsi que des démonstrations.

Ségolène Charaudeau

Jeudi 20 mars 2014 à 11h, salle 25-26/101

Slides

Au cours de ce séminaire, je vous présenterai le travail que j’ai réalisé durant ma thèse à l’UMRS 707 de l’INSERM sur l’influence de la structure du réseau complexe formé par les mouvements de commuting entre les villes française sur la propagation d’une maladie infectieuse, en utilisant l’exemple de la grippe. Les phénomènes de diffusion dans un groupe social, entre communautés ou individus, d’une maladie ou d’une information par exemple, sont influencés par la structure des contacts individuels entre ces entités: pour analyser ces phénomènes, des modèles basés sur des réseaux reproduisant la structure des contacts sont fréquemment utilisés. Dans le cas de la propagation de maladies infectieuses, plusieurs types de réseaux entrent en jeu: les mouvements de population quotidiens créent notamment un réseau complexe de contacts entre villes, dont la structure impacte la diffusion de maladies transmissibles par contact, telle que la grippe. Si cette influence a été abondamment étudiée pour les réseaux internationaux, notamment par l’étude des déplacements aériens, elle n’a que peu été analysée à l’échelle nationale et régionale. Durant mon travail de thèse, je me suis attachée à l’étude de la diffusion de la grippe sur le réseau formé par les mouvements de commuting en France et de ses propriétés, en lien avec la structure du réseau: pour cela, j’ai développé un modèle simulant la propagation de la grippe sur un réseau de contacts. Afin de lier les propriétés observées pour la diffusion à la structure du réseau, j’ ai mis en place des outils permettant de comparer la propagation obtenue sur le réseau de commuting et sur des réseaux randomisés. Cette analyse a permis de mettre en évidence l’existence de communautés de villes ayant un comportement de propagation similaire et de chemins de propagation préférentiels entre ces communautés. Elle a également permis d’analyser la structure de ces communautés, pour la plupart centralisées autour d’un groupe de nœuds qui assurent la communication avec les communautés environnantes.

Catherine Matias

Jeudi 22 mai 2014 à 11h, salle 25-26/101

Dans cet exposé, je présenterai tout d’abord les problématiques de co-évolution et de co-phylogénie qui portent sur la modélisation de l’évolution conjointe de deux systèmes biologiquement liés (hôtes-parasites ou gènes-espèces). La réconciliation cherche à fournir un scénario explicatif de la co-évolution entre deux phylogénies (arbres) liés, en prenant en compte un certain nombre d’évènements évolutifs comme la co-spéciation, la duplication, la perte et le transfert. Des algorithmes de réconciliation parcimonieuse existent pour une fonction de coût (de chacun des évènements ci-dessus) fixée, mais le résultat est évidemment très dépendant du choix de cette fonction. Une approche naturelle est de choisir pour ces coûts des fonctions inversement proportionnelles à la probabilité de chaque évènement sous un modèle co-évolutif. Je présenterai une méthode statistique qui permet d’estimer les paramètres d’un modèle de co-évolution entre deux arbres et donc des fonctions de coût associées. Il s’agit d’une méthode de type ABC (approximate Bayesian computation) qui n’utilise pas le calcul de la vraisemblance du modèle (likelihood-free method). J’illustrerai les résultats de la méthode sur données simulées et réelles.    

Cédric Sueur

Jeudi 27 mars 2014 à 11h, salle 25-26/101

Slides

Network optimality has been described in genes, proteins and human communicative networks. In the latter, optimality leads to the efficient transmission of information with a minimum number of connections. Whilst studies show that differences in centrality exist in animal networks with central individuals having higher fitness; network efficiency has never been studied in animal groups. Living in groups has many advantages but it also involves certain disadvantages such as increased disease transmission and the need to make collective decisions. In theory, the social network properties optimizing decision accuracy and the spreading of information should also increase the disease transmission rate, creating a trade-off between decision-making efficiency and infection risk. We aim to explore this trade-off by examining social network properties and investigating how they might interact to maximize decision accuracy and minimize infection risk. We studied several groups of primates and found that group size and neocortex ratio were correlated with network efficiency. Centralisation (whether several individuals are central in the group) and modularity (how a group is clustered) had opposing effects on network efficiency, showing that tolerant species have more efficient networks. Such network properties affecting individual fitness could be shaped by natural selection affecting bot information and disease transmission. The main question of interest is how social network properties and individual attributes within this network effect separately and at the same time the diffusion of transmission (tested through opening of a fruit box as a proxy for information and social learning) and of disease (tested through pseudoectoparasites). Two parallel diffusion experiments, tracking the two different flows at the same time through the same individuals, will be carried out on Japanese macaques at the Koshima field site of Kyoto University, Japan. Ultimately, through an innovative experimental approach, this study aims at understanding the relative influence of different factors inherent in social-living, both cultural (innovation) and ecological (infectious disease), on human sociality.

Antoine Mazières

Jeudi 13 mars 2014 à 11h, salle 25-26/101

Lors de ce séminaire, je vous présenterai le projet Sexualitics.org, ainsi que le papier associé publié dans le premier numéro de Porn Studies (à paraître en mars 2014). La pornographie en ligne et ce qu’elle représente de la sexualité n’a que très rarement fait l’objet d’approche quantitative. En effet, la pornographieest étudiée à travers des questions de genre, du féminisme, de l’identité sexuelle et de sa mise en scène, par le biais d’interviews, de questionnaires, etc. Notre approche visait à prendre avantage des données disponibles sur les plateformes hébergeant les vidéos – principalement les mots-clés de 2 millions de vidéos – et reconstruire réseaux, communautés et indices divers à plus grande échelle. Parmi les réalisations de cette recherche, on peut trouver un réseau sémantique des « catégories » dont les communautés rassemblent des éléments de mise en scène, de pratique, de nationalité, raciaux, etc. La capacité descriptive de certaines de ces catégories est remise en question et un « nicheness score » est élaboré pour mettre en avant les catégories qui discriminent un contenu spécifique. Aussi, un outil en ligne – Porngram – permet à chacun de représenter la fréquence des mots de leur choix sur 5 années. Les datasets et code source des outils sont disponible en ligne. Aucune image à caractère pornographique n’est montrée lors de la présentation ou le papier. Néanmoins, des mots-clés explicites apparaissent fréquemment sur les visualisations et lors des explications. Site du projet : http://sexualitics.org Pre-print du papier : http://hal.archives-ouvertes.fr/hal-00937745 Datasets : http://sexualitics.github.io/ Porngram : http://porngram.sexualitics.org

Pierre-André Maugis

Vendredi 28 février 2014 à 11h, salle 25-26/101

In this talk I will show how the relationship between the local and global characteristics of random graphs can be used for statistical inference. There exists a long history of research on graphs/networks as mathematical objects. However, the need for methods allowing for statistical inference based on network data is but recent, and was prompted by the current boom in available network datasets along with their relevance to research in the social and biological sciences. The problem we face, set in the classical statistical paradigm, consists in seeing the networks as issuing from a random process, and in trying to infer from the observed network some characteristics of the said random process. The difficulty is both theoretical and practical: we only observe one realisation of the network (where statisticians usually assume they have a large number of repeated measurements), and networks are large objects, easily involving millions of connections, which raises computational issues. Studying networks through the local characteristics that are motifs (e.g. triangles, squares, cliques, …) offers a solution to both problems at once. Motifs are small (and hence computationally amenable), and occur multiple times throughout the network. Moreover, as we will show, under the assumption of exchangeability one can relate the random process from which the network ensued and the distribution of realised motifs. Using these results we will describe how one can use motifs to produce sound statistical inference on network data. This is a joint Work with Sofia Olhede and Patrick Wolfe.

Emmanuel Faure

Jeudi 20 février 2014 à 11h, salle 25-26/101

La reconstruction des dynamiques multi-échelles de la morphogenèse des organismes vivants est devenue un enjeu majeur pour la bio-médecine. Le développement dun organisme multi-cellulaire est le résultat de phénomènes biomécaniques multi-échelles complexes. Léchelle cellulaire est un niveau dintégration fondamental aussi bien pour létude de la biomécanique que pour les processus de réactions-diffusions. La plateforme BioEmergences vise à reconstruire les dynamiques multi-échelles de la morphogenèse des organismes et à mesurer les différences et les similitudes entre les individus, aux différentes échelles, tout au long de leurs individuations. Depuis les données dimagerie obtenues par acquisition en microscopie multi-photons jusquà la modélisation des comportements cellulaires par lapproche des systèmes complexes, nos travaux se situent dans un cadre intrinsèque dinterdisciplinarité. Mon approche théorique propose la thèse que la reconstruction du lignage cellulaire vue comme un processus de branchement spatio-temporel fournit l’ensemble des morphodynamiques cellulaires. Jaborderai notamment lors de cette présentation une stratégie de reconstruction phénoménologique du lignage cellulaire fondée sur des méthodes probabilistes. De plus, à partir de différentes analyses de comportements cellulaires, je montrerai un modèle computationnel du développement du poisson zèbre au cours des phases précoces de lembryogenèse, fondé sur lensemble des caractéristiques mesurées.

Elisa Omodei

Jeudi 06 février 2014 à 14h30, salle 26-00/101

Comment les structures sociales et épistémiques dune communauté scientifique contraignent-elles les dynamiques de recherche à venir ? Nous avons analysé deux grands corpus de publications scientifiques décrivant plus de 20 ans de recherche dans deux domaines très différents : la physique et la linguistique computationnelle. Nous avons pu extraire un réseau social de collaborations entre auteurs et un réseau épistémique de co-occurrences entre les concepts abordés dans les articles (donnés par les codes PACS pour ce qui concerne la physique, et par des mots-clés extraits à travers des méthodes automatiques pour la linguistique computationnelle). Nous mettons notamment en évidence que le réseau épistémique a une structure modulaire et une distribution des degrés hétérogène. La structure en communautés peut sans doute être expliquée par des processus de sélection locaux. Un examen empirique montre que les dynamiques épistémiques locales dépendent aussi bien des structures sociales et épistémiques passées. De plus, nous montrons que lévolution du réseau social dépend également de facteur épistémiques, ce qui semble indiquer que les deux réseaux évoluent lun avec lautre.

Romain Boulet

Jeudi 23 Janvier 2014 à 11h30, salle 25-26/105

Slides

La complexité juridique est de plus en plus présente et débattue ; cette complexité possède plusieurs aspects dont celui induit par les (très nombreuses) citations croisées de textes : c’est l’aspect que nous modéliserons et analyserons dans cet exposé grâce à la théorie des graphes et l’analyse des réseaux. L’exposé commencera par une rapide introduction sur les graphes et réseaux et la présentation des problématiques liées aux sciences juridiques que nous aborderons. En particulier, le texte de loi sera vu à deux niveaux de granularité : le code et l’article. Dans un premier temps, nous analyserons donc le réseau des codes juridiques. Chaque code constitue alors un nœud du réseau et les liens sont les liens de citations de textes entre les différents codes. Bien que ce réseau possède un petit nombre de sommets, il n’en demeure pas moins difficile à appréhender de par son fort nombre d’arêtes (et donc sa forte densité). En considérant chaque code comme un grand domaine juridique et en parvenant à extraire une structure de ce réseau, nous pouvons exhiber une cartographie des grands domaines juridiques. Dans un deuxième temps, nous changerons d’échelle et de granularité : le texte de loi considéré (et donc le nœud du nouveau réseau) sera l’article au sein du code de l’environnement. Nous comparerons la structure du réseau de citations des articles du code de l’environnement avec la structure choisie par la commission supérieure de codification (découpage du code de l’environnement en sept livres). Romain Boulet est actuellement Maître de Conférences en mathématiques à l’Université Lyon 3 ; les travaux présentés ont été faits en collaboration avec Pierre Mazzega (Directeur de Recherche à l’IRD) et Danièle Bourcier (Directrice de Recherche au CNRS) de 2009 à 2012.

Bernard Conein (1) & Alexandre Delanoë (2)

Jeudi 09 janvier 2014 à 11h, salle 25-26/101

Slides

En proposant d’explorer comment, en envoyant un message sur une liste de discussion, un contributeur peut contrôler la forme du réseau dans lequel il intervient, on montrera quun fil de discussion peut se décrire comme un réseau de répliques dont lextension (nombre de messages, nombre de contributeurs) est gouvernée par des dynamiques de contrôle propre à certaines séquences d’interactions. Slides disponibles à l’adresse suivante : B. Conein :http://www.complexnetworks.fr/?p=1750 A. Delanoë : http://alexandre.delanoe.org/academie/docs/2014-01_DelanoeConein.svg

Qinna Wang

Jeudi 12 Décembre 2013 à 14h,salle 25-26/101

Slides

Dans le contexte des réseaux complexes, la structure communautaire du réseau devient un sujet important pour plusieurs domaines de recherche. Les communautés sont en général vues comme des groupes intérieurement denses. La détection de tels groupes offre un éclairage intéressant sur la structure du réseau. Par exemple, une communauté de pages web regroupe des pages traitant du même sujet. La définition de communautés est en général limitée à une partition de lensemble des nœuds. Cela exclut par définition quun nœud puisse appartenir à plusieurs communautés, ce qui pourtant est naturel dans de nombreux (cas des réseaux sociaux par exemple). Une autre question importante et sans réponse est létude des réseaux et de leur structure communautaire en tenant compte de leur dynamique. Cettethèseporte sur létude de réseaux dynamiques et la détection de communautés recouvrantes. Nous proposons deux méthodes différentes pour la détection de communautés recouvrantes. La première méthode est appelée optimisationde clique. L’optimisation de clique vise à détecter les nœuds recouvrants granulaires. La méthode de l’optimisation de clique est une approche à grain fin. La seconde méthode est nommée détection floue (fuzzy detection). Cette méthode est à grain plus grossier et vise à identifier les groupes recouvrants. Nous appliquons ces deux méthodes à des réseaux synthétiques et réels. Les résultats obtenus indiquent que les deux méthodes peuvent être utilisées pour caractériser les nœuds recouvrants. Les deux approches apportent des points de vue distincts et complémentaires. Dans le cas des graphes dynamiques, nous donnons une définition sur la relation entre les communautés à deux pas de temps consécutif. Cette technique permet de représenter le changement de la structure en fonction du temps. Pour mettre en évidence cette relation, nous proposons des diagrammes de lignage pour la visualisation de la dynamique des communautés. Ces diagrammes qui connectent des communautés à des pas de temps successifs montrent lévolution de la structure et l’évolution des groupes recouvrantes., Nous avons également appliquer ces outils à des cas concrets.

Bertrand Jouve

Jeudi 21 novembre 2013 à 11h, salle 25-26/101

A partir de deux exemples d’applications sur des données historiques (reconstruction de réseaux sociaux de la paysannerie médiévale et dynamiques de parcellaires anciens), nous montrerons comment il est possible d’améliorer nos outils de la théorie des graphes pour l’analyse des réseaux d’interactions. Nous baserons notre propos sur des recherches en théorie intervallaire et en topologie algébrique.

Nicolas Dugué

Jeudi 07 novembre 2013 à 11h, salle 25-26/101

Slides

Les capitalistes sociaux sont des utilisateurs particuliers de Twitter. Ces utilisateurs cherchent à obtenir un maximum de followers par des méthodes que nous décrirons pour gagner de la visibilité sur ce réseau. La visibilité et la potentielle influence obtenues par ces utilisateurs ne sont pas basées sur le contenu de leurs tweets et la crédibilité de leur compte mais sur une accumulation de followers artificielle. Il est donc intéressant de détecter ces utilisateurs afin d’étudier leur réelle influence sur le réseau. Nous proposons une méthode de détection des capitalistes sociaux utilisant des mesures simples basées sur la topologie du réseau uniquement. Suite à cela, nous montrons que les méthodes employées par ces utilisateurs font qu’ils forment un sous groupe densément connecté dans le graphe représentant le réseau. Par ailleurs, à travers une étude sur l’évolution de certains de ces comptes entre 2009 et 2013, nous démontrons l’efficacité de ces techniques pour accumuler des followers. Nous confirmons ensuite grâce à un compte Twitter automatisé qu’il est toujours possible d’appliquer ces méthodes. Enfin, nous nous intéressons à la position des capitalistes sociaux dans le réseau. Nous nous basons ainsi sur la notion de rôles communautaires introduite par Guimerà et Amaral pour caractériser la position de ces utilisateurs au sein des communautés du réseau. Nous généralisons cette méthode, l’adaptons aux graphes orientés et montrons que les capitalistes sociaux occupent des rôles spécifiques.

Laurent Beauguitte

Jeudi 24 octobre 2013 à 11h, salle 26-00/428

Slides

Si la géographie a longtemps et de manière quasi exclusive privilégié l’étude des réseaux techniques (réseaux de transport notamment, voir Barthelemy, 2011), l’analyse de réseau, entendue comme une boîte à outils méthodologiques plus que comme une théorie des phénomènes sociaux, permet d’enrichir les approches en géographie économique ou politique. Cette présentation montre comment divers outils et mesures, issus de la Social network analysis comme des Complex network studies, peuvent être mobilisés pour une réflexion relative à la régionalisation politique du monde. La première partie présente le cadre épistémologique et les emprunts disciplinaires effectués. Diverses hypothèses relatives à la régionalisation politique sont ensuite exposées ainsi que les principaux résultats obtenus avec des données issues de l’Assemblée générale de l’ONU (vote et parrainage de résolution, lien entre tats et groupes régionaux). Enfin, une troisième partie souligne les limites conceptuelles et méthodologiques des choix effectués et de possibles pistes de recherche permettant de les contourner. Si la pluri-disciplinarité paraît une voie prometteuse, les obstacles demeurent et ne se limitent pas à des choix lexicaux divergents. Références Marc Barthelemy, 2011, Spatial networks, Physics reports, 499, 1-101. Laurent Beauguitte, 2011, L’Assemblée générale de l’ONU de 1985 à nos jours. Essai de géographie politique quantitative, Thèse de doctorat, Université Denis Diderot Paris 7, disponible sur TEL.

Charles Bouveyron

Jeudi 03 octobre 2013 à 11h, salle 25-26/101

Slides

In the last two decades, many random graph models have been proposed to extract knowledge from networks. Most of them look for communities or more generally clusters of vertices with homogeneous connection profiles. While the first models focused on networks with binary edges only, extensions now allow to deal with valued networks. Recently, new models were also introduced in order to characterize connection patterns in networks through mixed memberships. This work was motivated by the need of analyzing a historical network where a partition of the vertices is given and where edges are typed. A known partition is seen as a decomposition of a network into subgraphs that we propose to model using a stochastic model with unknown latent clusters. Each subgraph has its own mixing vector and sees its vertices associated to the clusters. The vertices then connect with a probability depending on the subgraphs only, while the types of the edges are assumed to be sampled from the latent clusters. A variational Bayes expectation-maximization algorithm is proposed for inference as well as a model selection criterion for the estimation of the cluster number. Experiments are carried out on simulated data to assess the approach. The proposed methodology is then applied to an ecclesiastical network in merovingian Gaul. An R package, called Rambo, implementing the inference algorithm is available on the CRAN. This is a joint work with Y. Jernite, P. Latouche, P. Rivera, L. Jegou & S. Lamassé. Preprint available at http://arxiv.org/abs/1212.5497.

Benjamin Renoust

Mardi 17 septembre 2013 à 11h, salle 25-26/101

Slides

The analysis and exploration of a social network depends on the type of relations at play. Borgatti had proposed a type taxonomy organizing relations in four possible categories. Homophily (similarity) relationships form an important category where relations occur when entities of the network link whenever they exhibit similar behaviors. Examples are networks of co-author, where homophily between two persons follows from co-authorship; or network of actors having played under the supervision of the same movie director, for instance. Homophily is often embodied through a bipartite network where entities of a given type A (authors, movie directors) connect through entities of a different type B (papers, actors). A common strategy is then to project this bipartite graph onto a single-type network with entities of a same type A , possibly weighting edges based on how the type A entities interact with the type B entities underlying the edge. The resulting single-type network can then be studied using standard techniques such as community detection using edge density, or the computation of various centrality indices. This paper revisits this type of approach and introduces three measures derived from past work by Burt. Two entities of type B interact when they both induce a same edge between two entities of type A . The homogeneity of a subgroup thus depends on how intensely and how equally interactions occur between entities of type B giving rise to the subgroup. The measure thus differentiates between subgroups of type A exhibiting similar topologies depending on the interaction patterns of the underlying entities of type B.

François Queyroi

Mardi 09 juillet 2013 à 14h, salle 25-26/101

Slides

Des travaux en sociologie, géographie ou biologie suggèrent la présence d’une structure de communautés multi-niveaux au sein des réseaux complexes. Cette structure peut être modélisée par un partitionnement hiérarchique des sommets d’un graphe. Plusieurs algorithmes ont été proposés récemment pour répondre à ce problème. En revanche, la question de l’évaluation d’une partition hiérarchique a été peu étudiée. Je présenterai une généralisation des mesures de qualité additives au partitionnements multi-niveaux. Cette généralisation sinterprète comme un parcours des nœuds de l’arbre de partition réalisé en propageant le « gain » de chaque groupe à ses descendants. Je discuterai également plusieurs applications possible utilisant ce nouveau type de mesure ; notamment l’optimisation de la hiérarchie produite lors du déroulement de l’algorithme de Louvain.