Abstracts of the lectures and materials (slides, links to relevant web sites) are given below the calendar.
Lectures (3h)
-
Spectral Theory for Complex Networks
Charles Bordenave (CNRS, Institut de Mathématiques, Université de Toulouse)In this lecture, we will first review the main notions of spectrum that have been used to understand complex networks and natural dynamics on these networks (such as the random walk). Then, for the simplest probabilistic models of large networks, we will see how these spectra can be described using concepts of random matrix theory and limit graph theory. The lecture will not require a prior knowledge on the subject apart from the most basics definitions of linear algebra and probability.
Slides in pdf
-
Multiscale Processing on Networks and Community Mining (slides part I part II)
Pierre Borgnat (Physics Laboratory (UMR 5672), ENS Lyon, CNRS, Université de Lyon, France)For the study of networks (especially when they are large) and for the analysis of signals or data deployed on the network, the issue of the scale of analysis is relevant. Recent advances in signal processing for graph signals has led to the developments of many multiscale representations over graphs (such as wavelet transforms on graphs) and, after recalling their definitions and properties, we will review how they can be used to process data on graphs or to learn information about the structure of graphs. One topic will be covered in particular : how the multiscale wavelet transform can be used to revisit the classical question of finding communities in networks in a multi scale approach.
Slides in pdf: part I part II
-
Spreading processes on complex networks: structure and dynamics
Márton Karsai (LIP-ENS Lyon, INRIA Grenoble)Spreading phenomena are in the focus of several fields of research ranging from epidemiology to computational science. Typically these processes can be captured by compartment models, which are evolving on networks coding the possible interactions of connected entities. Therefore the dynamics of spreading phenomena are strongly determined by the topological features of the backgrounding networks. The aim of this lecture is to give an introduction to the modelling of spreading processes. First we are going to introduce the conventional models of spreading behaviour, we will understand how their global outbreaks depend on the topology of the backgrounding network, and discuss strategies one can follow to suppress and control their global diffusion. Finally we will gain insight into models capturing the co-evolution of spreading processes with time-varying network structures.
Slides in pdf
Lectures (1h30)
-
Random Walk Based Algorithms for Complex Network Analysis
Konstantin Avratchenkov (Inria, Sophia Antipolis, France)Typical questions in the analysis of large complex networks are how large is a network in terms of nodes and links? which nodes are most important/central? the degree distribution follows a power law? if yes, what is the exponent of the power law? how to estimate quickly the clustering coefficient? how to detect quickly principal clusters/communities of the network? All these questions can be answered with the help of the theory of random walks on graphs. In particular, using the theory of random walks on graphs, we can design algorithms with linear or even sublinear complexity. Such light complexity is necessary if we need to deal with networks of billions of nodes and links.
Slides in pdf
-
The notion of hyperbolicity in graphs
David Coudert (EPC COATI, Inria et laboratoire I3S (CNRS/UNS), Sophia Antipolis)The Gromov hyperbolicity is an important parameter for analyzing complex networks since it expresses how the metric structure of a network (distances) looks like the metric structure of a tree. For instance, it gives bounds on the best possible stretch resulting from the embedding of a network into a weighted tree. It is also used to provide bounds on the expected stretch of greedy-routing algorithms in Internet-like graphs. However, the best known algorithm for computing this parameter has time complexity in O(n^3.69), which is prohibitive for large-scale graphs such as the graph of the Autonomous System of the Internet (more than 40.000 nodes).
In this presentation, we will explain how to compute this parameter on Internet-like graph. We will first present methods for drastically cutting the search space and resulting in a simple and efficient algorithm. Then, we will survey decompositions methods (biconnected components, split, clique-separators) used as pre-processing for reducing the size of the input graph. Last, we will present some heuristics proposed to compute this parameter on graphs with millions of nodes.
Slides in pdf
-
Centers and diameter computations in huge graphs and some extensions
Michel Habib (LIAFA, UMR 7089 CNRS & Université Paris Diderot - Paris 7, France)When the size of the graph (or network) you study is huge, (i.e. so big that no exact algorithms having a quadratic complexity can be applied in the biggest computer you have access to), then you are forced to use or invent new linear time heuristics or linear time approximation algorithms. So when dealing with huge graphs even for polynomial problems it is worth to consider linear time processing.
I will explain in full details our results on computing centers and diameter of huge graphs, using very few successive Breadth First Searches (BFS). I will try to explain why our experimental results are so good. Such an approach could be extended to the computation of other graph parameters such as betweenness or some other centrality parameters.
Graph search is a very efficient tool to deal with huge graphs : easy to implement, and no need to store the whole graph is memory. At each step only the adjacency list of the current vertex is needed. Furthermore using a series of dependant consecutive graph searches may help to find some of the structure of a given graph. For example smoothing the graph in order to find an approximate modular decomposition. I will describe new results and some research directions in this area. For example for max flow problems several polynomial time algorithms are known, but no linear time approximation algorithms is known yet. This could be a goood challenge.
Slides in pdf
-
Internet measurements: topology discovery and dynamics
Renata Cruz Teixeira (Inria, France)A better understanding of the Internet topology and its dynamics is key for a wide range of tasks from network planning and diagnostics to the development of online services. Due to the distributed nature of the Internet, however, no single entity has full knowledge of the topology. Thus, researchers, network administrators, and service providers often resort to traceroute to infer end-to-end paths and then combine paths into a network topology. Traceroute sends probes to a destination with an increasing Time-To-Live (TTL) to force routers along the path to send an error message, which reveals the IP address of the router’s interface that issued the error message.
This talk will present techniques to map Internet topologies with traceroute. There are a number of challenges in mapping the Internet topology and tracking its dynamics with traceroutes. First, traceroute’s output may be inaccurate or incomplete. Second, traceroute reports the address of one of the interfaces of the router. We must then identify which interfaces belong to the same a router (a process often called alias resolution). Third, probing a large number of paths in the hope to cover a large fraction of the topology takes time during which the underlying topology may change. There is a tradeoff between how fast we can measure each individual path to track dynamics and how many paths we can measure. We will discuss recent research advances that address the challenges above.
Slides in pdf
Tutorials
-
Practical Introduction to the GAMA platform: development of a model about the disease diffusion in an urban context
Patrick Taillandier (UMR 6266 CNRS IDEES, Université de Rouen)The agent-based modeling is more and more use to study complex systems. This modeling approach allows to take into account the heterogeneity of the entity composing the system and to study it at different levels. If building an agent-based model requires high-level skills in computer science, these last years have seen the development of several platforms allowing to ease their implementation. This course will be dedicated to an introduction to one of these platforms: GAMA. This open-source platform offers an integrated development environment and a dedicated modeling language allowing to simply define complex models. In the context of this course, we will propose in a first part a presentation of the GAMA platform and of the numerous tools it integrates. Then, in a second part, we will propose a tutorial concerning the propagation of a disease in a small city. This tutorial will allow to present some specific features of GAMA: integration of GIS data, use of spatial and social graphs, 3D visualization...
Gama web page
Slides in pdf
-
Tulip Data Visualization Software
David Auber (LaBRI, Univ. Bordeaux)Dans ce tutorial nous présenterons tout d'abord les fonctionnalités de la plateforme de Visualisation de données Tulip (www.tulip-software.org). Cette plateforme permet la visualisation et l'analyse de grands graphes. Elle offre un large panel d'algorithmes et de visualisations. Elle permet de tester interactivement des chaînes de traitement complexes en combinant ces algorithmes et ces visualisations. Après une présentation du méta-model de donnée utilisé dans Tulip nous présenterons une liste non exhaustive des algorithmes et visualisation existantes. Nous montrerons que Tulip permet :
- De calculer des mesures sur les graphes
- De calculer des clusters sur les graphes
- De dessiner les graphes
- De visualiser des graphes avec plusieurs métaphores visuelles : noeud lien, matricielle, arc diagram, pixel oriented, SOM, Geo-map et coordonnées parallèles.
Dans la deuxième partie de ce tutorial nous regarderons comment intégrer ses propres algorithmes dans la plateforme Tulip. Pour cela nous nous concentrerons sur l'environnement de développement Python qui est intégré dans Tulip 4.5. Après une description du fonctionnement, nous passerons à la pratique. L'objectif à atteindre est d'être capable d'écrire son propre plug-in Tulip.
Tulip web site
Students presentations
-
Students presentations (session 1)
Name Title Guillaume Artero-Gallardo On Estimating the End-to-End Bandwidth in Multi-Transceiver Multi-Hop Cognitive Radio Networks Benjamin Baron How to expand the boundaries of the Internet through vehicles? Maximilien Danisch Community detection and proximity measures Samuel Marchal URL Semantic Analysis for Phishing Detection Jean-Gabriel Krieg Setting up a testbed with USRP N210 Dimitrios Milioris Topic Detection and Trend Sensing in Twitter via Joint Complexity Patrice Raveneau WSN and observation satellites Tristan Braud Response time of antiparallel connections with respect to congestion control algorithms
-
Students presentations (session 2)
Name Title Diala Naboulsi Human Dynamics - An Urban Networking Perspective Brahim Neggazi Self-stabilizing algorithms for graph parameters Stephen Pirlot Newtork Models, Survivability quantification Victor Ramiro Random walk meets temporal graphs: applications on Opportunistic networks Jithin K. Sreedharan Distribution and dependence of extremes in PageRank-type processes Sid Ali Selmane A new efficient method for community detection based on formal concept analysis Noé Gaumont Detection of links community