Past Events.

Maximilien Danisch, Telecom ParisTech
Towards understanding and leveraging the structure of real-world graphs
Campus Jussieu, Salle 26-00/124 à 11h00
Real-world graphs (a.k.a. complex networks) are ubiquitous: the web, Facebook, Twitter, brain networks, protein interaction networks, etc. Studying these graphs and solving computational problems on them (say maximum clique, partitioning or dense subgraph) has applications in many fields.
I will first show that the structure of some real-world graphs is special. In particular, they are not adversarial and some difficult problems (say NP-complete or NP-hard problems) can be solved on some huge real-world graphs (say 2G edges or more).
I will then present two works along the lines of "understanding and leveraging the structure of real-world graphs in order to build better algorithms": (i) Enumerating all k-cliques and (ii) Computing the density-friendly graph decomposition.

Nicolas Bousquet, LIRIS
Coalition games on interaction graphs
15 Novembre 2016, salle 26-00/124
We consider cooperative games where the viability of a coalition is determined by whether or not its members have the ability to communicate amongst themselves. This necessary condition for viability was proposed by Myerson and is modeled via an interaction graph; a coalition S of vertices is then viable if and only if the graph induced graph S is connected. The non-emptiness of the core of a coalition game can be tested by a well-known covering LP. Moreover, the integrality gap of its dual packing LP defines exactly the multiplicative least-core and the relative cost of stability of the coalition game. This gap is upper bounded by the packing-covering ratio which is known to be at most the treewidth of the interaction graph plus one. We examine the packing-covering ratio and integrality gaps of graphical coalition games in more detail. First we introduce a new graph parameter, called the vinewidth (a parameter derived from the treewidth), which characterizes the worst packing-covering ratio. Then we will show that this new parameter correctly evaluates both primal and dual integrality gaps. Joint work with Zhentao Li and Adrian Vetta.

Ingo Scholtes, ETH Zürich
Mining Time-stamped Network Data – Spectral Methods and Centrality Measures
Mercredi 19 Octobre 2016 à 11h00 salle 24-25/405
Recent research has highlighted limitations of studying complex systems with time-varying topologies from the perspective of static, time-aggregated networks. Non-Markovian characteristics resulting from the specific ordering of interactions in temporal networks were identified as one important mechanism that alters causality and affects dynamical processes. So far, an analytical explanation for this phenomenon and for the significant variations observed across different systems is missing.   Summarizing our recent research in this area, in this talk I will introduce a framework that allows to analyze temporal networks with non-Markovian characteristics. The framework is based on higher-order aggregate networks, a simple generalization of the commonly used static representation of temporal network data. I will show that spectral properties of such higher-order aggregate networks can explain the slow-down of diffusion processes compared to aggregate networks, which has been observed in a number of empirical data sets. I further show that we can derive an exact analytical prediction for the magnitude of this change compared to the weighted, time-aggregate network. I finally present recent results on the analysis of node centralities in non-Markovian temporal networks, concluding that this approach provides interesting perspectives for (i) temporal community detection by spectral clustering, (ii) refined measures of centrality for time-evolving networks, and (iii) analytical studies of dynamical processes in complex systems with time-evolving interaction topologies.

David Coudert, INRIA Sophia Antipolis
On the notion of hyperbolicity in graphs
Salle 24-25/405
The Gromov hyperbolicity is an important parameter for analyzing complex networks since it is a measure of the tree-likeness of a graph from a metric perspective. This notion has been recently applied in different contexts, such as the design of routing schemes, network security, computational biology, the analysis of graph algorithms, and the classification of complex networks. For instance, it gives bounds on the best possible stretch of some greedy-routing schemes in Internet-like graphs.
The best known algorithm for computing hyperbolicity has running-time O(n^{3.69}), which is clearly prohibitive for big graphs.
In this talk, we will present recent advances on the computation of this parameter. We will present an algorithm that performs well in practice. Although its time complexity is in O(n^4), it can compute the hyperbolicity of graphs with 100.000 nodes in short time. We will discuss the limitations of this algorithm and related open problems. We will also provide some results on the time complexity lower bound. In addition, we will show how to use some simple properties of the graph to get tight bounds on its hyperbolicity, e.g., being bipartite, a line graph, vertex transitive, etc. These properties are used for establishing bounds on the hyperbolicity of various interconnection network topologies proposed for large data centers.

Mattias Mano, Ecole Polytechnique, Palaiseau
Classification of online discussions: is tree structure sufficient enough?
Vendredi 30 Septembre à 10h30, Salle 26-00/332
Over the past years, online communities have considerably grown. Especially, a new kind of forums emerged: the "Questions and Answers" (Q&A) forums. They cover lots of different fields, from opinion questions (such as Yahoo! Answers, Reddit, Quora, ...) to really technical questions in Computer Science (Stack Overflow, Bugzilla, ...) or in Mathematics (Math Overflow). We study the opinion forum "Reddit - Change My View". Participants debate on society subject. Using graph theory modeling, I wonder if structural informations of the discussion (graph) are sufficient enough to be characteristic of what happen in the discussion.

Christophe Paul, AlGCo, LIRMM, Montpellier
Parameterized complexity: from graph minor theory to efficient algorithms
Vendredi 08 juillet 2016 à 11h, salle 24-25/405
Parameterized complexity suggests a multi-parameter analysis of the computational complexity of hard problems. The idea is to understand the influence of parameters, distinct from the input size, in the resolution of a problem. Such parameters could be the solution size or the structural parameters such as width parameters. After an introduction to parameterized complexity, we will present some of the algorithmic consequences of the graph minor theory. From the work of Robertson and Seymour, it is known that every graph family closed under minor can be recognized in cubic time. However for most of such graph family, such a result is existential only. Since then constructive meta-algorithmic theorems have been proposed (including Courcelle’s theorem) within the framework of parameterized complexity. We will discuss recent developments in this line of research that led to efficient algorithms for large family of problems.

Sergey Kirgizov, Le2i, Université de Bourgogne
Temporal density of complex networks and ego-community dynamics
Lundi 04 julliet 2016 à 11h, salle 24-25/405
At first, we say that a ego-community structure is a probability measure defined on the set of network nodes. Any subset of nodes may engender its own ego-community structure around. Many community detection algorithms can be modified to yield a result of this type, for instance, the personalized pagerank. We also recall that community detection algorithms (including personalized pagerank) can be viewed from different perspectives: random walks, convergence of markov chain, spectral clustering, optimization, mincut(s), discrete cheeger inequality(ies), etc. Next, we present a continuous version of Viard-Latapy-Magnien link streams, that we call "temporal density". Classical kernel density estimation is used to move from discrete link streams towards their continuous counterparts. Using matrix perturbation theory we can prove that ego-community structure changes smoothly when the network evolves smoothly. This is very important, for example, for visualization purposes. Combining the temporal density and personalized pagerank methods, we are able to visualize and study the evolution of the ego-community structures of complex networks with a large number of temporal links in order to extract interacting information. For example, we can detect events, trace the evolution of (ego-)community structure, etc. We illustrate and validate our approach using "Primary school temporal network data" provided by, and we show how the temporal density can be applied to the study of very large datasets, such as a collection of tweets written by European Parliament candidates during European Parliament election in 2014.

Gilles Tredan, LAAS, Toulouse, France
Graphs: is there something between theory and practice?
Vendredi 24 juin 2016 à 11h, salle 24-25/405
My first part will focus on the problem of charting graphs: can we believe the maps we build for complex systems? My second part will present efforts to capture AFK social interaction networks (the Souk project), and figure out what to do with the obtained dynamic graphs. My third part is yet to be defined. My hole presentation will try to find a balance between algorithmic perspectives and data analysis.

Argyris Kalogeratos, MLMDA, CMLA, ENS Cachan
Suppressing diffusion processes on arbitrary networks using treatment resources of limited efficiency
Lundi 13 juin 2016 à 11h, salle 26-00/332
In many real-life situations, it is critical to dynamically suppress or remove an undesired diffusion process (viruses, information, behaviors, etc.). The talk will present a framework for Dynamic Resource Allocation (DRA) assuming a continuous-time SIS epidemic model, and that a budget of treatment resources of limited efficiency are at the disposal of authorities. Special emphasis will be given on the macro- and microscopic (or local) properties of the network structure for the problem and two strategies will be presented that fall in this framework: a) a simple yet effective greedy approach, and b) a more sophisticated one that uses a precomputed priority plan of how the healing strategy should proceed on a specific network. Additionally, extensions in competitive scenarios will be discussed.

Johan Mazel, National Institute of Informatics, Tokyo, Japan
Detection and classification of network traffic anomalies
Mercredi 8 juin 2016 à 11h, salle 24-25/405
Internet plays a central role in our lives. However, it is an extremely diverse and complex system. Ranging from non-malicious unexpected events such as flash-crowds and failures, to network attacks such as denials-of-service and network scans, network traffic anomalies can have serious detrimental effects on the performance and integrity of the network. Anomaly detection is thus paramount in order to guarantee users' access to Internet resources. In this talk, we will address recent advances in network traffic anomaly detection and classification, that leverage graph analysis techniques, machine learning techniques and big data.

Marthe Bonamy, LaBRI, Université de Bordeaux
Kempe equivalence of colourings
Vendredi 3 juin 2016 à 11h, salle 24-25/405
Given a colouring of a graph, a Kempe change is the operation of picking a maximal bichromatic subgraph and switching the two colours in it. Two colourings are Kempe equivalent if they can be obtained from each other through a series of Kempe changes. Kempe changes were first introduced in a failed attempt to prove the Four Colour Theorem, but they proved to be a powerful tool for other colouring problems. They are also relevant for more applied questions, most notably in theoretical physics. Consider a graph with no vertex of degree more than some integer D. In 2007, Mohar conjectured that all its D-colourings are Kempe-equivalent. Feghali, Johnson and Paulusma proved in 2015 that this is true for D=3, with the exception of one single graph which disproves the conjecture in its generality. We settle the remaining cases by proving the conjecture holds for every integer D at least 4. This is a joint work with Nicolas Bousquet (LIRIS, Ecole Centrale Lyon, France), Carl Feghali (Durham University, UK) and Matthew Johnson (Durham University, UK).

Jean Creusefond, GREYC, Université de Caen Basse-Normandie
La structure communautaire : évaluation et analyse de motifs dans les flux de liens
Vendredi 13 mai 2016 à 11h, salle 24-25/405
Cet exposé sera en deux parties relativement indépendantes : l'évaluation des structures communautaires par le biais des vérités de terrain et l'analyse des l'appartenance communautaire des motifs dans les flux de liens L'évaluation de structures communautaires de manière théorique est très délicate : de multiples propriétés structurelles sont considérées comme importantes, par conséquent considérer une structure comme meilleure qu'une autre implique des choix arbitraires sur ces préférences, matérialisé par le choix d'une fonction de qualité ou de benchmarks. Afin d'éviter ces problèmes, beaucoup de chercheurs évaluent maintenant leurs résultats par comparaison avec des structures communautaires extraites en même temps que des jeux de données, en argumentant que la proximité entre leurs résultats et la vérité de terrain est une preuve significative de pertinence. Dans cette partie, je vais discuter d'une méthodologie permettant de concilier les deux approches et d'identifier quelles vérités de terrain favorisent quelles fonctions de qualité. Je soulignerai notamment le choix de la fonction de comparaison de partitions, souvent considéré comme anodin, mais changeant en fait radicalement les résultats. Pour référence, le programme développé (incluant un grand nombre d'algorithmes de détection de communautés et de fonctions de qualité) est entièrement disponible à l'adresse suivante : En seconde partie, je discuterai de travaux en cours d'analyse de flots de liens : des graphe dont chaque arc est étiqueté par un temps et où les multiarcs sont possibles. Les flots de liens qui nous intéressent ici représentent des réseaux de communication, c'est-à-dire que chaque arc représente une interaction orientée entre deux utilisateurs. Fréquemment, les algorithmes de détection de communautés qui tentent de les analyser agglomèrent le réseau de communication sur des fenêtres temporelles, où des méthodes traditionnelles (ou adaptées) peuvent êtres appliquées. Dans ce cas, une information est perdue : la causalité entre les liens. Par exemple, si un ensemble de personnes ont systématiquement la même structure de communication (ex : quand "A" interagit avec "B", celui-ci intéragit ensuite systématiquement avec "C" et "D"), peut-on en déduire la structure communautaire associée? Afin d'évaluer l'impact de cette information, je me suis intéressé aux motifs : des chaînes de communication dont la causalité semble probable (la première interaction a probablement entraîné la suivante, etc.). Le lien entre ces motifs et la structure communautaire reste donc à analyser, et je présenterai les outils mis au point à ce dessein ainsi que quelques résultats préliminaires.

Fragkiskos Malliaros, Laboratoire d'Informatique (LIX), École Polytechnique
Degeneracy-based mining of social and information networks: dynamics and applications
Vendredi 01 avril 2016 à 11h, salle 24-25/405
Networks have become ubiquitous as data from diverse disciplines can naturally be mapped to graph structures. The problem of extracting meaningful information from large scale graph data in an efficient and effective way has become crucial and challenging with several important applications and towards this end, graph mining and analysis methods constitute prominent tools. In this talk, I will present part of my work that builts upon computationally efficient graph mining methods in order to: (i) design models for analyzing the structure and dynamics of real-world networks towards unraveling properties that can further be used in practical applications; (ii) develop algorithmic tools for large-scale analytics on data with inherent (e.g., social networks) or without inherent (e.g., text) graph structure. Our approaches rely on the concepts of graph degeneracy and core decomposition in graphs. In particular, for the former point I will show how to model the engagement dynamics of large social networks and how to assess their vulnerability with respect to user departures from the network. In both cases, by unraveling the dynamics of real social networks, regularities and patterns about their structure and formation can be identified; such knowledge can further be used in various applications including churn prediction and anomaly detection. For the latter, I will present a core decomposition-based approach for locating influential nodes in complex networks, with direct applications to epidemic control and viral marketing.

Samuel Martin, Université de Lorraine, ENSEM, CRAN, COPHY - CID
Modelling influence and opinion evolution in online collective behaviour
Vendredi 18 mars 2016 à 11h, salle 26-00/332
Opinion evolution and judgment revision are mediated through social influence. In this talk, I will present a study based on a crowdsourced in vitro experiment. The study shows how a consensus model can be used to predict opinion evolution in online collective behaviour. The model is parametrized by the influenceability of each individuals, a factor representing to what extent individuals incorporate external judgments. Judgment revision includes unpredictable variations which limit the potential for prediction. The study also serves to measure this level of unpredictability via a specific control experiment. More than two thirds of the prediction errors are found to occur due to unpredictability of the human judgment revision process rather than to model imperfection.

Thomas Louail, Institute for Cross-Disciplinary Physics and Complex Systems (IFISC), Palma De Mallorca, Spain
Uncovering the spatial structure of mobility networks in cities – Methods and applications
Vendredi 19 février 2016 à 11h, salle 24-25/405
The increasing availability of individual geographic footprints has generated a broad scientific interest for human mobility networks, at various scales and in different geographical contexts. In this talk I will present some recent results related to urban mobility. I will first present a method we developed to extract an expressive and coarse-grained signature from a large, weighted and directed network. I will then discuss the results we obtained when we applied this method to mobility networks extracted from mobile phone data in 31 Spanish cities, in order to compare the structure of journey-to-work commuting in these cities. The method distinguishes different types of links/flows, and clearly highlights a clear relation between city size and the importance of these types of . In the second part of my talk, I will focus on the shopping trips networks extracted from credit card transactions, performed by hundreds of thousands of anonymized individuals in the two largest Spanish cities. Starting from the bipartite networks that link individuals and businesses of the city, I will show that it is possible to evenly distribute business income among neighbourhoods -- and then mitigate spatial inequality -- by reassigning only a very small fraction of each individual's shopping trips. This spatial and bottom-up approach of wealth redistribution could be easily implemented in mobile apps, that would assist individuals in slightly reshaping their mobility routines. Our results hence illustrate the social benefits individuals are entitled to expect from the analysis of the data they daily produce.

Patricia Conde Céspedes, Université Paris 13, L2TI
A method for the Approximation of the Maximal α−Consensus Local Community detection problem in Complex Networks
Vendredi 22 janvier 2016 à 11h, salle 26-00/332
Although the notion of community does not have a unanimous accepted definition, it is often related to a set of strongly interconnected nodes. Indeed, the density of links plays an important role because it measures the strength of the relationships in the community. The need of these well connected and dense communities has led to the notion of α−consensus community. An α−consensus community, is a group of nodes where each member is connected to more than a proportion α of the other nodes. An α−consensus community is maximal if and only if adding a new node to the set breaks the rule. Consequently, an α−consensus community has a density greater than α. Existing methods for mining α−consensus communities generally assume that the network is entirely known and they try to detect all such consensus communities. Detecting the local community of specific nodes is very important for applications dealing with huge networks, when iterating through all nodes would be impractical. In this paper, we propose an efficient algorithm, called RANK-NUM-NEIGHS (RNN), based on local optimizations to approximate the maximal α−consensus local community of a given node. The proposed method is evaluated experimentally on real and artificial complex networks in terms of quality, execution time and stability. We also provide an upper bound on the optimal solution. The experiments show that It provides better results than the existing methods.

Fabrizio De Vico Fallani, INRIA, ARAMIS, ICM, Paris
Graph analysis of functional brain networks: theory, applications and issues
Vendredi 4 décembre 2015 à 11h, salle 26-00/332
We have known for at least 100 years that the brain is organized as a network of connections between neuronal ensembles. However, only in the last 10 years there has been a rapid growth in our ability to quantify the complex topology of brain networks, using mathematical tools derived from graph theory. In this talk, I will present recent development of graph theoretical approaches to analyze brain networks and model (re)organizational principles of the neural function underlying behavior and outcome, in healthy and diseased conditions. The final part will be devoted to highlight some of the current issues related to complex brain network analysis.

Oana Bălălău, Télécom ParisTech, Paris, France
Densest subgraph computation and applications in finding events on social media
Vendredi 27 novembre 2015 à 11h, salle 24-25/405
Finding dense subgraphs in large graphs is a key primitive in a variety of real-world application domains, encompassing social network analytics, event detection, biology, and finance. In most such applications, one typically aims at finding several (possibly overlapping) dense subgraphs which might correspond to communities in social networks or interesting events. In this talk we present a natural generalization of the densest subgraph problem, where the main goal is to find at most k subgraphs with maximum total aggregate density, while satisfying an upper bound on the pairwise Jaccard coefficient between the sets of nodes of the subgraphs. We will also illustrate how finding dense subgraphs can be an important subroutine for event detection in social media. Social media has great potential, as apart from the traditional media sources, many users post updates on different events. The highly dynamic nature of social networks gives the benefit of timely updates and the huge amount of content the benefit of diversity and large coverage. However, finding events presents also non-trivial challenges given the large amount of noisy and irrelevant data present in social media.

Ryota Kobayashi, Principles of Informatics Research Division, National Institute of Informatics, Tokyo, Japan
Inferring synaptic connections from spike data of multiple neurons
Vendredi 6 novembre 2015 à 11h, salle 26-00/332
Correlations in neuronal activity are defined as "functional connections" between pairs of neurons. It is still unclear how the functional connectivity is related to underlying (physiological) synaptic connectivity. Here, we develop a coupled escape rate model (CERM) to infer synaptic connections from spike data of multiple neurons. Estimation performance of the proposed method was compared to that of the previous methods by using a simulated data generated by a realistic cortical network model, which consists of thousands of detailed model neurons (Kitano & Fukai, 2007). We conclude that CERM method is a promising method to infer synaptic connections from multiple neural spike data. This is joint work with Katsunori Kitano.

Yann Busnel, Computer Sciences Department, Ensai
Dependable Issues Resolved with Distributed Streams
Mardi 6 octobre 2015 à 11h, salle 24-25/405
The analysis of massive data streams is fundamental in many monitoring applications (e.g, Internet routers). For networks operators, it is a recurrent and crucial issue to determine whether huge data streams, received at their monitored devices, are correlated or not as it may reveal the presence of attacks. First, we propose a metric, called codeviation, that allows to evaluate the correlation between distributed streams. This metric is inspired from classical metric in statistics and probability theory, and as such enables to understand how observed quantities change together, and in which proportion. We then propose to estimate the codeviation in the data stream model. In this model, functions are estimated on a huge sequence of data items, in an online fashion, and with a very small amount of memory with respect to both the size of the input stream and the values domain from which data items are drawn. We give upper and lower bounds on the quality of the codeviation, and provide both local and distributed algorithms that additively approximates the codeviation among data streams using sub-linear space. On the other hand, we consider the problem of identifying global iceberg attacks in massive and physically distributed streams. A global iceberg is a distributed denial of service attack, where some elements globally recur many times across the distributed streams, but locally, they do not appear as a deny of service. A natural solution to defend against global iceberg attacks is to rely on multiple routers that locally scan their network traffic, and regularly provide monitoring information to a server in charge of collecting and aggregating all the monitored information. Any relevant solution to this problem must minimise the communication between the routers and the coordinator, and the space required by each node to analyse its stream. We propose a distributed algorithm that tracks global icebergs on the fly with guaranteed error bounds, limited memory and processing requirements. We present a thorough analysis of our algorithm performance. In particular we derive an optimal upper bound on the number of bits communicated between the multiple routers and the coordinator in presence of an oblivious adversary. Finally, we present the main results of the experiments we have run on a cluster of single-board computers. Those experiments confirm the efficiency and accuracy of our algorithm to track global icebergs hidden in very large input data streams exhibiting different shapes.

Ghislain Romaric Meleu, Faculté des Sciences, Université de Yaoundé 1
Modèles de génération des graphes de collaboration multi-niveaux
Vendredi 2 octobre 2015 à 11h, salle 24-25/405
Les entêtes des articles scientifiques permettent de construire trois réseaux de collaborations : les réseaux des auteurs, des laboratoires et des institutions. Les réseaux sont corrélés du fait des relations d'affiliations qui existent entre les acteurs des trois réseaux. Nous appelons réseaux hiérarchiques (ou multi-niveaux) de tels réseaux; les réseaux de niveaux supérieurs étant déduits du réseau de co-publication des auteurs. Nous étudions une généralisation de ces réseaux hiérarchiques où un acteur est affilié à une organisation qui peut elle aussi être affiliée à une organisation de niveau supérieur et ainsi de suite. Les relations entre entités à un même niveau sont déduites de celles existantes entre entités de niveau inférieur. Être capable de générer artificiellement de tels réseaux suppose que l'on comprenne à la fois comment les acteurs (au niveau le plus bas) interagissent, mais aussi la dynamique des affiliations aux organisations. Nous proposons une première analyse de tels réseaux. Nous commençons par construire un modèle de génération de graphes de collaboration (de niveau 0) basé sur l'arrivée de petites cliques. Nous observons expérimentalement que ces réseaux ainsi que les réseaux de niveaux supérieurs déduits à partir d'un modèle d'affiliation par attachement préférentiel sont des réseaux « small-world » et « scale-free ». Les démonstrations sont faites pour le niveau 0.

Christian Glacet, National Research Council of Italy - Institute of Electronics, Computer and Telecommunication Engineering (CNR - IEIIT), Torino, Italy
Compact routing, main results and techniques
Vendredi 25 septembre 2015 à 11h, salle 24-25/405
Message routing is a central activity in any interconnection network. Route efficiency and memory requirements are two major central parameters in the design of a routing scheme. Routing along short paths is clearly desirable, and the storage of the routing information at each node must also be limited to allow quick routing decision, fast update, and scalability. There is a trade-off between the route efficiency (measured in terms of stretch) and the memory requirements (measured by the size of the routing tables). For a n nodes network, the classical shortest path routing scheme achieve stretch 1 with n entries per node (router). Compact routing techniques offer different tradeoffs by allowing routing detours. It is known that in order to guaranty that every route has a stretch strictly lower than 2k+1 the routing tables must have size of order n^1/k at least. Is it actually possible to design routing schemes that attain these lower bounds? This is the question I will answer during my talk, explaining in the mean time the main algorithmic ideas used to achieve the currently best known trade-offs. Finally I'll also introduce the more specific problem of compact routing in "internet-like" graphs.

Arunabha Sen, School of Computing, Informatics and Decision Systems Engineering, Arizona State University
Strategic Analysis and Design of Robust and Resilient Interdependent Power and Communication Networks with a New Model of Interdependency
Vendredi 11 septembre 2015 à 11h, salle 26-00/332
The critical infrastructures of the nation such as the power grid and the communication network are highly interdependent. Recognizing the need for a deeper understanding of the interdependency in a multi-layered network, significant efforts have been made in the research community in the last few years to achieve this goal. Accordingly a number of models have been proposed and analyzed. Unfortunately, most of the models are over simplified and as such they fail to capture the complex interdependency that exists between entities of power grid and communication networks involving a combination of conjunctive and disjunctive relations. To overcome the limitations of existing models, we have recently proposed a new model that is able to capture such complex interdependency relations. Utilizing this model, we have studied a number of problems, including (i) identification the k most vulnerable nodes of an interdependent network, (ii) entity hardening problem, (iii) progressive recovery problem, (iv) targeted attack problem and several others. In this talk, we first present the new model and then discuss several problems that has been studied utilizing this model.

Pierre Aboulker, Universidad Andres Bello, Santiago, Chile
Classes of digraphs defined by forbidding induced subdigraphs and their chromatic-number
Jeudi 09 juillet 2015 à 11h, salle 26-00/332
A class of graphs is $chi$-bounded if there exists a function f such that for any graph G in the class, $chi(G)$ ≤ f (ω(G)). Gyárfas conjectured that for any tree T, the class of graphs that do not contain T as an induced subgraph is $chi$-bounded. We investigate the oriented analogue of this Conjecture. This a joint work with J. Bang-Jensen, N. Bousquet, P. Charbit, F. Havet, F. Maffray, S. Thomassé and J. Zamora

Élie de Panafieu, Research Institute for Symbolic Computation, Johannes Kepler University, Linz, Austria
Inhomogeneous Hypergraphs
Jeudi 02 juillet 2015 à 11h, salle 24-25/405
We introduce the inhomogeneous hypergraph model. Each edge can contain an arbitrary number of vertices, the vertices are colored, and each edge receives a weight which depends on the colors of the vertices it contains. This model provides a uniform setting to solve problems arising from various domains of computer science and mathematics. We will focus on applications to the enumeration of satisfied and satisfiable instances of Constraint Satisfaction Problems (CSP), and compute the limit probability for a random graph to be bipartit, the limit probability of satisfiability of systems of equations, the enumeration of properly k-colored graphs and investigate some graphs coming from social networks. We will present results on the asymptotics of inhomogeneous hypergraphs and their typical structure. Our main tool is analytic combinatorics.

Kévin Huguenin, Dependable Computing and Fault Tolerance - TSF, LAAS-CNRS
(Some) Social aspects of location privacy
Jeudi 18 juin 2015 à 11h, salle 24-25/405
Smartphones hold and collect ever-increasing amounts of personal and contextual data about their owners. This information is often shared on social networks or sent to on-line service providers, in order to benefit from social and context-aware features. This, however, raises serious privacy issues. My talk will revolve around the human and social aspect of privacy: I will discuss the privacy implications of the relationship between location, co-location (e.g., name tagging in posts and photos on mobile social networks) and social ties and the implications of the use of generalization-based privacy protection techniques on the utility of location-based services.

Bivas Mitra, Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur, India
Emergence of Superpeer Networks: A New Perspective
Jeudi 11 juin 2015 à 11h, salle 24-25/405
In superpeer based p2p networks, the superpeer nodes are discovered through the process of bootstrapping, whereby resourceful peers get upgraded to superpeers. However, bootstrapping is influenced by several factors like limitation on the maximum number of connections a peer can have due to bandwidth constraints, limitation on the availability of information of existing peers due to cache size constraints and also by the attachment policy of the newly arriving peers to the resourceful peers. In this talk we propose an analytical framework which explains the emergence of superpeer networks on execution of the commercial peer-to-peer bootstrapping protocols by incoming nodes. Bootstrapping protocols exploit physical properties of the online peers like resource content, processing power, storage space, connectivity etc as well as take the finiteness of bandwidth of each online peer into consideration. With the help of rate equations, we show that execution of these protocols results in the emergence of superpeer nodes in the network - the exact degree distribution is evaluated. We also show that the cache parameters must also be suitably tuned so as to increase the fraction of superpeers in the network. We validate the developed framework through extensive simulation. The analysis of the results shows that the amount of superpeers produced in the network depends on the protocol as well as the properties of the joining nodes. As an application study, we show that our framework can explain the topological configuration of commercial Gnutella networks.

Robin Lamarche-Perrin, Max-Planck-Institute for Mathematics in the Sciences, Leipzig, Germany
Analyse multi-échelles des systèmes complexes: théorie de l’information et optimisation combinatoire
Vendredi 15 mai 2015 à 11h, salle 24-25/405
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).

Pádraig Cunningham, School Of Computer Science & Informatics, University College Dublin, Ireland
Graph Similarity Using Network Motif Profiles
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.

Laurent Vuillon, LAMA, Université de Savoie
Tilings and networks applied to protein structures: bio-mathematical aspects of fold plasticity
Jeudi 19 mars 2015 à 11h, salle 24-25/405
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.

Alexandru Stan, Business Information Systems Department, Babes-Bolyai University, Romania
Flash crashes, VPIN metric and market topology considerations
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, MIA, INRA/AgroParisTech
Analyse de réseaux au moyen du modèle à blocs stochastiques
Lundi 02 mars 2015 à 14h, salle 24-25/405
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.

Louisa Harutyunyan, LIP6, Université Pierre et Marie Curie
Hexagonal based Beacon-less Flooding in MANETs
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, Universidad Complutense, Madrid
Problèmes sociologiques et méthodes mathématiques: la recherche du réseau squelette
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 qu’il s’agit, 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 l’interaction binaire n’est pas encore une relation sociale, qu’il faut au moins trois individus pour constituer l’atome du social. D’autre part les groupes sociaux sont bien moins nombreux que les individus, et cependant, leurs intersections permettent d’individualiser univoquement tous les membres d’une 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 n’exclut pas identifier leurs membres, s’il le fallait pour quelque raison que ce soit. En plus, les réseaux bipartites constituent un modèle de n’importe quel réseau. Et ils permettent plus aisément l’identification del classes d’équivalence structurelle des points du réseau. Les concepts de place et de réseaux de places que j’ai proposé constituent une approximation intéressante pour aborder ce problème. Le problème de l’identification des cliques, informatiquement compliqué, peut être contourné en partant des données sur des groupes sociaux.

Márton Karsai, INRIA, LIP, ENS de Lyon
Complex contagion process in spreading of online innovation
Jeudi 15 janvier 2015 à 11h, salle 26-00/332
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, LIAFA, Université Paris Diderot et Linkfluence
Dynamiques des réseaux sociaux en ligne, recommandations et interaction
Jeudi 04 décembre 2014 à 11h, salle 26-00/332
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.

Artur Ziviani, National Laboratory for Scientific Computing (Petrópolis, Brazil)
Modeling time-varying multilayer networks (and beyond?)
Jeudi 09 octobre 2014 à 11h, salle 25-26/101
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.

Lautaro Dolberg, Interdisciplinary Centre for Security, Reliability and Trust (SnT), Université du Luxembourg
DNS Monitoring, looking out for anomalies using the time frame Name – IP association
Jeudi 09 octobre 2014 à 10h, salle 25-26/101
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. I’m 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.

Soumajit Pramanik, Department of Computer Science and Engineering, IIT Kharagpur
Controlling Information Flow in Social Networks
Vendredi 03 octobre 2014 à 11h, salle 26-00/101 (Noguez)
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, LIP6, Université Pierre et Marie Curie
Complexité de l’exploration des graphes dynamiques T-intervalle-connexes
Jeudi 02 octobre 2014 à 11h, salle 25-26/101
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, Université catholique de Louvain
Community detection and Role extraction in networks
Jeudi 18 septembre à 11h, salle 25-26/101

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.


Author Thesis:


Baptiste Mélès, Laboratoire PHIER, Université Blaise Pascal (Clermont-Ferrand)
L’invention des concepts en informatique

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.


Huan Liu, Arizona State University
Deepening Our Understanding of Social Media via Data Mining

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


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


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.


Sebastiano Vigna, Dipartimento di Informatica, Università degli Studi di Milano
In-Core Computation of Geometric Centralities with HyperBall: A Hundred Billion Nodes and Beyond

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


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.

Catherine Matias, Laboratoire Stat & Génome, CNRS, Université d'Évry-Val d'Essonne
Coala : Co-evolution Assessment by a Likelihood-free Approach

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.



Anh-Dung Nguyen, ISAE, Université de Toulouse
Les réseaux dynamiques : des données aux modèles

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


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.

Christophe Crespelle, LIP, Université Claude Bernard (Lyon 1)
Dynamic Contact Network of an Hospital

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


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.

Arnaud Casteigts, LaBRI, Université de Bordeaux
Impact de la dynamique du réseau sur quelques problèmes d’algorithmique distribuée et classification de graphes dynamiques

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


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.

Bertrand Ducourthial, Laboratoire Heudiasyc, Université de Technologie de Compiègne
Applications collaboratives dans les réseaux dynamiques : applications aux réseaux de véhicules

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


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.

Lionel Tabourier, naXys, Université de Namur
RankMerging : une méthode d’apprentissage supervisé pour prédire les liens dans un réseau social
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.

Cédric Sueur, IPHC, Université de Strasbourg
Social Networks as a Trade-Off Between Efficient Information Transmission and Reduced Disease Transmission
Jeudi 27 mars 2014 à 11h, salle 25-26/101

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.

Daniel Bernardes, soutenance de thèse
Information Diffusion in Complex Networks: Measurement-Based Analysis Applied to Modelling
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.

Ségolène Charaudeau, UMRS 707, INSERM ; Institut Jacques Monod, Université Paris Diderot
Influence de la structure du réseau des mouvements de commuting sur la diffusion de la grippe
Jeudi 20 mars 2014 à 11h, salle 25-26/101

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.

Sharad Goel, Microsoft Research (New York)
“Going Viral” and the Structure of Online Diffusion
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.

Antoine Mazières, INRA-SenS ; LIAFA, Université Paris Diderot
Deep Tags: Toward a Quantitative Analysis of Online Pornography
Jeudi 13 mars 2014 à 11h, salle 25-26/101

Lors de ce séminaire, je vous présenterai le projet, 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 pornographie est é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 :

Pre-print du papier :

Datasets :

Porngram :

Pierre-André Maugis, University College London
Motifs Distribution in Exchangeable Random Networks
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, École Polytechnique, plateforme BioEmergences, ISC-PIF
Reconstruction des dynamiques multi-échelles de la morphogenèse animale
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 d’un organisme multi-cellulaire est le résultat de phénomènes biomécaniques multi-échelles complexes. L’échelle cellulaire est un niveau d’inté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 d’imagerie obtenues par acquisition en microscopie multi-photons jusqu’à la modélisation des comportements cellulaires par l’approche des systèmes complexes, nos travaux se situent dans un cadre intrinsèque d’interdisciplinarité. 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. J’aborderai 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 l’embryogenèse, fondé sur l’ensemble des caractéristiques mesurées.

Elisa Omodei, Institut des Systèmes Complexes ; LaTTiCe-CNRS
Analyse et modélisation des dynamiques socio-épistémiques des communautés scientifiques
Jeudi 06 février 2014 à 14h30, salle 26-00/101

Comment les structures sociales et épistémiques d’une 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 l’un avec l’autre.

Romain Boulet, Université Lyon 3
Modélisation et analyse à base de graphes de citations de textes de loi : histoire d’une collaboration entre mathématiciens et juristes
Jeudi 23 Janvier 2014 à 11h30, salle 25-26/105

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), (1) LASMIC, Université de Nice-Sophia Antipolis & (2) CNRS, Laboratoire CAMS, EHESS
Le contrôle de la forme des réseaux par leurs membres : le fils de discussion comme réseau d’interaction
Jeudi 09 janvier 2014 à 11h, salle 25-26/101

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 qu’un fil de discussion peut se décrire comme un réseau de répliques dont l’extension (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 :

Qinna Wang, LIP6, Université Pierre et Marie Curie
Détection de communautés recouvrantes dans des réseaux de terrain dynamiques
Jeudi 12 Décembre 2013 à 14h, salle 25-26/101

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 l’ensemble des nœuds. Cela exclut  par définition qu’un 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.  Cette thèse porte 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 optimisation  de 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, CNRS, FRAMESPA/IMT - Toulouse
Une plus grande utilisation de la théorie des graphes dans l’analyse des réseaux
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é, LIFO, Université d'Orléans
Les capitalistes sociaux sur Twitter : détection, évolution, caractérisation
Jeudi 07 novembre 2013 à 11h, salle 25-26/101

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.

Analyse des réseaux et géographie politique : l’ONU comme terrain de jeu
Jeudi 24 octobre 2013 à 11h, salle 26-00/428

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.


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, Laboratoire MAP5 (Université Paris Descartes)
The Random Subgraph Model for the analysis of an ecclesiastical network in Merovingian Gaul
Jeudi 03 octobre 2013 à 11h, salle 25-26/101

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

Benjamin Renoust, Inria, LaBRI (Université Bordeaux I) ; Institut National de l'Audiovisuel
Assessing Group Cohesion in Homophily Networks
Mardi 17 septembre 2013 à 11h, salle 25-26/101

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, LaBRI (Université Bordeaux I)
Évaluation et optimisation d’une partition hiérarchique de graphe
Mardi 09 juillet 2013 à 14h, salle 25-26/101

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 s’interprè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, Nodus Labs (Berlin)
Using the Framework of Networks to Enhance Learning and Social Interactions
Jeudi 27 juin 2013 à 11h, salle 55-65/211

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 one’s capabilities for social interactions. Specifically, we’re 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 - - 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 text’s 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 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 one’s 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, Interdisciplinary Centre for Security, Reliability and Trust (Université du Luxembourg)
Scalable Analysis for Network Monitoring and Forensics Purposes
Jeudi 06 juin 2013 à 11h30, salle 55-65/211

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, German Research Center for Artificial Intelligence (DFKI)
Social Network Analysis of Authority in the Blogosphere and its Application
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, e-lab, Bouygues
Partition en sous-graphes denses pour la détection de communautés
Jeudi 23 mai 2013 à 11h, salle 25-26/101

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.

Joyce El Haddad, LAMSADE, Université Paris-Dauphine
Trust-Based Service Discovery in Multi-Relation Social Networks
Jeudi 25 avril 2013 à 11h, salle 25-26/101

With the increasing number of services, the need to locate relevant services remains essential. To satisfy the query of a service requester, available service providers has first to be discovered. This task has been heavily investigated from both industrial and academic perspectives based essentially on registers. However, they completely ignore the contribution of the social dimension. When integrating social trust dimension to service discovery, this task will gain wider credibility and acceptance. If a service requester knows that discovered services are offered by trustworthy providers, he will be more confident.

In this talk, we present a new discovery technique based on a social trust measure that ranks service providers belonging to the service requester’s multi-relation social network. The proposed measure is an aggregation of three measures: the social position, the social proximity and the social similarity. To compute these measures, we take into account both semantic and structural knowledge extracted from the multi-relation social network. Semantic information includes service requestor and provider profiles and their interactions. Structural information includes among other the position of service providers in the multi-relation social network graph.

This is joint work with A. Louati and S. Pinson.

Nicolas Tremblay, ENS Lyon
Wavelets on Graphs: a Tool for Multiscale Community Mining in Graphs
Jeudi 11 avril 2013 à 11h, salle 25-26/101

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.

Nicolas Broutin, Inria Paris-Rocquencourt
Connectivity of Bluetooth Graphs
Jeudi 28 mars 2013 à 11h, salle 25-26/101

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.

Sylvain Sené, Laboratoire IBISC, Université d'Évry-Val d'Essonne
Propriétés combinatoires et de robustesse de modèles discrets de réseaux biologiques
Mercredi 13 mars 2013 à 14h, salle 25-26/105

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, INRIA, LIP, ENS Lyon
Lois d’échelle des processus de trafic dans les réseaux de communications
Jeudi 07 mars 2013 à 14h30, salle 25-26/101

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.

Eric Freyssinet, Guillaume Bonfante et Jean-Yves Marion,
Lutte contre les botnets
mardi 12 février 2013 à 10h30, salle 25-26/101

A l'occasion de ce séminaire, deux présentations complémentaires sur la lutte contre les botnets sont prévues:

  • Avancée de la réflexion sur la classification (Eric Freyssinet, Pôle judiciaire de la Gendarmerie Nationale, Chef de la division de lutte contre la cybercriminalité & LIP6):
La classification des botnets ne fait pas encore l'objet d'une standardisation, contrairement aux logiciels malveillants eux-mêmes ou encore les incidents de sécurité informatique. Après une année de suivi de l'activité et des informations publiées sur un grand nombre de botnets et leur inclusion dans un Wiki sémantique, notre réflexion permet d'envisager de faire des propositions pour contribuer aux standards de classification actuels. La présentation portera sur les premières pistes de propositions, ainsi que sur quelques idées quant aux approches nécessaires pour assurer un suivi proactif du déploiement de botnets.
  • On detection methods and analysis of malware (Guillaume Bonfante and Jean-Yves Marion, University of Lorraine, LORIA, Nancy, France):

This talk will present different research directions in malware analysis and detection. First, we will make a brief overview of the detection techniques and of the malware defenses. Then, we will essentially focus on (i) the analyze of cryptographic implementations, which are important for malware analysis where they are an integral part both of the malware payload and the unpacking code that decrypts this payload (presented at CCS this year) on (ii) behavior detection by means of model-checking (presented at Esoric this year) and  (iii)  on similarity detection by morphological analysis on which the current implementation of our home-made anti-virus is based.

Mathieu Jacomy, Medialab, Sciences Po
e-Diasporas Atlas
jeudi 10 janvier 2013 à 11h, salle 25-26/101

Le e-Diasporas Atlas est une expérimentation unique par ses résultats scientifiques, sa méthode et son mode de publication.

Historiquement, les e-diasporas ont émergé avec la diffusion de l’internet et le développement de multiples services publiques en ligne. A la fin des années 90, de nombreuses institutions se sont emparé des “e-technologies” (e-administration, e-education...), entraînant dans leur sillage des associations de populations migrantes. Si les premiers sites ont été produits par des professionnels des technologies de l’information, toutes les communautés disporiques, et à tous les niveaux, ont rapidement occupé le terrain du web. Les dix dernières années témoignent de l’usage du web 1.0 comme du web 2.0, ainsi que de l’adoption massive de différentes plateformes de réseaux sociaux (Facebook, LinkedIn...). Ces nouveaux moyens de communication et outils d’organisation ont produit un vaste “e-corpus” dont l’exploration, l’analyse et l’archivage n’avaient pas été tentés auparavant.

Fruit des efforts de plus de 80 chercheurs à travers le monde, le e-Diasporas Atlas est le premier de son espèce, avec près de 8000 sites migrants archivés et observés dans leurs interactions.

Dana Diminescu, directrice scientifique du programme TIC-Migrations, et Mathieu Jacomy, responsable R&D, présenteront l’atlas et les étapes qui ont permis de le construire. Différentes questions mathématiques ou d’ingénierie ont trouvé une réponse originale, nécessitant souvent des développements spécifiques. C’est par exemple au sein du programme TIC-Migrations que le logiciel Gephi a été créé et incubé.

Nous vous proposons de participer à une discussion sur les méthodes numériques et l’opérationnalisation du web-mining et de la théorie des graphes dans les humanités numériques.

Raphaël Fournier-S'niehotta, soutenance de thèse
Détection et analyse d’une thématique rare dans de grands ensembles de requêtes : l’activité pédophile dans le P2P
vendredi 21 décembre 2012 à 12h, salle 25-26/105

L'objectif de cette thèse est d'utiliser de grands ensembles de requêtes collectés sur des systèmes P2P pour étudier l'activité pédophile au sein de ces réseaux. En effet, malgré l'importance de ce problème pour la société, il existe peu de connaissances fiables en la matière.

Nous procédons dans un premier temps à la mise au point d'un outil capable de détecter les requêtes qui ciblent des contenus à caractère pédopornographique, en assez faible quantité dans l'ensemble des requêtes. Après avoir identifié quatre catégories de requêtes pédophiles, nous établissons les listes de mots-clefs et tests lexicaux requis pour les distinguer. Nous faisons ensuite classer des requêtes à un ensemble d'experts, afin d'évaluer les performances de notre outil. Celui-ci disposant d'une précision élevée et d'un bon rappel, nous l'utilisons pour estimer de façon fiable la fraction de requêtes pédophiles, proche de 0,25%.

Nous abordons ensuite la quantification des utilisateurs entrant ces requêtes. Dans un tel contexte, où l'on ne dispose que de l'adresse IP et éventuellement d'un port de communication, identifier des utilisateurs est difficile. Nous proposons plusieurs méthodes pour ne pas mélanger les requêtes d'utilisateurs différents. La fraction d'utilisateurs pédophiles est proche de 0,22%.

Nous analysons ensuite la dynamique temporelle de l'activité pédophile. La fraction de requêtes pédophiles a significativement augmenté entre 2009 et 2012. Nous examinons également l'intégration sociale des utilisateurs pédophiles et constatons qu'ils privilégient la fin de la nuit pour effectuer ce type de requêtes, ce en quoi ils diffèrent des autres utilisateurs, notamment ceux soumettant des requêtes pornographiques.

Enfin, nous confrontons les résultats obtenus sur le réseau eDonkey avec ceux du réseau KAD, après avoir défini une méthodologie permettant d'obtenir des données comparables. Nous supposons initialement que le niveau d'anonymat offert par KAD, complètement décentralisé, permet aux utilisateurs de participer à davantage d'échanges pédopornographiques. Nous constatons au contraire que l'activité pédophile est plus importante sur eDonkey et estimons que la fraction de requêtes pédophiles sur KAD est proche de 0.1%.

Emilie Coupechoux, soutenance de thèse
Analyse de grands graphes aléatoires
lundi 10 décembre 2012 à 10h30, salle du Conseil (4ème étage), antenne parisienne de l'INRIA, 23 avenue d'Italie, 75013 Paris

Plusieurs types de réseaux du monde réel peuvent être représentés par des graphes dont les sommets représentent des individus (dans le cas des réseaux sociaux) ou des pages Web (dans le cas du World Wide Web), pour ne citer que ces exemples. Chaque arête du graphe correspond à une interaction entre sommets: dans les réseaux sociaux, une arête est présente entre deux sommets si les individus qu’ils représentent sont amis; dans le World Wide Web, les arêtes représentent les liens hypertextes entre les pages Web. Comme il s’agit de réseaux de très grande taille, leur topologie détaillée est généralement inconnue, et nous les modélisons par de grands graphes aléatoires ayant les mêmes propriétés statistiques locales que celles des réseaux observés. Un exemple de telle propriété est la présence de regroupements dans les réseaux réels: si deux individus ont un ami en commun, ils ont également tendance à être amis entre eux. Étudier des modèles de graphes aléatoires qui soient à la fois appropriés et faciles à aborder d’un point de vue mathématique représente un challenge, c’est pourquoi nous considérons plusieurs modèles de graphes aléatoires possédant ces propriétés.

La propagation d’épidémies dans les graphes aléatoires peut être utilisée pour modéliser plusieurs types de phénomènes présents dans les réseaux réels, comme la propagation de maladies, ou la diffusion d’une nouvelle technologie. Le modèle épidémique que nous considérons dépend du phénomène que nous voulons représenter :

• un individu peut contracter une maladie par un simple contact avec un de ses amis (ces contacts étant indépendants),

• mais une nouvelle technologie est susceptible d’être adoptée par un individu lorsque beaucoup de ses amis ont déjà la technologie en question.

Nous étudions essentiellement ces deux différents cas de figure. Dans chaque cas, nous cherchons à savoir si une faible proportion de la population initialement atteinte (ou ayant la technologie en question) peut propager l’épidémie à une grande partie de la population: si c’est le cas, on dit qu’une ’cascade’ est possible. La transition de phase de ce phénomène est étroitement liée à l’apparition d’une composante géante dans un graphe aléatoire (il y a une ’composante géante’ dans un graphe aléatoire si la taille de sa plus grande composante connexe augmente de façon linéaire avec la taille totale du graphe).

L’étude des graphes aléatoires permet notamment la prédiction de propriétés globales (savoir dans quel cas une cascade est possible ou non) pour des grands réseaux sur lesquels nous ne disposons que de données locales.

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

Jean-Loup Guillaume, soutenance d'HDR
Déterminisme et non-déterminisme au service de la détection de communautés dynamiques
lundi 19 novembre 2012 à 14h, salle 25-26/105

De nombreux systèmes, tels que des réseaux sociaux ou des réseaux informatiques, peuvent être modélisés par des graphes, que l’on appelle alors graphes de terrain. Un certain nombre de travaux ont montré que ces graphes, bien que différents par bien des aspects, sont aussi semblables par beaucoup d’autres et notamment ils possèdent tous une structure communautaire assez forte, c’est-à-dire qu’ils sont formés de sous-ensembles de sommets densément connectés. Si l’on se restreint à une partition en communautés, on dispose de méthodes efficaces pour calculer cette structure, notamment la méthode de Louvain que j’ai contribué à créer et qui est la plus efficace dans le domaine. Or, la plupart de ces réseaux réels sont dynamiques et évoluent au cours du temps par l’ajout ou la suppression de sommets et de liens. Cette dynamique touche naturellement les communautés et il faut donc proposer de nouvelles méthodes pour les calculer et les analyser.

Nous nous sommes intéressés dans ce mémoire à l’approche naturelle qui consiste à considérer un graphe dynamique comme une succession de graphes statiques, puis à calculer une partition en communautés à chaque instant et, enfin, à essayer de faire le lien entre les communautés à différents instants. Nous avons montré que cette approche n’est pas utilisable directement car une modification mineure de la topologie peut engendrer des modifications très importantes de la structure communautaire, d’où un phénomène d’instabilité. Nous avons alors proposé deux approches pour tenter de résoudre ce problème.

La première approche considère que si le graphe évolue peu, ses communautés devraient rester globalement stables. Nous avons donc tout d’abord tenté de stabiliser un algorithme existant en gardant la mémoire des calculs passés, ce qui a donné des résultats bien meilleurs mais avec toujours une instabilité résiduelle. Puis, nous avons étendu cette solution en calculant des partitions multi-pas de bonne qualité sur plusieurs instants de temps. Nous avons couplé cela avec une méthode de décomposition hiérarchique du temps afin de calculer des plages temporelles sur lesquelles ces partitions multi-pas ont un sens. Cette méthode à été appliquée avec succès à des données réelles.

La seconde approche considère que même s’il y a de nombreuses partitions de qualité, elles ne sont pas complètement différentes. Nous avons donc proposé une méthode pour calculer en pratique ces similitudes, qui permettent de définir des coeurs de communautés. Nous avons montré que les coeurs sont pertinents dans les graphes de terrain et permettent de les distinguer des graphes sans réelle structure communautaire (comme les graphes aléatoires par exemple). Nous avons également entamé des travaux pour montrer que les coeurs peuvent être utilisés dans le cas dynamique et qu’ils sont naturellement stables et que les modifications qu’ils peuvent subir sont cette fois très corrélées aux modifications topologiques.

Franck Delaplace, Laboratoire IBISC, Université d'Évry-Val d'Essonne
Analysis of Modular Organisation of Interaction Networks Based on Asymptotic Dynamics
Jeudi 18 octobre 2012 à 10h30, salle 25-26/101

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

Alain Barrat, Centre de Physique Théorique (Marseille) et Institute of Scientific Interchange (Turin)
Réseaux dynamiques : de la mesure à la modélisation
Vendredi 21 septembre 2012 à 14h, salle 25-26/101

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

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

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

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

Emilie Coupechoux, TREC (INRIA-ENS)
Impact of clustering on epidemics in random networks
Lundi 2 avril 2012 à 14h, salle 55-65/211
Motivated by the analysis of social networks, we study a model of network that has both a given degree distribution and a tunable clustering coefficient. We analyze two types of epidemic processes on this random graph model: a diffusion process, which is characterized by an infection probability, each neighbor transmitting the epidemic independently, and a contagion model, which is inspired by a simple coordination game played on the network. Both types of processes have been used to model spread of new ideas, technologies, viruses or worms and results have been obtained for random graphs with no clustering. In this talk, we are interested in the impact of clustering on the growth processes. In both cases, we characterize conditions under which a global cascade is possible, and compute the cascade size explicitly, as a function of the degree distribution and the clustering coefficient. While clustering inhibits the diffusion process (in power-law and regular graphs), its impact for the contagion process is more subtle and depends on the connectivity of the graph: in a low connectivity regime, clustering also inhibits the contagion, while in a high connectivity regime, clustering favors the appearance of global cascades but reduces their size.

Blaise Ngonmang, L2TI - Univ. Paris 13 LIRIMA & UMMISCO - Univ. Yaoundé I
Local community identification in social networks
Jeudi 22 mars 2012 à 11h, salle 25-26/101
In social networks, the detection of communities has gained considerable interest because it can be used for instance for visualization, recommendation in business applications or the analysis of the spread of infectious diseases. Many methods proposed in the litera- ture for the solution of this problem, assume that the structure of the entire network is known, which is not realistic for very large and dynamic networks. For this reason, approaches have been introduced recently to find the local community of a node. Most of these methods often fail when the starting node is at the boundary of a community. In addition, they are not able to detect overlapping communities. In this work, we propose new methods to find local communities that don't have these drawbacks. Experiences on real and computer generated social networks such as Netscience, Amazon 2006 and Lan- cichinetti et al.'s benchmark show that these methods perform better than the solutions with which the comparisons were performed.

Camille Roth, CAMS - EHESS
Dynamics on and of subway networks
Vendredi 2 mars 2012 à 14h,  salle 25/26-101
Subway networks shape, to some extent, the structure of movements of individuals across a city; similarly, they are being partially shaped by the presence of these individuals in the city.  This talk will present two complementary studies describing the dynamic processes which subway networks both host and undergo. The first analysis focuses on dynamics processes occurring on the subway network of a large city (London) in terms of its commuting patterns.  It uses the large scale, real-time electronic ticketing data from the Oyster Card system, introduced less than a decade ago, to reveal a part of the structure and organization of the city.  More precisely, this study shows that patterns of intraurban movement are strongly heterogeneous in terms of volume, but not in terms of distance travelled, and that there is a polycentric structure composed of large flows organized around a limited number of activity centers.  For smaller flows, the pattern of connections becomes richer and more complex and is not strictly hierarchical since it mixes different levels consisting of different orders of magnitude. The second study investigates the temporal evolution of the major subway networks in the world over the last century.  The main result is that most of these networks tend to converge to a shape which shares some generic features, despite their geographical and economical differences. These features include a core with branches radiating from it to cover about twice the average radial extension of the core.  The core generally includes about 60% of the network stations and exhibits an average degree of order 2.5.  Interestingly, core and branches define two distinct and universal regimes in terms of the number of stations at a given distance from the barycenter.  This result which was difficult to interpret in the framework of fractal geometry finds here a natural explanation. More broadly, these two types of studies open the way to more integrated analyses of the coevolution between the dynamics on and of subway networks.

Renaud Lambiotte, Naxys - FUNDP
On Pagerank, teleportation and modelling dynamics in complex networks
Jeudi 16 février 2012 à 11h - salle 55-65/211
In this talk, I will present recent results from 2 recent papers. i) Random teleportation is a necessary evil for ranking and clustering directed networks based on random walks. Teleportation enables ergodic solutions, but the solutions must necessarily depend on the exact implementation and parametrization of the teleportation. For example, in the commonly used PageRank algorithm, the teleportation rate must trade off a heavily biased solution with a uniform solution. Here we show that teleportation to links rather than nodes enables a much smoother trade-off and effectively more robust results. We also show that, by not recording the teleportation steps of the random walker, we can further reduce the effect of teleportation with dramatic effects on clustering. ii) The traditional way of studying temporal networks is to aggregate the dynamics of the edges to create a static weighted network. This implicitly assumes that the edges are governed by Poisson processes, which is not typically the case in empirical temporal networks. Consequently, we examine the effects of non-Poisson inter-event statistics on the dynamics of edges, and we apply the concept of a generalized master equation to the study of continuous-time random walks on networks. We show that the equation reduces to the standard rate equations when the underlying process is Poisson and that the stationary solution is determined by an effective transition matrix whose leading eigenvector is easy to calculate. We discuss the implications of our work for dynamical processes on temporal networks and for the construction of network diagnostics that take into account their nontrivial stochastic nature.

Jean-Charles Delvenne, Université Catholique de Louvain
Dynamics on networks for communities, centralities and consensus
Lundi 6 février 2012 à 11h - salle 25-26/105
Dynamical systems taking place on networks, such as opinion dynamics, synchronization, consensus or random walks, reveal a lot about their structure. In particular we show, through a dynamical reinterpretation of well-known concepts, how centrality measures (such as pagerank, eigencentrality, etc.)  and community detection quality functions (such as modularity, Potts, model, stability, etc.) are intimately related. The dynamical interpretation allows to design new centrality or community detection measures tailored for every particular application.

Arnaud Legout, INRIA Sophia Antipolis
I Know Where You are and What You are Sharing: Exploiting P2P Communications to Invade Users’ Privacy
Mardi 31 janvier 2012 à 11h - salle 25-26/101
In this presentation, we show how to exploit real-time communication applications to determine the IP address of a targeted user.  We focus our study on Skype, although other real-time communication applications may have similar privacy issues.  We first design a scheme that calls an identified-targeted user inconspicuously to find his IP address, which can be done even if he is behind a NAT.  By calling the user periodically, we can then observe the mobility of the user.  We show how to scale the scheme to observe the mobility patterns of tens of thousands of users.  We also consider the linkability threat, in which the identified user is linked to his Internet usage. We illustrate this threat by combining Skype and BitTorrent to show that it is possible to determine the filesharing usage of identified users.  We devise a scheme based on the identification field of the IP datagrams to verify with high accuracy whether the identified user is participating in specific torrents.  We conclude that any Internet user can leverage Skype, and potentially other real-time communication systems, to observe the mobility and filesharing usage of tens of millions of identified users.

Hervé Rivano, INSA Lyon
Modèle d’optimisation pour les réseaux radio maillés
Vendredi 20 janvier 2012 - salle 203-205 (bât 41)
Les réseaux radio maillés sont une solution d'extension des infrastructures cellulaires. Ils permettent de densifier simplement le réseau en collectant le trafic d'utilisateurs vers un point d'accès à l'infrastructure via des communications radio multi-saut. Cette densification permet une diminution des puissances d'émission, donc des consommations énergétiques, et un accroissement de la capacité offerte aux utilisateurs. Durant ce séminaire, nous présenterons des formulation en programmation linéaire et génération de colonnes de l'optimisation du routage et de la configuration de tels réseaux et nous en servons pour étudier le compromis entre consommation énergétique du système et capacité du réseau sur des modèles au réalisme croissant. Nous concluons sur les perspectives d'une étude prenant en compte de manière détaillée l'environnement urbain dans lequel ces réseaux ont vocation à être déployés.

Eric Freyssinet, Gendarmerie Nationale - ComplexNetworks
Gendarmerie, cybercriminalité et lutte contre les botnets
Jeudi 5 janvier 2012 à 11h - salle 25-26 / 101
Présentation générale des activités contre la cybercriminalité de la gendarmerie nationale. Projet de recherche sur le cas spécifique des botnets.

Xiaomin Wang, LIP6 (APR - ComplexNetworks)

Soutenance de thèse

Deciding on the type of the degree distribution of a graph (network) from traceroute-like measurements
Mardi 13 décembre 2011 à 10h - salle 25-26 / 105
The degree distribution of the Internet topology is considered as one of its main properties. However, it is only known through a measurement procedure which gives a biased estimate. This measurement may in first approximation be modeled by a BFS (Breadth-First Search) tree. We explore here our ability to infer the type (Poisson or power-law) of the degree distribution from such a limited knowledge. We design procedures which estimate the degree distribution of a graph from a BFS or multi-BFS trees, and show experimentally (on models and real-world data) that our approaches succeed in making the difference between Poisson and power-law degree distribution and in some cases can also estimate the number of links. In addition, we establish a method, which is a diminishing urn, to analyze the procedure of the queue. We analyze the profile of the BFS tree from a random graph with a given degree distribution. The expected number of nodes and the expected number of invisible links at each level of BFS tree are two main results that we obtain. Using these informations, we propose two new methodologies to decide on the type of the underlying graph.

Abdelhamid Salah Brahim, LIP6 (ComplexNetworks)

Soutenance de thèse

Diffusion d’information et structure en communautés dans un réseau de blogs
Jeudi 8 décembre 2011 à 10h30 - salle 25-26 / 105
On peut modéliser de nombreux objets issus du monde réel par des graphes. Ces objets sont issus de contextes très différents (ex. réseaux informatiques, sociaux ou biologiques), cependant ils se ressemblent au sens de certaines propriétées statistiques. On les désigne sous le terme général de graphes de terrain (complex networks en anglais) ou grands graphes d'interaction. L'analyse des graphes de terrain est probablement le plus grand champ de recherche du domaine et l'étude des phénomènes de diffusion constitue un des axes importants dans la compréhension de ces objets. Beaucoupde précédentes études ont été menées sur la diffusion avec une approche théorique mais avec l'apparition de données issues du monde réel de plus en plus riches, une approche empirique de l'analyse de ces réseaux est apparue comme une nécessité. La diffusion peut être de différentes natures: diffusion d'information, d'idées  ou d'opinion. Cette diffusion est vue dans la plupart des travaux comme le résultat de l'interaction entre les éléments du réseau (i.e. les nœuds du graphe). En complément de cette vision, nous considérons dans cette thèse que la diffusion, en plus de se produire entre les nœuds, est aussi le résultat de l'interaction entre des groupes de nœuds, appelés communautés, qui ont des propriétés en commun. On dit que le réseau possède une structure en communautés. Cette approche ouvre de nouvelles perspectives pour la compréhension et la caractérisation des graphes de terrain. L'objectif de cette thèse est d'étudier les phénomènes de diffusion de manière empirique non seulement à l'échelle des nœud mais à différents niveaux de la structure en communautés. A l'aide d'une approche statistique, nous proposons un ensemble de méthodes et de métriques pour aborder la diffusion sous un nouvel angle et aller plus loin dans la caractérisation de ces phénomènes .Nous nous proposons d'étudier les liens de diffusion au sein d'un réseau de blogs francophones. Nous montrons en premier lieu l'impact des communautés sur la popularité des blogs et distinguons des classes de comportement. Cela nous conduit à investiguer les interactions entre les communautés. Pour ce faire, nous définissons deux mesures: la distance communautaire et l'Homophilie. En dernier lieu, nous étudions la diffusion de proche on proche dans le graphe, caractérisée par des cascades de diffusion. Nous montrons que notre approche permet de détecter et d'interpréter les différents comportements de diffusion et de faire le lien entre les propriétés topologiques, temporelles et communautaires.

Olivier Lespinet, Institut de Génétique et de Microbiologie, Univ. Paris-Sud
Génomique comparée et fouille de données enzymatiques
Jeudi 1er Décembre 2011, 11h, Amphi Herpin (bât. Esclangon)
Les champignons possèdent une très grande variété d'enzymes aux nombreuses applications potentielles. Nos travaux visent à étudier l'ensemble de cette diversité enzymatique afin de comprendre comment elle a pu prendre place et se maintenir au cours du temps. En utilisant des méthodes d'apprentissage et de fouille de données nous essayons également de voir dans quelle mesure la capacité enzymatique des champignons permet de rendre compte de leur évolution.

Thomas Aynaud, LIP6 (ComplexNetworks)

Soutenance de thèse

Détection de communautés dans les réseaux dynamiques
Mercredi 30 novembre 2011 à 14h en salle 25-26 / 105
La plupart des graphes de terrain ont une structure particulière constituée de communautés. Les noeuds sont organisés suivant des groupes appelés des communautés avec beaucoup de connexions internes mais peu entre eux. L'identification des communautés apporte un éclairage nouveau sur la structure du graphe et est importante dans de nombreux contextes. Elle a, par exemple, déjà été utilisée pour la visualisation de graphes et pour étudier différents types de réseaux comme des réseaux sociaux ou biologiques. Nous allons étudier cette structure dans le cas des réseaux dynamiques. Pour cela, nous allons suivre deux approches. La première consiste à suivre des communautés au cours du temps en les détectant à chaque instant et en suivant leur évolution. Nous verrons que bien que très naturelle, cette approche pose de nombreuses questions de stabilité : les algorithmes ont tendance à modifier beaucoup leur résultat même si le réseau change peu. Cela implique que les transformations observées dans les communautés sont en fait liées à l'algorithme et non à l'évolution de la structure du réseau. Nous proposerons donc une analyse de l'instabilité de trois algorithmes et une solution que nous validerons sur plusieurs graphes de terrain. La deuxième approche consiste à détecter la structure communautaire non pas juste pour un instant mais pour une période donnée appelée la fenêtre de temps. La durée de la période est alors un problème crucial et nous proposons une méthode de décomposition en fenêtres de temps dans un graphe dynamique. Une particularité de la méthode est que le résultat est un regroupement hiérarchique : les fenêtres de temps sont elles-mêmes susceptibles d'en contenir. En outre, les fenêtres n'ont pas besoin d'être contiguës ce qui permet par exemple de détecter une structure se répétant. Enfin, nous conclurons par des applications à la détection d'événements sur Internet et la segmentation de vidéos. Nous montrerons que l'on peut détecter des événements en trouvant les moments où la structure change brutalement et montrerons que nous détectons à la fois de nouveaux événements et des événements déjà identifiés par d'autres méthodes. Pour la segmentation de vidéos, nous avons aussi eu des problème de stabilité  et nous avons donc développé une méthode plus stable de suivi et de détection.

Lamia Benamara, LIP6 (ComplexNetworks)

Soutenance de thèse

Dynamique des graphes de terrain : caractérisation et étude du biais lié à la mesure
Mardi 29 novembre 2011 à 11h, en salle 25-26 / 105
Les graphes de terrain apparaissent dans de nombreux contextes : réseaux informatiques, réseaux biologiques, réseaux sociaux, graphes issus du web, etc. Jusqu'à récemment ces objets étaient principalement étudiés sous un angle statique. Or, la plupart de ces graphes sont en réalité des graphes dynamiques. Cette dynamique peut apparaître d'une façon différente selon les contextes : réseaux sociaux dans lesquels des connexions entre individus apparaissent et disparaissent au cours du temps, graphes du web dans lesquels des pages sont créées ou supprimées, etc. Un grand nombre de résultats de ces 10 dernières années ont introduit un ensemble d'outils pour l'analyse et la description des graphes statiques, mais peu a été fait pour l'étude de leur dynamique. Nous avons abordé dans cette thèse la problématique de la caractérisation de la dynamique des graphes de terrain tout en prenant en compte le biais lié à la mesure, en nous appuyant sur des cas concrets de graphes dynamiques. Nos contributions se sont orientées dans deux directions. Nous nous somme tout d'abord intéressés à l'étude du biais dans l'observation de la dynamique induit par le fait que la période d'observation est finie. Nous avons proposé une nouvelle méthodologie qui permet de déterminer si la longueur de la période d'observation est suffisante pour une caractérisation rigoureuse d'une propriété donnée. Cette méthodologie est générique et peut être appliquée à n'importe quelle propriété caractérisant un graphe de terrain dynamique. Pour démontrer la pertinence de notre méthodologie, nous l'avons appliquée à l'étude de différentes propriétés dans un système P2P. Notre deuxième contribution consiste en une approche pour étudier des graphes dynamiques. Nous avons cherché à la fois à caractériser la dynamique globale de ces systèmes, et à identifier les éventuels nœuds ayant un comportement particulier. Nous avons étudié plusieurs jeux de données issus de réseaux de contacts entre personnes et nous avons montré que chaque jeu de données a ses particularités. Nous avons également constaté que certaines caractéristiques sont partagées par tous les jeux de données. En particulier, la dynamique globale du réseau change en fonction de la période d'observation et le comportement de certains nœuds diffère du comportement global du système.

Bruno Pinaud, LABRI
PORGY : Un environement interactif et visuel pour la réécriture de graphes adapté aux systèmes complexes
Jeudi 17 Novembre 2011, 11h, salle 25-26/105
Les systèmes de réécriture de graphes sont simples à expliquer : ils réalisent des modifications sur un graphe en remplaçant des sous-graphes sélectionnés au préalable sur la base de règles de transformations. Néanmoins, la combinaison des règles pour leur application transforme l'étude de ces systèmes en un problème complexe. A cause de cela, les experts de ces systèmes se satisfont bien souvent de représentations textuelles ou alors de dessins fait à la main pour représenter les règles de transformations. Au cours de cet exposé, je présenterai PORGY qui est un environnement visuel et interactif pour la réécriture de graphe. Cet environnement conçu avec des experts de réécritures de graphes qui avaient envie d'un véritable système interactif et visuel permet de construire, simuler et raisonner de façon visuelle et interactive sur le système complexe à étudier.

Telmo Menezes, CAMS, EHESS
Evolutionary Modeling of Large Complex Networks
Jeudi 17 Novembre 2011, 11h, salle 25-26/105
Complex networks are a powerful abstraction that fits a variety of phenomena across several scientific fields, including biology, sociology and economy. Analyzing and extracting insights from large complex networks is an ongoing goal of Complexity Science. In this presentation we present a novel approach based on evolutionary computation and genetic programming. Our method relies on using simple computer programs to represent network generative models, and then applying evolutionary search to find the best generators for observed networks. The final goal of this work is to be able to map large complex networks to plausible generators that have an high explanatory power. For this approach to be successful, a few obstacles have to be overcome. One of these is the measure of quality that guides evolutionary search, which has high overlap with another open problem in network theory: how to measure the distance between large networks with arbitrary sizes and topologies. We present our own solution to this problem using centrality metrics and a well known image recognition algorithm.

Thomas Aynaud, LIP6, Complex Networks
Détection de communautés dans des réseaux dynamiques
Jeudi 29 Septembre 2011, 11h, salle 26-00/101
Dans la plupart des graphes de terrain, il existe des groupes de noeuds fortement liés entre eux mais peu à l'extérieur, appelés des communautés et leur identification est importante dans de nombreux contextes pour décrire la structure du graphe. Nous étudierons la détection de ces communautés dans le cas de graphes dynamiques. Premièrement, nous détecterons des communautés à chaque instant, ce qui pose des problèmes de stabilité. Ensuite, nous définirons des communautés pertinentes sur une longue durée et proposerons une méthode pour trouver les durées intéressantes. Nous verrons enfin des applications à la détection d'événements et à la segmentation de vidéos.

Marie-Aude Aufaure, Chair in Business Intelligence - Laboratoire MAS - École Centrale
Graphs for Business Intelligence
16 juin 2011 à 11h : salle 25-26/101

Business Intelligence aims at supporting better business decision-making, by providing tools and methods for collecting, modeling and interacting with data. Users have to deal with big data from structured databases and unstructured content (emails, documents, social networks, etc). Moreover, these data are often distributed and highly dynamic. Social Media and mobile technologies have changed our way to access information, facilitating communication and data exchange/sharing.  All these evolutions refer to Business Intelligence 2.0.

An adapted modeling and visualization technique of links and interactions between several objects (e.g. products and sites, customers and products, social network...) is a precious mean to permit a good understanding of a lot of situations in the enterprise context. In this latter context, most of the time, these objects and their relations are stored in relational databases. But extracting and modeling such heterogeneous graphs, with heterogeneous objects and relations, are outside of the classical graph models capabilities, moreover when each node contains a set of values. On the other hand, graph models can be a natural way to present these interactions and to facilitate their querying. In this way, we propose a graph model named SPIDER-Graph which is adapted to represent interactions between complex heterogeneous objects extracted from relational databases, used for heterogeneous objects graph extraction from a relational database. One of the steps involved in this approach consists in identifying automatically the enterprise objects. Since the enterprise ontology has been used for describing enterprise objects and processes, we propose to integrate it in the object identification process (identify objects to be able to transform a graph of heterogeneous objects according to the user choice). Finally, we introduce the main principles of an aggregation algorithm used for community detection and graph visualization.

Oussama Allali, ComplexNetworks - LIP6 - UPMC
Structure et dynamique des graphes de terrain bipartis : liens internes et prédiction de liens
26 mai 2011 à 11h : salle 25-26/101
Beaucoup de graphes de terrain, comme les relations acteur-film ou fichier-fournisseur, ont une nature bipartie et sont modélisés par des graphes bipartis, dont les nœuds sont divisés en deux ensembles avec des liens entre des nœuds de différents ensembles seulement. Cependant, il y a actuellement un manque de méthodes pour analyser correctement ces graphes, la plupart des méthodes existantes étant conçues pour des graphes classiques. Une approche courante, mais qui a des  limites, consiste à transformer les graphes bipartis en graphes classique, par un procédé appelé projection. Cependant ceci entraîne une perte importante d'informations. Dans cet exposé je présenterai les liens internes et je les proposerai comme une nouvelle notion importante pour analyser les graphes de terrain bipartis : elle permet de mesurer la redondance dans ces graphes, et de mesurer la perte d'information entre un graphe biparti et ses projections. Je montrerai en étudiant différents jeux de données que les liens internes sont très fréquents, et que les statistiques associées permettent de souligner les ressemblances et les différences entre les graphes de terrain bipartis et les graphes bipartis aléatoire. La plupart des graphes de terrain sont de plus dynamiques, c'est-à-dire que leur structure évolue au fil du temps par l'ajout et/ou le retrait de nœuds et/ou de liens. L'étude de la dynamique des graphes de terrain peut s'aborder par le problème de la prédiction de nouveaux liens dans ces graphes. Plusieurs travaux ont étudié le problème de la prédiction de liens dans les graphes classiques (non-bipartis). Toutefois, leurs méthodes ne sont pas directement applicables à, ou appropriées pour, les graphes bipartis. Je présenterai une approche basée sur les liens internes pour la prédiction dans les graphes bipartis. Je montrerai que notre méthode fonctionne très bien, beaucoup mieux que l'approche de recommandation classique.

Franck Ghitalla, INIST - CNRS
Des données, des graphes et des cartes
19 mai 2011 à 11h : salle 25-26/101
Au delà des graphes et des méthodes de leur visualisation, la cartographie de l'information représente un univers original qui a ses propres contraintes. L'exposé sera l'occasion de présenter les principales dimensions de la cartographie d'information, à partir d'exemples commentés.

Stefano Battiston, Chair of Systems Design - ETH Zurich, Suisse
Risk diversification and default cascades in financial networks
28 avril 2011 de 11h à 12h en salle 25-26/101
We introduce a discrete dynamics of distress propagation in networks. The formulation combines a diffusion and a contact process which are relevant to complex networks in general. In particular it is more suitable than previous  models to describe contagion processes occurring in the financial system. Our results indicate that diversification of risk at the individual level can have an ambiguous effect on the global level, leading in some cases to higher systemic risk. Moreover, we show that the same structure can be resilient or fragile depending on the relative strength of the two processes at play. In the financial context, this corresponds to the level of optimism in the market. Thus, our work has interesting implications for the debate on the network architecture that is most resilient to financial crises.

Binh-Minh Bui-Xuan, APR - LIP6 - CNRS & UPMC
Parameterized optimisation: a decomposition viewpoint
7 avril 2011 à 11h : salle 25-26/101

Decomposition is a technical term that, from an algorithmic point of view, refers to the act of dividing an input instance into simpler pieces. Popular examples of decomposition include Merge-Sort and the factorization of polynomials. Decomposition is fundamental for divide-and-conquer algorithms, and variants such as dynamic programming.

We first present a generic approach to design efficient decomposition algorithms on graphs, that will be expressed under the light of combinatorial optimisation over set famillies. We show how to apply the machinery on several old and new notions of decomposition. These decomposition notions can be extended so that NP-complete graph problems can be tackled within a reasonable (parameterized) runtime. To this aim we discuss on what can be qualified as two natural ways to generalise a particularly classical notion, the modular decomposition of graphs. One is tightly bound to a well-known topic in algorithmic graph theory called width parameters. The other links to recent works in clustering, social networks, complex systems, etc.

Emmanuel Lazega, IRISSO - Université Paris Dauphine
Dynamique des réseaux de conseil : les mécanismes sociaux à l’origine d’une stabilisation précaire
17 mars 2011 de 11h à 12h : salle 25-26/101
La question de savoir si la structure d’un collectif reste stable malgré un fort turnover de ses membres et un fort turnover des relations entre ces membres est une question classique de la sociologie. Nous proposons une réponse à cette question en procédant à une analyse longitudinale d’un réseau de conseil intra-organisationnel explorant la relation entre la structure formelle de l’organisation et un processus d’apprentissage collectif par ses membres. Nous identifions une structure centre-périphérie et un mouvement cyclique de centralisation-décentralisation du réseau de conseil. Nous expliquons cette dynamique comme l’effet d’une oscillation des membres de l’organisation entre surcharge et conflits épistémiques. La question de la stabilité de la structure malgré un fort turnover de ses membres et un fort turnover des relations entre eux est ainsi traduite en termes de stabilisation plus ou moins précaire de cette dynamique par les acteurs du système eux-mêmes.

Arnaud Legout, (Planète - INRIA)
Bluebear : Exploration des risques d’atteinte à la vie privée sur Internet
10 mars 2011 de 11h à 12h : salle 25-26/101
Les risques d'atteinte à la vie privée sur Internet sont largement sous estimés. Il est connu que les internautes laissent énormément d'informations personnelles sur, par exemple, les réseaux sociaux. Cependant, peu de gens savent que toute activité sur Internet laisse des traces. Dans cet exposé, nous allons montrer qu'il est possible de collecter ces traces à grande échelle et sans infrastructure dédiée. Plus précisément, nous allons montrer qu'il est possible de surveiller l'activité sur BitTorrent de centaines de millions d'internautes. Nous allons également montrer qu'en exploitant des mesures faites sur BitTorrent et sur un réseaux de voix sur IP, il est non seulement possible de lier à une identité réelle une liste de téléchargement de manière automatique, mais qu'il est également possible de suivre les déplacements d'un grand nombre de personnes sans que ces personnes n'aient aucun moyen de détecter ni de bloquer ces mesures.

Jean-Daniel Fekete, AVIZ - INRIA
Visualiser les réseaux par matrice d’adjacence : état de l’art et défis
24 février 2011 à 11h : salle 25-26/101
Les réseaux sont des objets complexes qui peuvent être analysés et explorés, généralement à l’aide de visualisation. Jusqu’à présent, la grande majorité des outils de visualisation utilise la représentation par nœuds et liens : les sommets sont représentés par des nœuds et les arcs par des lignes. Cette représentation est familière mais elle devient illisible lorsque le réseau devient dense. Alternativement, il est possible d’afficher la matrice d’adjacence du réseau en plaçant les sommets en lignes et colonnes et les liens en cellules à l’intersection de ces lignes et colonnes. Une cellule est marquée lorsqu’un arc existe entre le somme de la ligne et celui de la colonne. Cette représentation est moins familière mais reste lisible même lorsque la densité du réseau augmente. Ces dernières années, la représentation matricielle a été beaucoup étudiée : nous allons présenter les divers solutions proposées pour visualiser, ordonner et naviguer dans ces matrices d’adjacence, ainsi que les représentations mélangeant matrices avec nœuds et liens.

Ludovic Denoyer, MALIRE - UPMC
Learning Propagation Schemes in Multi-Graphs
10 février 2011 de 11h à 12h : salle 25-26/101
We consider the problem of labeling nodes in a multi-graph where the nodes may be connected with different types of relations. This type of problem occurs in many situations like for example the analysis of social networks or bibliographic data. Relations may be provided (e.g. friends) or computed (e.g. similarity). We propose a new learning algorithm for exploiting the rich multi-relational information in the labeling task. This method is able to optimally learn combining the influence of different relation types. It is one of the very first algorithms able to handle multi-graph information for this classi fication task. We describe experiments on four datasets which show the model ability to deal with complex relationships and to take bene fit of multi-relational information for complex labeling problems.

Damien Magoni, LaBRI - Université Bordeaux I
CLOAK: a virtual networking architecture
02 février 2011 de 14h à 15h : salle 26-00/228
In order to untie entities, applications and devices, CLOAK introduces a P2P overlay architecture and redefines the notion of a session. A session is a communication descriptor that contains everything needed for linking entities, applications and devices together in a flexible way. A session represents the identity and the management information of a given communication. Thus the lifetime of a communication between several entities is equal to the lifetime of its corresponding session. A device can move or be changed for another without terminating the session. Similarly, an application can be changed for another if deemed appropriate or even moved (i.e. mobile code) also without terminating the session. Finally entities can move or change (i.e. be transferred to another entity) without terminating the session if this is appropriate for a given communication. We can see that in our new architecture, entities, applications and devices are loosely bound together during a communication and all the movements and changes of devices, applications and entities are supported. To be able to implement our notion of session, we need to introduce several new layers of identifiers in order to decouple lower layers (devices) from middle layers (entities) and from higher layers (applications). Hence the name CLOAK given to this project. We add naming layers above the existing ones in order to give abstract names to objects such as entities and devices. Thus we lay a cloak on the current Internet architecture.

Mario Chavez, Cogimage, CRICM - CNRS & UPMC
Complex brain networks
27 janvier 2011
Electroencephalography, magnetoencephalography, or functional magnetic resonance imaging (fMRI) techniques are currently used to estimate functional connectivity patterns between different brain areas. In this talk I'll show how a complex network description might provide new insights into the understanding of human brain connectivity during different pathological and cognitive neuro-dynamical states.

Laurent Viennot, LIAFA - INRIA & Université Paris 7
Spanners de graphes
16 décembre 2010
Étant donné un graphe G, un spanner est un sous graphe H qui couvre tous les sommets de G. On s'intéresse alors à deux paramètres : la distance dans H par rapport à la distance dans G, et la taille de H en nombre d'arêtes. L'optimisation simultanée de ces deux paramètres conduit à des compromis que nous mettrons en évidence.

Juan David Cruz-Gomez, LUSSI - Telecom Bretagne
Point of View Based Clustering of Socio-Semantic Networks
03 décembre 2010
Classic algorithms for community detection in social networks use the structural information to identify groups in the social network, i.e., how clusters are formed according to the topology of the relationships. However, these methods don't take into account any semantic information which could guide the clustering process, and which may add elements to do further analyses. The method we propose, uses in a conjoint way, the semantic information from the social network, represented by the point of view, and its structural information. This is, by the combination of the relationships, expressed by the edges on one hand, and the implicit relations deduced from the semantic information on the other hand.

Dmitri Krioukov, University of California, San Diego
Optimal routing in a hyperbolically mapped Internet
07 juillet 2010
We establish a connection between the scale-free topology of complex networks, and the hyperbolic geometry of hidden metric spaces underlying these networks. Given a hyperbolic space, networks topologies with scale-free degree distributions and strong clustering naturally emerge on top of the space as topological reflections of its hyperbolic geometry. Conversely, for any scale-free network with strong clustering, there is an effective hyperbolic space underlying the network. The underlying hyperbolic geometry enables greedy routing with optimal efficiency. Greedy routing does not require any global information about network topology to navigate the network. At each hop, greedy routing selects as the next hop the current hop neighbor closest to the destination in the underlying hyperbolic space. We show that in complex networks mapped to their hyperbolic spaces, greedy routing always succeeds reaching the destination, following the topologically shortest paths. Furthermore, we show that even without re-mapping the network or changing any node coordinates, this navigation efficiency is remarkably robust with respect to rapid network dynamics, and catastrophic levels of network damage. We map the real Internet AS-level topology to its hyperbolic space, and find that greedy routing using this map exhibits similar efficiency. These results effectively deliver a solution for Internet interdomain routing with theoretically best possible scaling properties. Not only routing table sizes and stretch are as small as possible, but also routing communication overhead is reduced to zero.

Shaowen Qin, Flinders University - Australie
Clustering of Software Classes at Execution and Its Implications
17 juin 2010
We present a study on clustering of software classes based on software execution data, which offers a dynamic, hence more realistic, perspective to the understanding of software structure and the evaluation and improvement of the existing architectural design. The approach first uses association rule mining to extract low-level class relations in object-oriented software. The mining results are then processed by hypergraph-based clustering to identify an optimal set of high-level clusters of classes that have relatively high cohesion within and low coupling between them. It is also shown that such clusters are actually unique. The identified clusters can be seen as execution components of the software, which represents the effect, rather than the intention of the existing design. Two case studies are presented to demonstrate the application of our approach. Relevant concepts in complex network are also introduced to interpret the findings of this study

Alina Stoica, LIAFA - Université Paris 7
Réseaux sociaux: une analyse centrée sur l’individu
10 juin 2010
Pour le développement des services ou le marketing, la connaissance des utilisateurs (des plateformes sociales en ligne, du téléphone mobile, fixe etc.) est très importante. Pour améliorer cette connaissance, on peut analyser les usages, collecter des données socio-démographiques ou étudier les réseaux sociaux modélisant les relations entre les utilisateurs. Dans cet exposé je présenterai une méthode permettant de caractériser chaque individu en utilisant le réseau social auquel il est connecté. Après avoir obtenu une caractérisation de chaque personne, on peut alors mesurer les corrélations avec d'autres indicateurs liés à l'individu. Je présenterai la comparaison de cette caractérisation prenant en compte le réseau social avec des indicateurs de popularité en ligne sur MySpace et de fréquence de communication par téléphone mobile.

Jussara Almeida, Federal University of Minas Gerais, Brazil
Detecting Non-Cooperative User Behavior in Online Social Networks
10 juin 2010
A number of online video social networks, out of which YouTube is the most popular, provides features that allow users to post a video as a response to a discussion topic. These features open opportunities] for users to introduce polluted content into the system. For instance, spammers may post an unrelated video as response to a popular one aiming at increasing the likelihood of the response being viewed by a larger number of users. Moreover, opportunistic users - promoters - may try to gain visibility to a specific video by posting a large number of (potentially unrelated) responses to boost the rank of the responded video, making it appear in the top lists maintained by the system. In this talk, I will present some of our initial results on detecting spammers and content promoters on YouTube. Our study is based on a characterization of several properties associated with YouTube users as well as the use of state-of-the-art classification algorithms.

Etienne Birmelé, Université d'Evry
Définition et détection de motifs locaux dans les graphes biologiques
25 mai 2010
Une approche classique d'analyse statistique des réseaux biologiques est de déterminer les motifs de ces réseaux, c'est-à-dire les sous-graphes dont le nombre d'occurrences dans le réseau est significativement plus élevé que dans un modèle aléatoire, l'idée directrice étant que leur présence en sur-nombre indique une sélection positive au cours de l'évolution. Cependant, les méthodes existantes se réfèrent à une sur-représentation dans l'ensemble du graphe alors qu'il est connu que les motifs ayant un intérêt biologique ont tendance à s'agglomérer en certaines régions du graphe.
Je définirai la notion de motif local et développerai les trois aspects que nécessite leur détection:
  • le modèle de réseaux aléatoires sous-jacent
  • le problème de comptage du nombre d'occurences d'un sous-graphe dans un réseau
  • la mise au point d'une statistique permettant de décider si un sous-graphe est sur-représenté
Enfin, je développerai l'application de la méthode au réseau de régulation de la levure.

Marie-Noelle Comin, Géographie-cités - Université Paris 4
Research networks and urban dynamics in Europe
29 avril 2010
Cities concentrate economic activities, information, power and people in both quantitative and qualitative ways. Cities are also nodes of networks of complex interconnection. In Europe, the construction of a large supranational entity results spatially in the multiplication and the intensification of the relations between politically unified countries. The majority of these relations pass through cities. Then very complex links underpin the European system of cities and understanding them is critical to understanding the interdependencies in the system.
In this talk, the interconnection of the European national urban systems is studied by analysing knowledge spillovers which flow between the European cities. Knowledge spillovers are considered as an input and also an output of the innovation process.
For the analysis, I consider networks created by collaborative research in European funded research and technology development projects dedicated to converging technologies. Data come from the EC database CORDIS RTD-PROJECTS drawn from the 2nd to the 6th European Framework Programmes (1986 to 2006).
Cities concentrate economic activities, information, power and people in both quantitative and qualitative ways. Cities are also nodes of networks of complex interconnection. In Europe, the construction of a large supranational entity results spatially in the multiplication and the intensification of the relations between politically unified countries. The majority of these relations pass through cities. Then very complex links underpin the European system of cities and understanding them is critical to understanding the interdependencies in the system. In this talk, the interconnection of the European national urban systems is studied by analysing knowledge spillovers which flow between the European cities. Knowledge spillovers are considered as an input and also an output of the innovation process. For the analysis, I consider networks created by collaborative research in European funded research and technology development projects dedicated to converging technologies. Data come from the EC database CORDIS RTD-PROJECTS drawn from the 2nd to the 6th European Framework Programmes (1986 to 2006).

Hoàng Anh Phan, <acronym title="Laboratoire d'Informatique Algorithmique: Fondements et Applications">LIAFA</acronym> - Université Paris 7
Application du paradigme pair-à-pair à la gestion de systèmes distribués
15 avril 2010
Le paradigme « pair-à-pair » (ou P2P, pour peer-to-peer) s’oppose au paradigme « client-serveur ». Dans un système pair-à-pair dont les utilisateurs partagent un ensemble de ressources, telles que des fichiers ou des ressources de calcul, tous jouent le même rôle. En particulier, chaque utilisateur peut agir comme serveur pour certains pairs, et comme client pour d’autres. Plusieurs méthodes de publication et de recherche de ressources ont été proposées pour les systèmes P2P. Parmi ces propositions, les tables de hachage distribuées (ou DHT, pour Distributed Hash Table) se basent sur un plongement des ressources et des utilisateurs dans un même espace métrique, appelé espace des clés. Cette espace possède une structure permettant le routage, sur lequel peut construire les fonctions de publications et de recherches.
En effet, les réseaux P2P peuvent être utilisés comme support de diffusion multimédia. La fonctionnalité de multicast n’ayant pas encore été déployée à grande échelle dans l’Internet au niveau IP, plusieurs propositions visent à promouvoir le déploiement de procédures de multicast au niveau applicatif, par exemple dans un réseau logique P2P.
Je parlerai dans un premier temps de la mise en marche du protocole P2P D2B : gestion de la dynamicité du réseau, des joints et départs en même temps, de la tolérance aux pannes. Ensuite, je présenterai de trois méthodes d’équilibrage de charge dans les réseaux P2P basés sur les graphes de De Bruijn. Enfin, je décrirai un algorithme multicast: Tree-Farm, basés sur l’ensemble des arbres nœuds intérieurs disjoints. Nous avons montré que, dans le cas des systèmes P2P utilisant la topologie des graphes de De Bruijn, Tree-Farm atteignait une meilleure bande passante (pour un taux de perte nul) que l’algorithme BFS utilisant un seul arbre multicast enraciné en la source ou que l’algorithme PrefixStream [L. Viennot et A. T. Gai - ICON2006].
Le paradigme « pair-à-pair » (ou P2P, pour peer-to-peer) s’oppose au paradigme « client-serveur ». Dans un système pair-à-pair dont les utilisateurs partagent un ensemble de ressources, telles que des fichiers ou des ressources de calcul, tous jouent le même rôle. En particulier, chaque utilisateur peut agir comme serveur pour certains pairs, et comme client pour d’autres. Plusieurs méthodes de publication et de recherche de ressources ont été proposées pour les systèmes P2P. Parmi ces propositions, les tables de hachage distribuées (ou DHT, pour Distributed Hash Table) se basent sur un plongement des ressources et des utilisateurs dans un même espace métrique, appelé espace des clés. Cette espace possède une structure permettant le routage, sur lequel peut construire les fonctions de publications et de recherches. En effet, les réseaux P2P peuvent être utilisés comme support de diffusion multimédia. La fonctionnalité de multicast n’ayant pas encore été déployée à grande échelle dans l’Internet au niveau IP, plusieurs propositions visent à promouvoir le déploiement de procédures de multicast au niveau applicatif, par exemple dans un réseau logique P2P. Je parlerai dans un premier temps de la mise en marche du protocole P2P D2B : gestion de la dynamicité du réseau, des joints et départs en même temps, de la tolérance aux pannes. Ensuite, je présenterai de trois méthodes d’équilibrage de charge dans les réseaux P2P basés sur les graphes de De Bruijn. Enfin, je décrirai un algorithme multicast: Tree-Farm, basés sur l’ensemble des arbres nœuds intérieurs disjoints. Nous avons montré que, dans le cas des systèmes P2P utilisant la topologie des graphes de De Bruijn, Tree-Farm atteignait une meilleure bande passante (pour un taux de perte nul) que l’algorithme BFS utilisant un seul arbre multicast enraciné en la source ou que l’algorithme PrefixStream [L. Viennot et A. T. Gai - ICON2006].

Monojit Choudhury, Microsoft Research Lab - Bangalore, India
What does spectral analysis tell us about the global structure of a network? Some case studies in linguistic networks
09 avril 2010
One of the very important aspect of studying any complex network is to characterize and describe its global structure, which, by definition, is too complex to be described in terms of simple statistics. Traditionally aggregate statistics of certain local properties, such as degree distribution, assortatitivity, and clustering coefficient are used to characterize the topology of the network, but these statistics do not capture the global structure of a network. In this talk, I shall describe how the spectrum of a network (i.e., the eigenvalues and eigenvectors of the adjacency matrix of the network or its Laplacian) provides us with valuable insight into the global structure of the network and therefore, the underlying physical processes generating it. I will take the following three case studies from the domain of language to illustrate this: (a) the co-occurrence networks of words, (b) the networks of syntactic and semantic similarity of the distribution of words, and (c) the co-occurrence network of phonemes (PhoNet).

Marc Barthelemy, IPhT, CEA & CAMS, EHESS
Spatial organisation of large networks
08 avril 2010
Most transportation networks are embedded in space and consequently, their topology is not independent from spatial constraints. In particular, these constraints can induce a hierarchical organization with hubs controlling specific regions of space, non-trivial correlations between the weights, the connectivity pattern and the actual spatial distances of vertices, and the emergence of anomalous fluctuations in the betweenness-degree correlation function. In this talk I will illustrate these effects both from an empirical and modeling point of view, with various examples ranging from the large scale air travel network to smaller scales of inter- and intra- cities transportation networks.

Mathieu Bastian, INIST - CNRS
Gephi 0.7 – Modular Architecture for a Large Network Visualization Software
25 mars 2010
In this practical talk, I will present 0.7 version of Gephi, open-source graph visualization & manipulation software. Gephi possesses a complete set of network visualization and analysis features, proposes major innovations in dynamic and hierarchical graphs and above all is a flexible and extensible architecture for plugins. I will firstly sum up embedded features: Layout, Metrics, Ranking, Filters, Partition, Preview, Clustering, DataLab. Then, I will present and discuss dynamic and hierarchical graphs features and roadmaps while showing live demo. Afterwards, I will outline our approach by presenting the Gephi project, some insights about performance and the various possibilities of using and extending Gephi in the way scientists and engineers can rely on. To conclude I will speak about plugin development and show how to create a plugin in five minutes.

Jean-Jacques Pansiot, LSIIT - Université de Strasbourg
Extracting Intra-Domain Topology from mrinfo Probing
11 mars 2010
Active and passive measurements for topology discovery have known an impressive growth during the last decade. If a lot of work has been done regarding inter-domain topology discovery and modeling, only a few papers raise the question of how to extract intra-domain topologies from measurements results. In this paper, based on a large dataset collected with mrinfo, a multicast tool that silently discovers all interfaces of a router, we provide a mechanism for retrieving intra-domain topologies. The main challenge is to assign an AS number to a border router whose IP addresses are not mapped to the same AS. Our algorithm is based on probabilistic and empirical IP allocation rules. The goal of our pool of rules is to converge to a consistent router to AS mapping. We show that our router-to-AS algorithm results in a mapping in more than 99% of the cases. Furthermore, with mrinfo, point-to-point links between routers can be distinguished from multiple links attached to a switch, providing an accurate view of the collected topologies. Finally, we provide a set of large intra-domain topologies in various formats.

Pierre Borgnat, SISYPHE - ENS & CNRS
Unsupervised host behavior classification from connection patterns
04 mars 2010
Dans un but de classification du trafic émis par des ordinateurs via internet mais aussi de détection des anomalies de trafic, une méthode de caractérisation des communications d'ordinateurs est étudiée. Un espace de représentation des motifs de connexions de chaque ordinateur est étudié en ce qu'il représente le trafic échangé, la dispersion de ce trafic, la connectivité de l'ordinateur. On montrera que cette représentation permet par exemple de quantifier plus finement les graphlets empiriques utilisés par la méthode BLINC (Karagiannis et al. 2005). Cette représentation du trafic échangé permet alors de mettre en place une classification non supervisée du trafic internet par une approches de classification par MST (Minimum Spanning Tree), sur des liens backbones et sans disposer du contenu des paquets ni du trafic bidirectionnel (ici validé sur le trafic backbone d'un lien transpacifique opéré par WIDE, Japon).

Marc Lelarge, TREC - ENS & INRIA
Diffusions et cascades dans les graphes aléatoires
25 février 2010
Nous introduisons un modèle de diffusion qui généralise à la fois le processus de contact et la percolation 'bootstrap'. Nous analysons ce processus sur des graphes aléatoires dilués. Ceci nous permet de retrouver des résultats connus (taille de la composante géante, seuil de percolation) et nouveaux (condition de cascade, impact de différentes vaccinations). Les preuves reposent sur des idées de couplages développées récemment par Janson et Luczak.

Réseaux sociaux égocentriquesActive learning on networks : you must label all nodes. You can ask the true labels of 42 nodes. Choose wisely.
28 janvier 2010
In many networks, vertices have hidden attributes that are correlated with the network’s topology. For instance, in social networks, people are more likely to be friends if they are demographically similar. In food webs, predators typically eat prey of lower body mass. We explore a setting in which the network’s topology is known, but these attributes are not. If each vertex can be queried, learning the value of its hidden attributes — but only at some cost — then we need an algorithm which chooses which vertex to query next, in order to learn as much as possible about the attributes of the remaining vertices. We assume that the network is generated by a probabilistic model, but we make no assumptions about the assortativity or disassortativity of the network. We then query the vertex with the largest mutual information between its type and that of the others (a well-known approach in active learning) or with the largest average agreement between two independent samples of the Gibbs distribution which agree on its type. We test these approaches on two networks with known attributes, the Karate Club network and a food web of species in the Weddell Sea. In several cases, we found that the average agreement algorithm performs better than mutual information, and both perform better than simpler heuristics. The algorithms appear to explore the network intelligently, first querying vertices at the centers of communities, and then vertices along the boundaries between communities.

Marcelo Dias De Amorim, LIP6 - CNRS & UPMC
Looking into the surround of contacts in intermittently-connected wireless networks
14/01/2010, de 11H00 à 12H00, en salle 847
In this talk, we will discuss some preliminary work on the spatial characterization of intermittently-connected wireless networks. The motivation is that the literature has focused almost exclusively on the temporal aspect of contacts and inter-contacts between nodes. Furthermore, it is frequently assumed that contacts have infinite capacity, which is a too strong consideration especially in wireless networks. We propose the surround indicator as a metric to exhibit the spatial dimension of contacts in opportunistic networks. This metric can be used for example as a measure of potential interference that a contact might undergo or to understand the validity of forwarding strategies like betweenness centrality. We evaluate the surround indicator on two existing datasets. Our preliminary results reveal that contacts have too heterogeneous surrounds to be considered only in terms of duration. This work is part of Nadjet Belblidia's thesis and is done in collaboration with Jérémie Leguay (Thalès), Vania Conan (Thalès), Jon Crowcroft (Cambridge University), and Serge Fdida (UPMC).

Christophe Prieur, LIAFA - Université Paris 7
Réseaux sociaux égocentriques
19/11/2009, de 11H00 à 12H00, en salle 555
En dix ans, la vision Google des réseaux sociaux a cédé la place à la vision Facebook. Dans le milieu des années 90, avec l'apparition du web et son intégration progressive dans la société, s'est répandue l'image d'un monde connecté, village global traversé par les autoroutes de l'information permettant de relier n'importe qui à n'importe qui d'autre en six degrés de séparation. En 1998, Google apportait à cette civilisation-là un algorithme permettant de traiter le gigantesque bazar que constituait déjà le graphe des pages web, permettant d'en extraire les pages les plus pertinentes pour le genre humain. Aujourd'hui, les résultats de Google sont un acquis, c'est la wikipédie de tout un chacun, presque aussi poussiéreuse que le Larousse de la grand-mère. Je sais, quand j'en ai besoin, chercher des informations dans le réseau des réseaux, reste donc à trouver des informations quand je ne les cherche pas (Google ne me dira ce qu'est Paf le chien que si j'ai l'idée de le lui demander), et pour cela, écouter ce qui se passe dans... mon réseau. Parce que si je suis à O(6) degrés de séparation de n'importe qui, je préfère réduire la portée de mon réseau pour limiter la cacophonie, et le pagerank ne m'aidera pas pour ça. Nous allons donc profiter de notre expérience de vieux googliens pour aborder les réseaux personnels avec des outils que les « anciens » analystes des réseaux sociaux n'avaient pas, quitte à ce qu'ils nous reprochent de leur piquer leur jouet.

Fabien de Montgolfier, LIAFA - Université Paris 7
Vidéo à la demande en Peer-to-peer intégral
12/11/2009, de 11H00 à 12H00, salle 847
La vidéo « à la demande » (VoD) est un service en pleine expansion. Avec le développement des modems (« box ») d'accès à l'ADSL, offrant maintenant des capacités de stockage, on peut imaginer un service totalement décentralisé. Les films sont pré-chargés sur certains modems. Les utilisateurs se connectent aux modems qui les ont pré-chargés et visionnent, sans intervention d'un serveur (d'où un service robuste et à coût faible). Nous montrons que le nombre de films disponibles peut croitre de façon linéaire (ou quasi-linéaire sous d'autres hypothèses) en fonction du nombre de modems et que toutes requêtes d'utilisateurs peuvent être satisfaites AFP. Travail réalisé avec Y. Boufkhad, F. Mathieu, D. Perino et L. Viennot.