Tag Archives: Modelling

Plots

Bias in generated random graphs

Bias in generated random graphs

> By Fabien Viger and Matthieu Latapy One of the main approaches for modelling complex networks is to sample a random graph with prescribed degree distribution; in other words, one chooses a graph uniformly at random (i.e. all graphs have the same probability to be chosen) among all the graphs with a given number N […]

Posted in Plots | Also tagged |
Plots

Profiles of BFS to model internet topology measurements

Profiles of BFS to model internet topology measurements

> By Wang Xiaomin, Matthieu Latapy and Michèle Soria The basic approach to construct a map of the internet as a graph is as follows: one runs the traceroute tool from some machines, called monitors, towards some others, called destinations, and then merges all the obtained paths. The view obtained from each monitor is roughly […]

Posted in Plots | Also tagged , |
Papers

Description and simulation of dynamic mobility networks

Pierre Borgnat, Eric Fleury, Jean-Loup Guillaume, Céline Robardet and Antoine Scherrer

During the last decade, the study of large scale complex networks has attracted a substantial amount of attention and works from several domains: sociology, biology, computer science, epidemiology. Most of such complex networks are inherently dynamic, with new vertices and links appearing while some old ones disappear. Until recently, the dynamic of these networks was less studied and there is a strong need for dynamic network models in order to sustain protocol performance evaluations and fundamental analyzes in all the research domains listed above. We propose in this paper a novel framework for the study of dynamic mobility networks. We address the characterization of dynamics by proposing an in-depth description and analysis of two real-world data sets. We show in particular that links creation and deletion processes are independent of other graph properties and that such networks exhibit a large number of possible configurations, from sparse to dense. From those observations, we propose simple yet very accurate models that allow to generate random mobility graphs with similar temporal behavior as the one observed in experimental data.

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

Describing and simulating routes on the Internet

Jérémie Leguay, Matthieu Latapy, Timur Friedman, Kavé Salamatian

This contribution deals with actual routes followed by packets on the internet at IP level. We first propose a set of statistical properties to analyse such routes, which brings detailed information on them. We then use the obtained results to suggest and evaluate methods for generating artificial routes suitable for simulation purposes. This also makes it possible to evaluate various network models. This work is based on large data sets provided mainly by CAIDA's skitter infrastructure.

Posted in Papers | Also tagged , |
Papers

Bipartite graphs as Models of Complex Networks

Jean-Loup Guillaume and Matthieu Latapy

It appeared recently that the classical random graph model used to represent real-world complex networks does not capture their main properties. Since then, various attempts have been made to provide accurate models. We study here the first model which achieves the following challenges: it produces graphs which have the three main wanted properties (clustering, degree distribution, average distance), it is based on some real-world observations, and it is sufficiently simple to make it possible to prove its main properties. This model consists in sampling a random bipartite graph with prescribed degree distribution. Indeed, we show that any complex network can be viewed as a bipartite graph with some specific characteristics, and that its main properties can be viewed as consequences of this underlying structure. We also propose a growing model based on this observation.

Posted in Papers | Also tagged |
Papers

Clustering in P2P exchanges and consequences on performances

Stevens Le Blond, Jean-Loup Guillaume and Matthieu Latapy

We propose here an analysis of a rich dataset which gives an exhaustive and dynamic view of the exchanges processed in a running eDonkey system. We focus on correlation in term of data exchanged by peers having provided or queried at least one data in common. We introduce a method to capture these correlations (namely the data clustering), and study it in detail. We then use it to propose a very simple and efficient way to group data into clusters and show the impact of this underlying structure on search in typical P2P systems. Finally, we use these results to evaluate the relevance and limitations of a model proposed in a previous publication. We indicate some realistic values for the parameters of this model, and discuss some possible improvements.

Posted in Papers | Also tagged , |
Papers

Random generation of large connected simple graphs with prescribed degree distribution

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.

Posted in Papers | Also tagged , |
Papers

Bipartite Structure of all Complex Networks

Jean-Loup Guillaume and Matthieu Latapy

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.

Posted in Papers | Also tagged |