Robin Lamarche-Perrin

Vendredi 15 mai 2015 à 11h, salle 24-25/405

Slides

Entre processus microscopiques et phénomènes émergents, l’analyse des systèmes complexes ne peut véritablement se passer d’une approche multi-échelles. Nous abordons en particulier deux problèmes : celui de la représentation multi-échelles de données structurées et celui de la prédiction multi-échelles des systèmes dynamiques. Premièrement, nous proposons d’exploiter des mesures classiques développées en théorie de l’information pour évaluer la pertinence des niveaux de représentation/prédiction en termes d’information et de complexité(gain d’entropie, divergence de Kullback-Leibler, Information Bottleneck). Le problème de la représentation/prédiction optimale est donc formalisé sous la forme d’un problème d’optimisation combinatoire à deux objectifs, visant à extraire et agréger l’information disponible au niveau microscopique pour apporter des éléments d’analyse macroscopique. Deuxièmement, afin d’engendrer des représentations exploitables en pratiques par les experts, nous garantissons leur cohérence avec les connaissances /a priori/ du système en contraignant l’espace de recherche du problème d’optimisation à partir des propriétés structurelles du système. Si le problème d’optimisation correspondant est NP-completen général, nous proposons néanmoins des algorithmes polynomiaux dans le cas de structures particulières (hiérarchies, ensembles d’intervalles, produit cartésien des deux structures). Cette approche est notamment appliquée à l’agrégation spatio-temporelle de données médiatiques pour l’analyse multi-échelles des relations internationales, et à la prédiction des dynamiques multi-échelles dans un modèle classique de diffusion d’opinion (Voter Model).

Pdraig Cunningham

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

As we recognise the importance of information in graph or network format it is useful to be able to quantify how similar one graph is to another. This is particularly useful in the context of ego networks, the local networks around a nodes. This seminar focuses on network motif profiles (i.e. counts of specific network motifs) to characterise networks in much the same way that a bag-of-words strategy allows text documents to be compared in a vector space framework. This strategy has a long history in social science and bioinformatics and has considerable potential in social network analysis. The seminar will outline the general strategy and present case-studies from Wikipedia, YouTube spam campaigns and peer to peer lending in the Prosper marketplace.

Alexandru Stan

Jeudi 12 mars 2015 à 11h, salle 24-25/405

This presentation aims to shed some light into the dynamics of market flash crashes by presenting several volume time models for the price evolution of financial assets. The theoretical foundation of our modeling relies upon the hypothesis that the flash crash represents the immediate repercussion of growing levels of order flow toxicity, as informed traders adversely select uninformed traders and, progressively, force them out of the market. We model the unfolding of this hostile behavior through a classic stochastic prey-predator model which segregates market transactions into toxic and harmless. Assuming that the price is following an Ito-process, we show how to predict the flash crash conditions during the flash crash unfolding. We also notice structural breaks in the dynamics of the market topology.

Stéphane Robin

Lundi 02 mars 2015 à 14h, salle 24-25/405

Slides

Les réseaux d’interaction constituent une façon naturelle de représenter sous forme de graphe les échanges ou relations existant entre un ensemble d’individus. Le modèle à blocs stochastiques (‘stochastic block-model’ ou SBM) est un des modèles les plus populaires qui permet de rendre compte de l’hétérogénéité observée dans ces graphes au travers d’une structure latente. D’un point de vue statistique, ce modèle présente des problèmes d’inférence spécifiques qui nécessitent le recours à des approximations. Les propriétés des modèles à variables latentes pour les graphes seront décrites dans le cadre des modèles graphiques et une approche variationnelle sera proposée pour contourner les difficultés d’inférence. On présentera plusieurs exemples et on discutera notamment de la prise en compte de co-variables dans ce type de modèle.

Laurent Vuillon

Jeudi 19 mars 2015 à 11h, salle 24-25/405

Slides

Protein oligomers are made by the association of protein chains via intermolecular amino acid interactions (interaction between subunits) forming so called protein interfaces. This talk proposes mathematical concepts to investigate the shape constraints on the protein interfaces in order to promote oligomerization. First, we focus on tiling the plane (2 dimensions) by translation with abstract shapes. Using the fundamental Theorem of Beauquier-Nivat, we show that the shapes of the tiles must be either like a square or like a hexagon to tile the whole plane. Second, we look in more details at the tiling of a cylinder and discuss its relevancy in constructing protein fibers. The universality of such « building » properties are investigated through biological examples. In a third part, we investigate the network properties of adjacent atoms in proteins.In particular we focus on real familial mutations involved in p53 related cancers. We show a local to global destabilization of the p53 protein, namely from the site of a single mutation changes are observed in the whole protein structure. Potential consequences and impacts on the fold and function of p53 are discussed.

Louisa Harutyunyan

Jeudi 05 février 2015 à 11h, salle 25-26/101

Flooding is an important primitive in mobile ad hoc networks (MANETs). Due to mobile nodes and possible change of location information, it is of importance for a flooded data packet to be received by every node, but at the same time to limit the number of forwarding nodes. Using a simple flooding scheme for such purposes causes redundant rebroadcasting at some nodes. To address redundant rebroadcasting at some nodes we propose a beacon-less flooding algorithm (HBLF) based on an overlayed hexagonal virtual network. We give sufficient condition that even in the presence of holes in the network, HBLF achieves full delivery. We also give further theoretic analysis of HBLF in regards to lower and upper bounds on the number of forwarding nodes, the dilation factor as well as the broadcast time of HBLF in a network with or without holes.

Narciso Pizarro

Jeudi 22 janvier 2015 à 11h, salle 25-26/105

Lorsque on examine la nature des relations sociales qui sont représentées avec des réseaux, on constate quil sagit, dans presque tous les travaux empiriques, directes, binaires, entre acteurs sociaux. Ces acteurs sont trop souvent des individus, et les rapports directs entre eux sont des interactions intersubjectives, ce qui produit à la fois des grands réseaux et des données peu fiables. Depuis Simmel, nous savons que linteraction binaire nest pas encore une relation sociale, quil faut au moins trois individus pour constituer latome du social. Dautre part les groupes sociaux sont bien moins nombreux que les individus, et cependant, leurs intersections permettent dindividualiser univoquement tous les membres dune population de grandeur N: Lorrain a prouvé que le nombre minimum de cercles sociaux C nécessaires pour cette identification est: C=log2N Donc, travailler avec des groupes nexclut pas identifier leurs membres, sil le fallait pour quelque raison que ce soit. En plus, les réseaux bipartites constituent un modèle de nimporte quel réseau. Et ils permettent plus aisément lidentification del classes déquivalence structurelle des points du réseau. Les concepts de place et de réseaux de places que jai proposé constituent une approximation intéressante pour aborder ce problème. Le problème de lidentification des cliques, informatiquement compliqué, peut être contourné en partant des données sur des groupes sociaux.

Mrton Karsai

Jeudi 15 janvier 2015 à 11h, salle 26-00/332

Slides

Diffusion of innovation can be interpreted as a social spreading phenomena governed by the impact of media and social interactions. Although these mechanisms have been identified by quantitative theories, their role and relative importance are not entirely understood, since empirical verification has so far been hindered by the lack of appropriate data. Here we analyse a dataset recording the spreading dynamics of the world’s largest Voice over Internet Protocol service to empirically support the assumptions behind models of social contagion. We show that the rate of spontaneous service adoption is constant, the probability of adoption via social influence is linearly proportional to the fraction of adopting neighbours, and the rate of service termination is time-invariant and independent of the behaviour of peers. By implementing the detected diffusion mechanisms into a dynamical agent-based model, we are able to emulate the adoption dynamics of the service in several countries worldwide. This approach enables us to make medium-term predictions of service adoption and disclose dependencies between the dynamics of innovation spreading and the socioeconomic development of a country.

Stéphane Raux

Jeudi 04 décembre 2014 à 11h, salle 26-00/332

Slides

Le succès de plateformes comme Facebook ou Twitter, qui s’appuient sur les interactions entre leurs utilisateurs pour artager des informations a profondément changé la manière dont nous utilisons le web. Cette thèse propose d’exploiter des méthodes d’analyse de grands graphes et de réseaux sociaux, mais aussi des techniques de *web mining* et d’analyse de texte pour élaborer des outils et des méthodes d’analyse des usages de ces sites de réseaux sociaux. Nous nous intéressons en particulier à deux types d’interactions : la conversation, que nous analysons à partir de réseaux de commentaires ou de mentions d’utilisateurs, et la recommandation, qui repose essentiellement sur des pratiques de citations de liens hypertextes. Une première analyse porte sur la dynamique des commentaires de Flickr et sur la manière dont ce réseau se construit. Nous proposons ensuite une méthode d’échantillonage de Twitter qui permet de capter en continu un corpus d’utilisateurs centré sur le web français, et d’élaborer une méthode de détection et de suivi des sujets à partir des citations de liens dans les données ainsi collectées. Il est ainsi possible de réaliser une typologie des utilisateurs en fonction de leur activité et de proposer une méthode de reconstitution des cascades de diffusion de liens sur Twitter. Ces travaux ont étés réalisés au sein de la société Linkfluence et ont donné lieu au développement de plusieurs programmes, dont le système de captation continue de messages sur Twitter et l’application Algopol, qui a permis de recruter plus de 12 000 participants pour une enquête sociologique et de collecter leurs profils Facebook dans le cadre d’un projet de recherche pluridisciplinaire.

Soumajit Pramanik

Vendredi 03 octobre 2014 à 11h, salle 26-00/101 (Noguez)

Slides

Social information flow is basically the spread of any information among socially connected (friends, family, colleagues etc.) people. In real life, this type of information flow is very hard to capture but in case of digital world this phenomenon can be investigated with the help of Online Social Networks (OSNs) like Facebook, Twitter, Foursquare etc. In OSNs, whenever a user shares any information, her direct neighbors (friends/followers) can automatically get exposed to that and may decide to propagate it or not. This type of information propagation can be logged and used as a proxy of real-world social information diffusion. In case of information propagation in OSNs, there is a specific role of mediators/information-brokers who help to spread the information beyond the immediate reach of social neighbors. For instance, in Twitter, « Mention » is such a mediator utility. « Mention » is enabled in a tweet by adding « @username ». All the users mentioned in a tweet will receive a mention notification and are able to retrieve the tweet from their personal « Mention » tabs. So, by using « Mention », one can draw attention from a specific user (may not belong to his set of followers), or highlight a place or organization anytime. So, the main research question we are trying to address is- « how this mediators (e.g. « Mention ») facilitates any information flow in an OSN (e.g. Twitter). »

Ahmed Wade

Jeudi 02 octobre 2014 à 11h, salle 25-26/101

Slides

Dans cet exposé, je vais parler de l’étude des graphes dynamiques T-intervalle-connexes du point de vue du temps nécessaire à leur exploration par une entité mobile (agent). Un graphe dynamique est T-intervalle-connexe (T >= 1) si pour chaque fenêtre de T unités de temps, il existe un sous-graphe couvrant connexe stable. Cette propriété de stabilité de connexion au cours du temps a été introduite par Kuhn, Lynch et Oshman (STOC 2010).

Arnaud Browet

Jeudi 18 septembre à 11h, salle 25-26/101

Slides

Network clustering, also known as graph partitioning, has focused the attention of many researchers during the last decade due to the increasing number of potential applications of network science. However, the amount of collected data makes their analysis a real challenge and dedicated algorithms must be developed in order to comprehend them. In this talk, I will first introduce recent developments on community detection and present a fast and highly parallelizable algorithm which outperforms existing methods in term of computational time. Yet, a community structure is not always representative of the actual distribution of the nodes in a network. For example, bipartite or cycle graphs often do not contain communities and are in fact more closely represented by what is known as a role structure. In a second part of the talk, I will present a pairwise node similarity measure which allows to extract those role structures and demonstrate its performance on synthetic and real graphs. Website: http://perso.uclouvain.be/arnaud.browet/ Author Thesis:http://perso.uclouvain.be/arnaud.browet/files/thesis/thesis.pdf  

Lautaro Dolberg

Jeudi 09 octobre 2014 à 10h, salle 25-26/101

Slides

DNS is an essential service in the Internet as it allows to translate human language based domain names into IP addresses. DNS traffic reflects the user activities and behaviours It is thus a helpful source of information in the context of large scale network monitoring. In particular, passive DNS monitoring garnered much interest for the security perspectives by highlighting the services the machines want to access. Im going to show a method for assessing the dynamics of the match between DNS names and IP subnetworks using an efficient aggregating scheme combined with relevant steadiness metrics. The evaluation relies on real data collected over several months and is able to detect anomalies related to malicious domains.

Artur Ziviani

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

Slides

The talk will present a recent on-going work on the modeling of time-varying multilayer networks developed collaboratively between LNCC in Brazil and ENS-Lyon/INRIA in France. The proposed model has a strong relationship with traditional directed graphs, thus leading to a useful theoretical framework for the analysis of complex networked systems. In the specific case of time-varying graphs, we show that this theoretical framework is a unifying model able to represent several previous (classes of) models for dynamic networks found in the recent literature, which in general are unable to represent each other.

Sebastiano Vigna

Mercredi 28 mai 2014 à 11h, salle 25-26/101

Slides

We approach the problem of computing geometric centralities, such as closeness and harmonic centrality, on very large graphs; traditionally this task requires an all-pairs shortest-path computation in the exact case, or a number of breadth-first traversals for approximated computations, but these techniques yield very weak statistical guarantees on highly disconnected graphs. We rather assume that the graph is accessed in a semi-streaming fashion, that is, that adjacency lists are scanned almost sequentially, and that a very small amount of memory (in the order of a dozen bytes) per node is available in core memory. We leverage the newly discovered algorithms based on HyperLogLog counters, making it possible to approximate a number of geometric centralities at a very high speed and with high accuracy. While the application of similar algorithms for the approximation of closeness was attempted in the MapReduce framework, our exploitation of HyperLogLog counters reduces exponentially the memory footprint, paving the way for in-core processing of networks with a hundred billion nodes using “just” 2TiB of RAM. Moreover, the computations we describe are inherently parallelizable, and scale linearly with the number of available cores.

Baptiste Mélès

Jeudi 12 juin 2014 à 11h, salle 25-26/101

Comment les informaticiens inventent-ils des concepts ? L’informaticien a parfois l’image d’un bricoleur d’une nouvelle génération, dont les concepts, en compromission permanente avec les contingences de la matière, n’auraient pas la pureté de sciences plus nobles que seraient la logique ou les mathématiques. Telle est la conception que nous remettrons en cause. Le philosophe et résistant Jean Cavaillès (1903-1944) a proposé dans son ouvrage posthume Sur la Logique et la théorie de la science (1947) ce que l’on peut voir comme une grammaire de l’invention des concepts mathématiques, dont les deux procédés principaux s’appellent paradigme et thématisation. En nous appuyant sur l’histoire des concepts de fichier et de processus de CTSS à Unix, nous montrerons que l’on retrouve ces deux procédés, et peut-être plus encore, dans l’invention des concepts informatiques. L’invention de concepts informatiques serait dès lors aussi pure, d’un point de vue rationnel, que l’invention des concepts mathématiques. Ceci nous conduira à caractériser l’informatique comme une science a priori — c’est-à-dire indépendante de toute expérience — à part entière, et dont l’apport est irréductible à la logique et aux mathématiques : bien plutôt qu’une science a posteriori des ordinateurs, elle peut être vue comme la science a priori de l’inscription des processus rationnels dans la matière. Nous conclurons en montrant sur quelques exemples en quoi l’informatique déborde largement la science des ordinateurs.  

Anh-Dung Nguyen

Vendredi 09 mai 2014 à 14h, salle 25-26/101

Slides

La science des réseaux dynamiques est un domaine de recherche très récent mais couvre un large champ d’applications, allant des réseaux biologiques aux réseaux sociaux, en passant par les réseaux informatiques tel que les réseaux mobiles ad hoc et les DTNs. Ces réseaux sont caractérisés par leur évolution spatio-temporelle : les noeuds et liens apparaissent et disparaissent au cours du temps, contrairement aux réseaux statiques dans lesquels les noeuds et liens sont fixes. En conséquence, les modèles classiques pour les réseaux statiques ne sont pas adaptés ou ne parviennent pas à expliquer les phénomènes, propriétés ou processus comme la diffusion d’information dans ces réseaux. Ce séminaire abordera des nouveaux modèles permettant de capturer fidèlement deux caractéristiques spatio-temporelles des réseaux dynamiques : le phénomène « petit-monde » et le niveau de désordre dans les contacts. Nous confronterons ces modèles avec des analyses intensives de traces réelles. Nous montrerons ensuite l’impact de ces caractéristiques sur la capacité de diffusion d’informations de ces réseaux. Enfin, une application sur le routage efficace dans les réseaux mobiles opportunistes sera présentée.

Huan Liu

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

Slides

Social media mining differs from traditional data mining in many ways, offering unique opportunities to advance data mining. It consists of massive amounts of user-generated content and extensive networked data. As detailed in our latest textbook “Social Media Mining: An Introduction”, we face novel challenges such as “the evaluation dilemma” and “the noise removal fallacy”. We will introduce these challenges and present some recent research issues we encounter – a big-data paradox unique to social media where many social networking sites are present but only minimum information is available, and whether distrust is relevant and useful in social media mining.  We will exemplify the intricacies of social media data, and show how to exploit unique characteristics of social media data in developing novel algorithms and tools for social media mining. The textbook’s pdf free download is at http://dmml.asu.edu/smm/   Dr. Huan Liu is a professor of Computer Science and Engineering at Arizona State University. He obtained his Ph.D. in Computer Science at University of Southern California and B.Eng. in CSEE at Shanghai JiaoTong University. At Arizona State University, he was recognized for excellence in teaching and research in Computer Science and Engineering and received the 2014 President’s Award for Innovation. His research interests are in data mining, machine learning, social computing, and artificial intelligence, investigating interdisciplinary problems that arise in many real-world, data-intensive applications with high-dimensional data of disparate forms such as social media. His well-cited publications include books, book chapters, encyclopedia entries as well as conference and journal papers. He is a co-author of Social Media Mining: An Introduction by Cambridge University Press. He serves on journal editorial boards and numerous conference program committees, is an IEEE Fellow and a member of several professional societies. http://www.public.asu.edu/~huanliu  

Christophe Crespelle

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

Slides

We analyse a fine-grain trace of contact data collected during 6 months on the entire population of a rehabilitation hospital. We investigate both the graph structure of the average daily contact network and the temporal structure of the evolution of contacts in the hospital. Our main results are to unveil striking properties of these two structures in the considered hospital, and to present a methodology that can be used for analysing any dynamic complex network where nodes are classified into groups.

Daniel Bernardes

Vendredi 21 mars 2014 à 14h, salle 25-26/105

Understanding information diffusion on complex networks is a key issue from a theoretical and applied perspective. Epidemiology-inspired SIR models have been proposed to model information diffusion. Recent papers have analyzed this question from a data-driven perspective, using on-line diffusion data. We follow this approach, investigating if epidemic models, calibrated with a systematic procedure, are capable of reproducing key structural properties of spreading cascades. We first identified a large-scale, rich dataset from which we can reconstruct the diffusion trail and the underlying network. Secondly, we examine the simple SIR model as a baseline model and conclude that it was unable to generate structurally realistic spreading cascades. We extend this result examining model extensions which take into account heterogeneities observed in the data. In contrast, similar models which take into account temporal patterns (which can be estimated with the interaction data) generate more similar cascades qualitatively. Although one key property was not reproduced in any model, this result highlights the importance of temporal patterns to model diffusion phenomena. We have also analyzed the impact of the underlying network topology on synthetic spreading cascade structure. We have simulated spreading cascades in similar conditions as the real cascades observed in our dataset, namely, with the same time constraints and with the same « seeds ». Using a sequence of uniformly random graphs derived from the real graph and with increasing structure complexity, we have examined the impact of key topological properties for the models presented previously. We show that in our setting, the distribution of the number of neighbors of seed nodes is the most impacting property among the investigated ones.