Tag Archives: Topology

Papers

Inadequacy of SIR Model to Reproduce Key Properties of Real-world Spreading Phenomena: Experiments on a Large-scale P2P System

Daniel Bernardes, Matthieu Latapy, Fabien Tarissan

Understanding the spread of information on complex networks is a key issue from a theoretical and applied perspective. Despite the effort in developing theoretical models for this phenomenon, gauging them with large-scale real-world data remains an important challenge due to the scarcity of open, extensive and detailed data. In this paper, we explain how traces of peer-to-peer file sharing may be used to this goal. We reconstruct the underlying social network of peers sharing content and perform simulations on it to assess the relevance of the standard SIR model to mimic key properties of real spreading cascades. First we examine the impact of the network topology on observed properties. Then we turn to the evaluation of two heterogeneous extensions of the SIR model. Finally we improve the social network reconstruction, introducing an affinity index between peers, and simulate a SIR model which integrates this new feature. We conclude that the simple, homogeneous model is insufficient to mimic real spreading cascades. Moreover, none of the natural extensions of the model we considered, which take into account extra topological properties, yielded satisfying results in our context. This raises an alert against the careless, widespread use of this model.

Posted in Papers | Also tagged , , |
Papers

Towards realistic modeling of IP-level routing topology dynamics

Clémence Magnien, Amélie Medem, Sergey Kirgizov, Fabien Tarissan

Many works have studied the Internet topology, but few have investigated the question of how it evolves over time. This paper focuses on the Internet routing IP-level topology and proposes a first step towards realistic modeling of its dynamics. We study periodic measurements of routing trees from a single monitor to a fixed destination set and identify invariant properties of its dynamics. Based on those observations, we then propose a model for the underlying mechanisms of the topology dynamics. Our model remains simple as it only incorporates load-balancing phenomena and routing changes. By extensive simulations,  we show that, despite its simplicity, this model effectively captures the observed behaviors, thus providing key insights of relevant mechanisms governing the Internet routing dynamics. Besides, by confronting simulations over different kinds of topology, we also provide insights of which structural properties play a key role to explain the properties of the observed dynamics, which therefore strengthens the relevance of our model.

Posted in Papers | Also tagged , , |
Papers

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

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.
Posted in Papers | Also tagged , , , , , |