Les résumés des cours avec les liens vers le matériel de présentation sont donnés plus bas dans cette page.




Cours (3h)

  • Théorie spectrale pour les réseaux complexes

    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
     

Cours (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
     

  • Notion d'hyperbolicité dans les graphes

    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
     

Tutoriels

  • Introduction à la plate-forme GAMA par la pratique : développement d'un modèle de diffusion d'une maladie dans un contexte urbain

    Patrick Taillandier (UMR 6266 CNRS IDEES, Université de Rouen)

    La modélisation à base d'agents est de plus en plus utilisée pour l'étude des systèmes complexes. Cette approche de modélisation permet de prendre en compte l'hétérogénéité des entités composant le système étudié et de l'étudier à différent niveaux. Si concevoir un modèle à base d'agents requière des compétences importantes en informatique, ces dernières années ont vu le développement de différentes plates-formes permettant de faciliter leur développement. Cette session sera consacrée à une introduction à l'un de ces plates-formes : GAMA. Cette plate-forme open-source offre un environnement intégré de développement ainsi qu'un langage de modélisation dédié permettant de simplement définir des modèles complexes. Dans le cadre de cette session, nous proposerons dans une première partie une présentation de la plate-forme GAMA et des nombreux outils qu'elle intègre. Nous proposerons ensuite, dans une seconde partie, un tutoriel consacré à la propagation d'une épidémie dans une petite ville. Ce tutoriel sera l'occasion de présenter l'utilisation de quelques outils de GAMA : intégration de données géographiques, utilisation de graphes spatiaux et sociaux, visualisation 3D...
      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
     

Présentations par les étudiants

 
 
CNRS GDR-ASR UNS I3S INRIA EDSTIC