Tag Archives: graph

Papers

Deciding on the type of the degree distribution of a graph from traceroute-like measurements

By admin | Published: May 25, 2012

Xiaomin Wang, Matthieu Latapy, Michèle Soria

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 of it, and show experimentally (on models and real-world data) that this approach succeeds in making the difference between Poisson and power-law degree distributions.

Xiaomin Wang, Matthieu Latapy, Michèle Soria

Posted in Papers | Also tagged , , , , , |
Plots

Diameter of massive graphs

By admin | Published: February 20, 2009
Diameter of massive graphs

> By Clémence Magnien, Matthieu Latapy and Michel Habib Computing the diameter (i.e. the maximal distance between two nodes) of a huge graph is in many cases too time-consuming to be performed. In Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs we propose several methods to obtain upper and lower bounds […]

Posted in Plots | Also tagged , |
Papers

Main-memory Triangle Computations for Very Large (Sparse (Power-Law)) Graphs

By admin | Published: December 1, 2008
Matthieu Latapy

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 unified 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 finally show with an experimental study that these two algorithms perform very well in practice, allowing to handle cases which were previously out of reach.

Matthieu Latapy

Posted in Papers | Also tagged , |
Papers

Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs

By admin | Published: October 24, 2008
Clémence Magnien, Matthieu Latapy and Michel Habib

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.

Clémence Magnien, Matthieu Latapy and Michel Habib

Posted in Papers | Also tagged , |