By admin | Published: January 1, 2011
Thomas Aynaud, Vincent Blondel, Jean-Loup Guillaume and Renaud Lambiotte
Dans ce chapitre, nous présentons une méthode gloutonne pour optimiser la modularité d'un graphe. Cette méthode de partionnement permet de traiter avec une excellente précision des systèmes de taille inégalée, allant jusqu'à plusieurs milliards de liens. Notre algorithme a de surcroît l'avantage de ne pas être limité à l'optimisation de la modularité puisqu'il peut être généralisé à d'autres fonctions de qualité, et de découvrir des communautés à différentes échelles. Les performances de l'algorithme sont évaluées sur des graphes artificiels pour lesquels la structure communautaire est connue, ainsi que sur des graphes de terrain réels.
Posted in Papers | Also tagged communities, modularity
By admin | Published: February 20, 2009
> 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 diameter, graph
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.
Posted in Papers | Also tagged graph, triangles
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.
Posted in Papers | Also tagged diameter, graph
By admin | Published: October 23, 2008
Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre
We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known community detection method in terms of computation time. Moreover, the quality of the communities detected is very good, as measured by the so-called modularity. This is shown first by identifying language communities in a Belgian mobile phone network of 2.6 million customers and by analyzing a web graph of 118 million nodes and more than one billion links. The accuracy of our algorithm is also verified on ad-hoc modular networks
Posted in Papers | Also tagged communities
By admin | Published: January 1, 2005
Fabien Viger and Matthieu Latapy
We address here the problem of generating random graphs uniformly from the set of simple connected graphs having a prescribed degree sequence. Our goal is to provide an algorithm suitable for practical use both because of its ability to generate very large graphs (efficiency) and because it is easy to implement (simplicity).
We focus on a family of heuristics for which we introduce optimality conditions, and show how this optimality can be reached in practice. We then propose a different approach, specifically designed for real-world degree distributions, which outperforms the first one. Based on a conjecture which we discuss rigorously and study empirically, we finally reduce the best asymptotic complexity bound known so far.
