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.

Dmitry Paranyushkin

Jeudi 27 juin 2013 à 11h, salle 55-65/211

Slides

The increasingly interconnected world brings up the new challenges related to rapid defragmentation of information and cognitive overload. The existing recommender systems and social networks tend to pack concepts and people into tightly-knit interest communities producing so-called filter bubbles » (Pariser 2011), making it difficult for such systems to evolve, adapt, and innovate. To address those challenges, we developed several social interaction strategies and online tools that are aimed at creating the new possibilities for communication and learning. The intention is to find out how the framework of networks can be used to enhance our learning strategies and expand ones capabilities for social interactions. Specifically, were interested in the notion of metastability the ability of a dynamical system to maintain several distinct latent states at once, which can interact and produce complex behavior on the global level. Metastable dynamics has been shown to be essential to adaptability of a complex system, which has to respond to the constantly changing environment. In this seminar we will present several case studies conducted by Nodus Labs. One of the projects we will present to exemplify our ideas is the online text network visualization tool – http://textexture.com – which can be used to represent any text as a network of interrelated concepts. The graph can then be used to get a general idea or a summary of the texts content, as well as the relations between the different topics present within the text. It can also be used for non-linear fast reading, allowing the users to create different narratives that are more relevant to their fields of interest. We will also present several case studies from our workshop and educational practice (see http://noduslabs.com for more information), where we created so-called constructed situations. In those carefully designed social settings we invited the participants to explore the basic ideas of network dynamics and metastability. The intention was to demonstrate how network thinking can be used to increase ones choices in any social or collaborative situation and lead to a better awareness of communicative dynamics within a group of people.

Jérôme François

Jeudi 06 juin 2013 à 11h30, salle 55-65/211

Slides

Security issues in Internet force the deployment of defensive measures to protect end users and Internet’s infrastructure itself. While a simple firewall would have been enough in the past, the trend is to promote a deeper analysis nowadays, in particular at the Internet operator level. Simple filtering has to be completed using more in-depth analysis tool. Detection of attacks may have to investigate multiple sources of data meantime and such sources, like network traffic captures, syslog, alerts or locations, may generate huge quantities of data. Forensics alleviates the real-time constraint but requires a perfect and global understanding of an intrusion to recover, protect in future and trigger legal actions as well. Hence, the problem is similar and finding evidences is like looking for a needle in a haystack. Therefore, the seminar will introduce several techniques to cope with big data issues in the context of security. Firstly, flow based methods will be presented as, for example, to track community of hosts participating to a botnet. This is possible by analyzing the traffic flow dependency in Internet and host relationships. Cyber-criminal organizations, like the Russian Business Network, are well organized and constructs their own Internet infrastructure and administrative domains which make them quite resistant to standard counter-measures like IP blacklisting. The seminar will then highlight how to reveal the underlying organization structure at a the Internet administrative domain level.

Darko Obradovic

Lundi 3 juin 2013 à 11h, salle 25-26/101

Blogs are among the first social media sources in the Web 2.0, and they remain influential until today, with a broad coverage of topics and languages. Due to their decentralised structure, sampling of data and network analyses are different from online social networking sites. We present a possible method and evaluation for identifying and measuring authoritative blogs with SNA, using k-cores, random graphs and community identification. These results are then applied in a prototype tool for the monitoring of specific topics, in combination with text-based subtopic detection, polarity classification and a trend detection.

Julien Darlay

Jeudi 23 mai 2013 à 11h, salle 25-26/101

Slides

La détection de communautés est un problème d’analyse de données où les informations peuvent être représentées comme un graphe. Les sommets correspondent aux observations et les arêtes représentent des interactions entre les observations. On cherche généralement une partition des sommets du graphe en classes induisant des sous-graphes denses, c’est-à-dire des groupes d’observations presque toutes deux à deux similaires. Dans ce contexte, nous proposons une fonction objectif pour le problème de partition de graphe basée sur la densité définie par Goldberg. La densité d’un graphe est le rapport entre le nombre d’arêtes et le nombre de sommets. La densité d’une partition d’un graphe est alors définie comme la somme des densités des sous-graphes induits par chaque classe de la partition. Nous montrons que le problème consistant à trouver la partition de densité maximale est un problème NP-difficile et non approximable. Lorsque le graphe est un arbre, nous montrons qu’il existe un algorithme polynomial pour trouver la partition optimale. Nous proposons une heuristique à base de recherche locale à l’aide de LocalSolver que nous évaluons sur des instances de la littérature.

Nicolas Tremblay

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

Slides

For data represented by networks, the community structure of the underlying graph is of great interest. A classical clustering problem is to uncover the overall best partition of nodes in communities. We work on a more elaborate description in which community structures are identified at different scales. To this end, we take advantage of the local and scale-dependent information encoded in graph wavelets. We classify nodes according to their wavelets or scaling functions, using, for instance, a scale-dependent modularity function. I will give an introduction on spectral graph wavelets and scaling functions, and talk about our recent advances. I will show results obtained on a graph benchmark having hierarchical structure and on real social networks. This is joint work with my supervisor Pierre Borgnat.

Sylvain Sené

Mercredi 13 mars 2013 à 14h, salle 25-26/105

Slides

Les réseaux d’automates sont des objets mathématiques mettant en jeu des entités (dites automates) qui interagissent les unes avec les autres au cours d’un temps discret. En voyant ces réseaux comme des modèles potentiels de systèmes d’interactions biologiques, l’idée générale de cet exposé est de montrer que l’informatique fondamentale permet d’accroître la connaissance des lois générales qui régissent le vivant. Plus précisément, nous utiliserons les réseaux d’automates booléens comme modèles de réseaux de régulation génétique. Dans ce cadre, nous focaliserons notre attention sur deux thèmes, développés en collaboration avec Mathilde Noual (I3S, UNS) et Damien Regnault (IBISC, UEVE) : – la combinatoire comportementale des cycles, objets dont on connaît l’importance sur la dynamique des réseaux depuis les travaux de René Thomas (1981) et de François Robert (1986), et – la robustesse structurelle des réseaux, au sens de René Thom (1972), que nous aborderons au travers de l’influence des modes de mise à jour, et qui nous mènera à l’étude d’une famille particulière de réseaux, les réseaux xor circulants.

Paulo Gonçalves

Jeudi 07 mars 2013 à 14h30, salle 25-26/101

Slides

Les travaux pionniers de Paxson (1994) et de Leland (1994), ont mis en évidence l’existence et identifié l’origine physique des propriétés d’auto-similarité et de dépendance à longue portée dans les signaux de trafic agrégé. Mais ces comportements ne sont pas les seules manifestations de phénomènes d’invariance d’échelle que l’on peut observer dans les réseaux de communications. Notamment, nous montrerons que le trafic agrégé présente en fait deux régimes de dépendance à long terme, d’origines différentes et correspondant chacun à une gamme d’échelle d’agrégation propre. Nous nous intéresserons ensuite à un flot TCP individuel et montrerons que celui-ci vérifie un principe empirique de grandes déviations que l’on sait caractériser analytiquement via un modèle de Markov. Ce résultat nous permet en particulier de généraliser la relation dite de Padhye à une distribution arbitraire des pertes de paquets. Dans un autre registre, nous proposerons enfin un modèle permettant de simuler la volatilité de charge d’un serveur de Vidéos à la Demande, mais qui vérifie un principe analogue de grandes déviations. Pour finir, nous ouvrirons alors quelques pistes de réflexion sur l’exploitation de ces propriétés d’invariance d’échelle particulières pour définir des politiques de management probabiliste des ressources. Travaux menés en collaboration avec P. Loiseau, S. Roy, T. Begin et J. Barral.

Nicolas Broutin

Jeudi 28 mars 2013 à 11h, salle 25-26/101

Slides

One of the main models for wireless networks is the random geometric graph. In this model, the graph gets connected with high probability only when the average degree is of the order of the logarithm of the size. Although it is not enourmous, it still raises the question of the scalability. Other models (irrigation graphs or Bluetooth graphs) have been devised that sparsify the graph using a local rule and hope that it remains connected. We prove tight threshold for the number of edges necessary for connectivity in this model, showing that the average degree must in particular tend to infinity to expect connectivity. This is joint work with L. Devroye, N. Fraiman and G. Lugosi.