↓

Random generation of large connected simple graphs with prescribed degree distribution

Fabien Viger and Matthieu Latapy

Extended abstract published in LNCS, proceedings of the 11-th international conference on Computing and Combinatorics COCOON’05, 2005, Kunming, Yunnan, Chine

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.

Download

Statistical analysis of a P2P query graph based on degrees and their time-evolution

Jean-Loup Guillaume, Matthieu Latapy and Stevens Le-Blond

LNCS, proceedings of the 6-th International Workshop on Distributed Computing IWDC’04, 2004, Kolkata, India

Despite their crucial impact on the performances of P2P systems, very few is known on peers behaviors in such networks. We propose here a study of these behaviors in a running environment using a semicentralised P2P system (eDonkey). To achieve this, we use a trace of the queries made to a large server managing up to fifty thousands peers simultaneously, and a few thousands queries per second. We analyse these data using complex network methods, and focus in particular on the degrees, their correlations, and their time-evolution. Results show a large variety of observed phenomena, including the variety of peers behaviors and heterogeneity of data queries, which should be taken into account when designing P2P systems.

Download

Bipartite Structure of all Complex Networks

Jean-Loup Guillaume and Matthieu Latapy

Information Processing Letters (IPL) 90:5, pages 215-221, 2004

The analysis and modelling of various complex networks has received much attention in the last few years. Some such networks display a natural bipartite structure: two kinds of nodes coexist with links only between nodes of different kinds. This bipartite structure has not been deeply studied until now, mainly because it appeared to be specific to only a few complex networks. However, we show here that all complex networks can be viewed as bipartite structures sharing some important statistics, like degree distributions. The basic properties of complex networks can be viewed as consequences of this underlying bipartite structure. This leads us to propose the first simple and intuitive model for complex networks which captures the main properties met in practice.

Download

Efficient and Simple Encodings for the Web Graph

Jean-Loup Guillaume, Matthieu Latapy and Laurent Viennot

LNCS, proceedings of the 3-rd international conference Web-Age Information Management WAIM’02, 2002, Beijing, Chine. Abstract published in the proceedings of the 11-th international conference World Wide Web WWW’02, 2002, Honolulu, Hawaï

In this paper, we propose a set of simple and efficient methods based on standard, free and widely available tools, to store and manipulate large sets of URLs and large parts of the Web graph. Our aim is both to store efficiently the URLs list and the graph in order to manage all the computations in a computer central memory. We also want to make the conversion between URLs and their identifiers as fast as possible, and to obtain all the successors of an URL in the Web graph efficiently. The methods we propose make it possible to obtain a good compromise between these two challenges, and make it possible to manipulate large parts of the Web graph.

Download

↑