•  
  •  
  •  
  •  
  •  
  •  
News and upcoming events:
  • January 31, 2009: CFP - Special issue of TSI on Complex Networks (in french) - deadline
  • December 1, 2008: Lamia Benamara begins her PhD in the team.
  • November 2008: Paper A Radar for the Internet accepted in the proceedings of ADN'08
  • November 2008: Paper Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs accepted in JEA
  • >>> Read More

Recent Papers:
  • Main-memory Triangle Computations for Very Large (Sparse (Power-Law)) Graphs, Matthieu Latapy, Theoretical Computer Science (TCS) 407 (1-3), pages 458-473, 2008.
  • Abstract
    Finding, counting and/or listing triangles (three vertices with three edges) in massive graphs are natural fundamental problems, which received recently much attention because of their importance in complex network analysis. We provide here a detailed survey of proposed main-memory solutions to these problems, in an uni?ed way. We note that previous authors paid surprisingly little attention to space complexity of main-memory solutions, despite its both fundamental and practical interest. We therefore detail space complexities of known algorithms and discuss their implications. We also present new algorithms which are time optimal for triangle listing and beats previous algorithms concerning space needs. They have the additional advantage of performing better on power-law graphs, which we also detail. We ?nally show with an experimental study that these two algorithms perform very well in practice, allowing to handle cases which were previously out of reach.
  • Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs, Clémence Magnien, Matthieu Latapy and Michel Habib, To appear in ACM Journal of Experimental Algorithmics (JEA).
  • Abstract
    The diameter of a graph is among its most basic parameters. Since a few years, it moreover became a key issue to compute it for massive graphs in the context of complex network analysis. However, known algorithms, including the ones producing approximate values, have too high a time and/or space complexity to be used in such cases. We propose here a new approach relying on very simple and fast algorithms that compute (upper and lower) bounds for the diameter. We show empirically that, on various real-world cases representative of complex networks studied in the literature, the obtained bounds are very tight (and even equal in some cases). This leads to rigorous and very accurate estimations of the actual diameter in cases which were previously untractable in practice.
  • A Radar for the Internet, Matthieu Latapy, Clémence Magnien and Frédéric Ouédraogo, To appear in the proceedings of ADN'08: 1st International Workshop on Analysis of Dynamic Networks, in conjonction with IEEE ICDM 2008.
  • Abstract
    In contrast with most internet topology measurement research, our concern here is not to obtain a map as complete and precise as possible of the whole internet. Instead, we claim that each machine's view of this topology, which we call ego-centered view, is an object worth of study in itself. We design and implement an ego-centered measurement tool, and perform radar-like measurements consisting of repeated measurements of such views of the internet topology. We conduct long-term (several weeks) and high-speed (one round every few minutes) measurements of this kind from more than one hundred monitors, and we provide the obtained data. We also show that these data may be used to detect events in the dynamics of internet topology.
  • Description and simulation of dynamic mobility networks., Pierre Borgnat, Eric Fleury, Jean-Loup Guillaume, Céline Robardet and Antoine Scherrer, Computer Networks 52 (2008), pp. 2842-2858.
  • Abstract
    During the last decade, the study of large scale complex networks has attracted asubstantial amount of attention and works from several domains: sociology, biology,computer science, epidemiology. Most of such complex networks are inherently dy-namic, with new vertices and links appearing while some old ones disappear. Untilrecently, the dynamic of these networks was less studied and there is a strong needfor dynamic network models in order to sustain protocol performance evaluationsand fundamental analyzes in all the research domains listed above.We propose in this paper a novel framework for the study of dynamic mobilitynetworks. We address the characterization of dynamics by proposing an in-depthdescription and analysis of two real-world data sets. We show in particular thatlinks creation and deletion processes are independent of other graph properties andthat such networks exhibit a large number of possible con¯gurations, from sparse todense. From those observations, we propose simple yet very accurate models thatallow to generate random mobility graphs with similar temporal behavior as theone observed in experimental data.

>>> All Papers

Plot of the week   –   All plots

courbe

Guillaume Valadon, Florian Le Goff and Christophe Berger

Video of the month   –   All videos

courbe

Matthieu latapy

    contact@complexnetworks.fr Links