↓

L’analyse des opinions politiques sur Twitter : Défis et opportunités d’une approche multi-échelle

Marta Severo and Robin Lamarche-Perrin

Revue française de sociologie: Big Data, Sociétés et Sciences Sociales, 2018

Des blogs et forums aux pages Facebook et comptes Twitter, le récent déluge des données numériques du web a fortement affecté la recherche en sciences sociales. Cette nouvelle catégorie d’information, utile à l’extraction des opinions politiques, se présente comme une alternative aux techniques traditionnelles telles que les sondages. Premièrement, en réalisant un état de l’art des études de l’opinion s’appuyant sur les données Twitter, cet article vise à mettre en relation les méthodes d’analyse utilisées dans ces études et les définitions de l’opinion politique qui y sont suggérées. Deuxièmement, cet article étudie la faisabilité de réaliser des analyses multi-échelles en sciences sociales concernant l’étude de l’opinion politique en exposant les mérites de plusieurs méthodes, allant des méthodes orientées contenus aux méthodes orientées interactions, de l’analyse statistique à l’analyse sémantique, des approches supervisées aux approches non supervisées. Le résultat de notre démarche est ainsi d’identifier les tendances futures de la recherche en sciences sociales concernant l?étude de l’opinion politique.

Caractériser lanalogie entre automates cellulaires déterministes et systèmes physiques

Lionel Tabourier

Lato Sensu, Revue de la Société de Philosophie des Sciences, Vol.5, n°2, 2018

La classification de Wolfram des automates cellulaires déterministes repose sur l’analogie entre le comportement dynamique des automates et celui de systèmes physiques au cours d’une transition de phase. Pour évaluer la valeur scientifique de la classification, longuement débattue, on doit s’interroger sur les caractéristiques de cette analogie. Nous établissons ici quels éléments, présents dans les transitions de phase, n’ont pas d’équivalent dans le domaine des automates. Ensuite, nous discutons la notion de potentiel d’une analogie en la comparant à deux autres exemples de la littérature.

Centrality metrics in dynamic networks: a comparison study

Marwan Ghanem, Clémence Magnien and Fabien Tarissan

IEEE Transactions on network science and engineering, 2018

For a long time, researchers have worked on defining different metrics able to characterize the importance of nodes in static networks. Recently, researchers have introduced extensions that consider the dynamics of networks. These extensions study the time-evolution of the importance of nodes, which is an important question that has yet received little attention in the context of temporal networks. They follow different approaches for evaluating a node’s importance at a given time and the value of each approach remains difficult to assess. In order to study this question more in depth, we compare in this paper a method we recently introduced to three other existing methods. We use several datasets of different nature, and show and explain how these methods capture different notions of importance. We also show that in some cases it might be meaningless to try to identify nodes that are globally important. Finally, we highlight the role of inactive nodes, that still can be important as a relay for future communications.

Download

Quantifying the diversity in users activity: an example study on online music platforms

Poulain Rémy and Tarissan Fabien

SNAMS, 2018

Whether it be through a problematic related to information ranking (e.g. search engines) or content recommendation (on social networks for instance), algorithms are at the core of processes selecting which information is made visible. Those algorithmic choices have in turn a strong impact on users activity and therefore on their access to information. This raises the question of measuring the quality of the choices made by algorithms and their impact on the users. As a first step into that direction, this paper presents a framework to analyze the diversity of the information accessed by the users. By depicting the activity of the users as a tripartite graph mapping users to products and products to categories, we analyze how categories catch users attention and in particular how this attention is distributed. We then propose the \emph{(calibrated) herfindahl diversity} score as a metric quantifying the extent to which this distribution is diverse and representative of the existing categories. In order to validate this approach, we study a dataset recording the activity of users on online music platforms. We show that our score enables to discriminate between very specific categories that capture dense and coherent sub-groups of listeners, and more generic categories that are distributed on a wider range of users. Besides, we highlight the effect of the volume of listening on users attention and reveal a saturation effect above a certain threshold.

Download

Mining the Integrated Connectedness of Biomedical Systems

Prof. Dr. Natasa Przulj

December 7th 2018, 14:00. Salle 24-25/405, LIP6 – UMPC, Sorbonne Université. 4 Place Jussieu, 75005 Paris.

We are faced with a flood of molecular and clinical data. Various bio-molecules interact in a cell to perform biological function, forming large, complex systems. Large-scale patient-specific omics datasets are increasingly becoming available, providing heterogeneous, but complementary information about cells, tissues and diseases. The challenge is how to mine these interacting, complex, complementary data systems to answer fundamental biological and medical questions.  Dealing with them is nontrivial, because many questions we ask to answer from them fall into the category of computationally intractable problems, necessitating the development of heuristic methods for finding approximate solutions. We develop methods for extracting new biomedical knowledge from the wiring patterns of systems-level, heterogeneous, networked biomedical data.  Our methods link the patterns in molecular networks and the multi-scale network organization with biological function.  In this way, we translate the information hidden in the wiring patterns into domain-specific knowledge. In addition, we introduce a versatile data fusion (integration) framework that can effectively integrate the information obtained from mining molecular networks with patient-specific somatic mutation data and drug chemical data to address key challenges in precision medicine: better stratification of patients, prediction of driver genes in cancer, and re-purposing of approved drugs to particular patients and patient groups. Our new methods stem from novel network science approaches coupled with graph-regularized non-negative matrix tri-factorization, a machine learning technique for dimensionality reduction and co-clustering of heterogeneous datasets. We utilize our new framework to develop methodologies for performing other related tasks, including disease re-classification from modern, heterogeneous molecular level data, inferring new Gene Ontology relationships, and aligning multiple molecular networks.

From a static to a dynamic analysis of complex networks (soutenance HDR)

Lionel Tabourier

September 24th 2018, 11am, room 25-26/105, Jussieu

Slides

Contacts entre individus, interactions sociales, transactions économiques ou encore machines échangeant des paquets d’information, tous ces systèmes ont en commun d’être constitués d’éléments en interaction et dépourvus de coordination par un « cerveau central ». Par conséquent, la structure de leurs interactions résultent de processus décentralisés, qui sont souvent mal connus. Depuis les années 90, il a été mis en évidence que la représentation en graphe de tels systèmes amenait à la découverte de propriétés communes, cela a permis l’utilisation de méthodes transverses pour les décrire et en comprendre les mécanismes sous-jacents. Ces études ont ensuite évolué pour constituer un champ de recherche à part entière : l’analyse de réseaux complexes. Parce qu’elles sont simples et qu’il existe un important volume de connaissance en théorie et en algorithmique de graphes, les représentations en graphes de tels systèmes en interaction ont mené à d’importants succès. Cependant, l’accès généralisé à des jeux de données en ligne a également mis en évidence la nécessité de prendre en compte l’aspect fondamentalement dynamique des données d’interaction. Mon travail de recherche touche à plusieurs aspects de l’évolution d’une représentation statique à une représentation dynamique de telles données. Celui-ci est organisé en trois axes distincts : le premier concerne la description de processus dynamiques sur des réseaux évoluant dans le temps, et plus précisément les phénomènes de diffusion. Le second axe se rapporte au problème de la prévision d’interactions dans un réseau temporel. Enfin, le troisième s’interroge sur la modélisation de la structure des interactions au moyen de réseaux aléatoires qui imitent la structure des données réelles.

Two ways you did not know mobile networks could be useful

Marco Fiore

Monday, September 24th 2018,  4pm, room 24-25/405

Slides

Mobile networks provide support to a variety of communication-based services that are steadily changing our lives. However, they are also pervasive infrastructures that can be used in unconventional ways unrelated to communication. Specifically, mobile networks can be seen as large-scale remote sensing platform capable of providing fine-grained information about a large (and increasing) fraction of the worldwide population. In this talk, I will discuss two case studies of remote sensing based on mobile networks: land use mapmaking, i.e., the detection of arrangements and activities in a target geographical region, and population density estimation, i.e., the monitoring of dwelling units and people presence. Solutions to both these problems have important applications in, e.g., urban planning and transportations, and can benefit from approaches that take advantage of the mobile network infrastructure.

Pattern Matching in Link Streams: Timed-Automata with Finite Memory

Clément Bertrand, Frédéric Peschanski, Hanna Klaudel and Matthieu Latapy

Scientific Annals of Computer Science, 2018

Link streams model the dynamics of interactions in complex distributed systems as sequences of links (interactions) occurring at a given time. Detecting patterns in such sequences is crucial for many applications but it raises several challenges. In particular, there is no generic approach for the specification and detection of link stream patterns in a way similar to regular expressions and automata for text patterns. To address this, we propose a novel automata framework integrating both timed constraints and finite memory together with a recognition algorithm. The algorithm uses structures similar to tokens in high-level Petri nets and includes non-determinism and concurrency. We illustrate the use of our framework in real-world cases and evaluate its practical performances.

Download

Degree-based Outliers Detection within IP Traffic Modelled as a Link Stream

Audrey Wilmet, Tiphaine Viard, Matthieu Latapy and Robin Lamarche-Perrin

TMA Conference 2018, Vienna

Precise detection and identification of anomalous events in IP traffic are crucial in many applications. This paper intends to address this task by adopting the link stream formalism which properly captures temporal and structural features of the data. Within this framework we focus on finding anomalous behaviours with the degree of IP addresses over time. Due to diversity in IP profiles, this feature is typically distributed heterogeneously, preventing us to find anomalies. To deal with this challenge, we design a method to detect outliers as well as precisely identify their cause in a sequence of similar heterogeneous distributions. We apply it to a MAWI capture of IP traffic and we show that it succeeds at detecting relevant patterns in terms of anomalous network activity.Degree-based Outliers Detection within IP Traffic Modelled as a Link Stream

Download

Examining Supreme Court Networks to Understand its Operation

Patrick Doreian

Friday, June 22th 2018, 14h, salle 26-00/101

The nature of the Supreme Court, its decisions, the principle of Stare Decisis are described. This is followed by a listing of the Supreme Court networks that are considered. This includes: the citation network of decisions citing earlier decisions (1789-2001); coherent clusters of decisions obtained by examining the extent to which they are co-cited by later decisions; signed two-mode networks featuring Justices and their votes for annual terms of the Court; one-mode signed networks of justices with the extent to which they vote with or against each other; and signed networks of Courts overturning decisions of prior Courts or their own decisions. Strategies for analyzing these networks are presented along with the subsequent results. Throughout, the network results are linked to substantive topics and constitutional principles. A long-term research agenda is presented.

Hierarchical Clustering Beyond the Worst-Case

Vincent Cohen-Addad

Wednesday, May 16th, 2018, 11h, salle 26-00/101, Campus Jussieu

Slides

Hiererachical clustering, that is computing a recursive partitioning of a dataset to obtain clusters at increasingly finer granularity is a fundamental problem in data analysis. Although hierarchical clustering has mostly been studied through procedures such as linkage algorithms, or top-down heuristics, rather than as optimization problems, Dasgupta recently proposed an objective function for hierarchical clustering and initiated a line of work developing algorithms that explicitly optimize an objective. In this paper, we consider a fairly general random graph model for hierarchical clustering, called the hierarchical stochastic block model (HSBM), and show that in certain regimes the SVD approach of McSherry combined with specific linkage methods results in a clustering that give an O(1) approximation to Dasguptas cost function. Finally, we report empirical evaluation on synthetic and real-world data showing that our proposed SVD-based method does indeed achieve a better cost than other widely-used heurstics and also results in a better classification accuracy when the underlying problem was that of multi-class classification.

Applications of Graph Sampling

Shweta Jain

Thursday, May 3th, 2018, 11h, salle 26-00/101, Campus Jussieu

Slides

Large graphs have become commonplace making many of the traditional graph-theoretic algorithms infeasible. Moreover, sometimes we don’t have access to the whole graph. This has led us to revisit graph algorithms and necessitated graph sampling. In this talk, I will explore 2 applications of graph sampling. In the first application, called TurnShadow, we propose a method for efficient counting of k-cliques. It uses the classic result called Turn’s theorem to give provable error bounds. We also do extensive evaluation of the method on real-world graph instances and demonstrate that it is fast and extremely accurate. In the second application, we propose a method called SADDLES to estimate the degree distribution when we are given only limited access to the graph, and accessing the graph is costly. We assume we have access to uniform at random (u.a.r ) vertex, u.a.r neighbor of a vertex and the degree of the vertex. We compare SADDLES with many other state-of-the-art methods and demonstrate that SADDLES requires far fewer samples to achieve the same degree of accuracy.    

Story Forest: Organizing Massive News Documents via AI and Natural Language Processing

Di Niu

Friday, May 4th, 2018, 11h, salle 26-00/428, Campus Jussieu

Slides

I will describe our recent experience of implementing a news content organization system in collaboration with Tencent that can discover hot events from vast streams of breaking news and connect events into stories for easy viewing. Our real-world system has distinct requirements in contrast to previous studies on document topic modeling and detection, in that 1) an event does not only contain articles of a similar topic, but is a cluster of documents that report exactly the same physical incidence; 2) we must evolve news stories in a logical and online manner. In solving these challenges, we propose Story Forest, a state-of-the-art news content organization system based on artificial intelligence and natural language processing. I will briefly describe the key enabling technologies in Story Forest, including identifying the relationship between text objects, e.g., whether they talk about the same event or whether one article is a follow-up of another, based on deep learning. Our system has been deployed in Tencent QQ Browser mobile app.

OLCPM: An Online Framework for Detecting Overlapping Communities in Dynamic Social Networks

Souâad Boudebza, Rémy Cazabet, Faiçal Azouaou and Omar Noual

Computer Communications, Elsevier, In press, 2018.

Community structure is one of the most prominent features of complex networks. Community structure detection is of great importance to provide insights into the network structure and functionalities. Most proposals focus on static networks. However, finding communities in a dynamic network is even more challenging, especially when communities overlap with each other. In this article , we present an online algorithm, called OLCPM, based on clique percolation and label propagation methods. OLCPM can detect overlapping communities and works on temporal networks with a fine granularity. By locally updating the community structure, OLCPM delivers significant improvement in running time compared with previous clique percolation techniques. The experimental results on both synthetic and real-world networks illustrate the effectiveness of the method.

Download

When Diversity Is Needed… But Not Expected!

Sylvain Castagnos

Thursday, May 17th, 2018, 11h, salle 26-00/101, Campus Jussieu

Slides

Recent studies have highlighted the correlation between users’ satisfaction and diversity within recommenders, especially the fact that diversity increases users’ confidence when choosing an item. Understanding the reasons of this positive impact on recommenders is now becoming crucial. Based on this assumption, we designed a user study that focuses on the utility of this new dimension, as well as its perceived qualities. This study has been conducted on 250 users and it compared 5 recommendation approaches, based on collaborative filtering, content-based filtering and popularity, along with various degrees of diversity. Results show that, when recommendations are made explicit, diversity may reduce users’ acceptance rate. However, it helps increasing users’ satisfaction. Moreover, this study highlights the need to build users’ preference models that are diverse enough, so as to generate good recommendations.

Enumerating maximal cliques in link streams with durations

Tiphaine Viard, Clémence Magnien, and Matthieu Latapy

Information Processing Letters 133 (2018), p. 44-48

Link streams model interactions over time, and a clique in a link stream is defined as a set of nodes and a time interval such that all pairs of nodes in this set interact permanently during this time interval. This notion was introduced recently in the case where interactions are instantaneous. We generalize it to the case of interactions with durations and show that the instantaneous case actually is a particular case of the case with durations. We propose an algorithm to detect maximal cliques that improves our previous one for instantaneous link streams, and performs better than the state of the art algorithms in several cases of interest.

Download

Discovering Patterns of Interest in IP Traffic Using Cliques in Bipartite Link Streams

Tiphaine Viard, Raphaël Fournier-S’niehotta, Clémence Magnien and Matthieu Latapy

International Conference on Complex Networks (CompleNet), 2018.

Studying IP traffic is crucial for many applications. We focus here on the detection of (structurally and temporally) dense sequences of interactions, that may indicate botnets or coordinated network scans. More precisely, we model a MAWI capture of IP traffic as a link streams, i.e. a sequence of interactions (t1,t2,u,v) meaning that devices u and v exchanged packets from time t1 to time t2 . This traffic is captured on a single router and so has a bipartite structure: links occur only between nodes in two disjoint sets. We design a method for finding interesting bipartite cliques in such link streams, i.e. two sets of nodes and a time interval such that all nodes in the first set are linked to all nodes in the second set throughout the time interval. We then explore the bipartite cliques present in the considered trace. Comparison with the MAWILab classification of anomalous IP addresses shows that the found cliques succeed in detecting anomalous network activity.

Stream Graphs and Link Streams for the Modeling of Interactions over Time

Matthieu Latapy, Tiphaine Viard and Clémence Magnien

Social Networks Analysis and Mining, 8: 61, 2018

Graph theory provides a language for studying the structure of relations, and it is often used to study interactions over time too. However, it poorly captures the both temporal and structural nature of interactions, that calls for a dedicated formalism. In this paper, we generalize graph concepts in order to cope with both aspects in a consistent way. We start with elementary concepts like density, clusters, or paths, and derive from them more advanced concepts like cliques, degrees, clustering coefficients, or connected components. We obtain a language to directly deal with interactions over time, similar to the language provided by graphs to deal with relations. This formalism is self-consistent: usual relations between different concepts are preserved. It is also consistent with graph theory: graph concepts are special cases of the ones we introduce. This makes it easy to generalize higher-level objects such as quotient graphs, line graphs, k-cores, and centralities. This paper also considers discrete versus continuous time assumptions, instantaneous links, and extensions to more complex cases.

Comparaison de mesures de centralité basées sur les plus courts chemins dans les réseaux dynamiques

Marwan Ghanem , Clémence Magnien, Fabien Tarissan

Extraction et Gestion de Connaissances (EGC 2018)

Définir l’importance des noeuds dans les réseaux statiques est une question de recherche très étudiée depuis de nombreuses années. Dernièrement, des adaptations des métriques classiques ont été proposées pour les réseaux dynamiques. Ces méthodes reposent sur des approches très différentes dans leur façon d’évaluer l’importance des noeuds à un instant donné. Il est donc nécessaire de pouvoir les évaluer et les comparer. Dans cet article, nous comparons trois approches existes pour mieux comprendre ce qui les différencie. Nous montrons que la nature des jeux de données influe grandement sur le comportement des méthodes, et que pour certains d’entre eux, la notion d’importance n’est pas toujours  pertinente.

↑