Papers – Page 7 – Complex Networks

↓

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

In Journal of Social Network Analysis and Mining, 3(4):1195-1208,Springer, 2013.

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.

Download

On the relevance of the edge-Markovian evolving graph model for real mobile networks

Aurélie Faure de Pebeyre, Fabien Tarissan et Julien Sopena

IFIP Wireless Days conference (WD’13), Valencia, Spain, 2013

The development of wireless devices led the scientific community to focus more and more on systems of interaction composed of moving entities. In this context, different models have been proposed in an attempt to capture properties of the observed dynamics. Among those models, the edge-Markovian evolving graph model is appealing since it enables to highlight temporal dependencies in the evolution of the graphs. This model relies on two parameters accounting respectively for the creation and suppression of links in the graph. Thus it assumes that these two parameters are sufficient to characterise the dynamics during all the evolution of the graph. In this paper, we test this hypothesis by confronting the model to 6 datasets recording real traces of evolving networks. In particular, we study the proportion of created and deleted links over the time. The results show that 5 of the 6 case studies present an heterogeneous distribution of those fractions which contradicts the underlying hypothesis of the model. Besides, in order to understand the importance this might have as regard structural properties of real networks, we also study the impact the Markovian model has on the mean degree over the time. It turns out that even in the suitable case, the model fails to reproduce correctly this property which indicates its inadequacy for even more complex properties of real evolving networks

Download

Method of reliability and availability analysis – From the dynamic properties of routing and forwarding paths

Dimitri Papadimitriou, Davide Careglio, Fabien Tarissan and Piet Demeester

Proceedings of the International Workshop on Reliable Networks Design and Modeling (RNDM’13), 2013 (Invited paper)

Confronted to the increasing dynamic of Internet routing system and its underlying topology, we propose a reliability and availability analysis method based on the characterization of the dynamic properties (in particular, the stability properties) of routing paths and their corresponding forwarding paths. The key driver underlying this method is that transient but frequent changes in the spatio-temporal properties of routing paths can affect the performance and operating conditions of the corresponding forwarding paths; hence, their reliability. The results obtained by means of this method verify that, although the main cause of instability results from the forwarding plane dynamics, a second order effect relates forwarding and routing path instability events. Applying our analysis method reveals that the dominant source (main cause) of instability originates indeed from the forwarding plane. This result which confirms previous studies from 2003 further corroborates the assumption that the dynamic properties of routing system are mainly driven by its adaptation to the forwarding system (adaptive routing). However, even if the likelihood of forwarding instability becomes the prominent behavior (cause), about 50% of them induce routing path instability whereas the corresponding forwarding path remains unstable. This observation suggests that 50% of the reactive decisions performed by the BGP routing system (reactive routing) tend to further delay convergence of the forwarding paths. In turn, this observation provides the first indication that simple causal effects can’t explain anymore the occurrence of instability. Moreover, more elaborated analysis techniques (such as the one proposed in this paper) are required to explain the inter-dependent routing and forwarding paths dynamics which affects their reliability and availability.

Download

Un modèle pour les graphes bipartis aléatoires avec redondance

Émilie Coupechoux and Fabien Tarissan

4ème Journées Modèles et l’Analyse des Réseaux : Approches Mathématiques et Informatique (MARAMI’13), 2013

Current models of random graphs do not capture all the properties observed in realworld networks. In particular, two cliques in such models generally do not have more than one node in common, while it is intuitive that, in social networks for instance, two friends have more than one interest in common. The model presented here aims at capturing this kind of property. More precisely, we present a model for random tripartite graphs such that the bipartite projection has degree and redundancy distributions close to those of a given bipartite graph.

Download

valuation du modèle évolutif par arête-markovienne pour reproduire la dynamique des réseaux mobiles

Aurélie Faure de Pebeyre, Fabien Tarissan and Julien Sopena

In 4ème Journées Modèles et l’Analyse des Réseaux : Approches Mathématiques et Informatique (MARAMI’13), 2013

L’avènement des équipements mobiles a amené la communauté scientifique à étudier plus intensément les systèmes d’interactions formés par des entités en mouvement. Dans ce contexte, plusieurs modèles ont été proposés pour tenter de capturer les propriétés dynamiques de tels systèmes. Parmi ceux-ci, le modèle de graphes évolutifs à arêtes markoviennes est attirant en ce qu’il met en avant les dépendances temporelles dans un graphe dynamique. Ce modèle repose sur l’identification de deux paramètres régissant respectivement l’apparition et la disparition des liens dans le graphe et fait donc l’hypothèse que ces deux paramètres sont suffisants pour caractériser cette dynamique sur l’ensemble de la durée de vie du graphe. Dans cet article nous testons la pertinence de cette hypothèse par rapport à 6 jeux de données réelles. Pour se faire, nous avons étudié la fraction de liens créés et supprimés au cours du temps. Les résultats montrent que dans 5 cas sur les 6 étudiés, la répartition de ces fractions est hétérogène, ce qui contredit l’hypothèse faite par le modèle. De plus, nous avons regardé l’impact que le modèle markovien avait sur le degré moyen des nœuds au cours du temps. Il s’avère que même dans le jeu de données favorable au modèle, ce dernier échoue à rendre compte du comportement des réseaux dynamiques de façon satisfaisante.

Download

The Power of Consensus: Random Graphs Have No Communities

Romain Campigotto, Jean-Loup Guillaume and Massoud Seifi

Proceedings of the 5th IEEE/ACM International Conference on Advances in Social Networks and Mining (ASONAM 2013). Niagara Falls, Canada.

Communities are a powerful tool to describe the structure of complex networks. Algorithms aiming at maximizing a quality function called modularity have been shown to effectively compute the community structure. However, some problems remain: in particular, it is possible to find high modularity partitions in graph without any community structure, in particular random graphs. In this paper, we study the notion of consensual communities and show that they do not exist in random graphs. For that, we exhibit a phase transition based on the strength of consensus: below a given threshold, all the nodes belongs to the same consensual community; above this threshold, each node is in its own consensual community.

Download

Towards realistic modeling of IP-level routing topology dynamics

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

Networking Science, 4 (1-4), p. 24-33, 2013

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.

Download

The network of the International Criminal Court decisions as a complex system

Fabien Tarissan and Raphaëlle Nollez-Goldbach

ISCS 2013: Interdisciplinary Symposium on Complex Systems, Emergence, Complexity and Computation, 8:225-264, Springer, 2013.

Many real-world networks lend themselves to the use of graphs for analysing and modeling their structure. This approach has proved to be very useful for a wide variety of networks stemming from very different fields. Yet, only few papers focused their attention on legal networks. This paper intends precisely to remedy this situation by analysing a major legal network by means of complex system methods. The network under investigation is the network composed by decisions taken by the International Criminal Court since its creation. We first model the network by a simple directed graph in which nodes are the decisions and links represent citations between decisions. Our analysis shows that standard properties shared by common real networks are also present in this network. Then we turn to studying the network by means of bipartite graphs that involve both decisions and articles of law. We show that this two-level structure presents several non trivial properties and we show evidences of the relevance of the bipartite representation to explain properties observed in the graph of citations.

Download

A Matter of Time – Intrinsic or Extrinsic – for Diffusion in Evolving Complex Networks

Alice Albano, Jean-Loup Guillaume, Sébastien Heymann and Bénédicte Le Grand

Proceedings of the 2013 IEEE/ACM International Conference on Advances n Social Networks Analysis and Mining (ASONAM 2013), Niagara Falls, Canada

Diffusion phenomena occur in many kinds of real-world complex networks, e.g., biological, information or social networks. Because of this diversity, several types of diffusion models have been proposed in the literature: epidemiological models, threshold models, innovation adoption models, among others. Many studies aim at investigating diffusion as an evolving phenomenon but mostly occurring on static networks, and much remains to be done to understand diffusion on evolving networks. In order to study the impact of graph dynamics on diffusion, we propose in this paper an innovative approach based on a notion of intrinsic time, where the time unit corresponds to the appearance of a new link in the graph. This original notion of time allows us to isolate somehow the diffusion phenomenon from the evolution of the network. The objective is to compare the diffusion features observed with this intrinsic time concept from those obtained with traditional (extrinsic) time, based on seconds. The comparison of these time concepts is easily understandable yet completely new in the study of diffusion phenomena. We experiment our approach on synthetic graphs, as well as on a dataset extracted from the Github sofware sharing platform.

Download

Towards a Bipartite Graph Modeling of the Internet Topology

Fabien Tarissan, Bruno Quoitin, Pascal Mérindol, Benoit Donnet, Matthieu Latapy et Jean-Jacques Pansiot

In Journal of Computer Networks, 57(11):2331-2347, Elsevier, 2013.

Modeling the properties of the Internet topology aims at generating large scale artificial IP networks that mimic properties of real ones for simulation purposes. Current models typ- ically consider the Internet as a simple graph where edges are point-to-point connections between routers. This approach does not take into account point-to-multipoint connec- tions that exist at lower layers in the network, e.g. layer-2 clouds, such as Ethernet switches or MPLS networks. Instead, such physical point-to-multipoint connections are modeled as several logical IP level point-to-point connections. In this paper, we rely on recent developments in topology discovery based on IGMP probing that allows for revealing part of the network’s layer-2 structure. We take advantage of this additional knowledge for proposing an Internet model based on bipartite graphs considering both point-to-point and point-to-multipoint connections. Our model remains simple: it only takes as input the node degree sequence for both layer-2 and layer-3 nodes, randomly generates a bipartite graph respecting those distri- butions, and then derives the corresponding layer-3 topology. We show that, despite the simplicity of our model, realistic network properties, such as high local density, emerge naturally. This is in contrast with the now common belief that such properties can only appear with more intricate models or if explicitly injected in random models. Besides, we also provide evidences of how the analysis performed at the bipartite level might shed light on important properties of the real network structure. Finally, we propose and evaluate a bipartite graph generator based on our model that only takes two synthetic node degree distributions as input.

Download

Internet routing paths stability model and relation to forwarding paths

Dimitri Papadimitriou, Davide Careglio, Fabien Tarissan and Piet Demeester

Proceedings of the the 9th International Conference on Design of Reliable Communication Networks (DRCN), Budapest, Hungary, 2013

Analysis of real datasets to characterize the local stability properties of the Internet routing paths suggests that extending the route selection criteria to account for such property would not increase the routing path length. Nevertheless, even if selecting a more stable routing path could be considered as valuable from a routing perspective, it does not necessarily imply that the associated forwarding path would be more stable. Hence, if the dynamics of the Internet routing and forwarding system show different properties, then one can not straightforwardly derive the one from the other. If this assumption is verified, then the relationship between the stability of the forwarding path (followed by the traffic) and the corresponding routing path as selected by the path-vector routing algorithm requires further characterization. For this purpose, we locally relate, i.e., at the router level, the stability properties of routing path with the corresponding forwarding path. The proposed stability model and measurement results verify this assumption and show that, although the main cause of instability results from the forwarding plane, a second order effect relates forwarding and routing path instability events. This observation provides the first indication that differential stability can safely be taken into account as part of the route selection process.

Download

Temporal Reachability Graphs

J. Whitbeck and M. Dias de Amorim and V. Conan and J.-L. Guillaume

The 18th Annual International Conference on Mobile Computing and Networking, Mobicom’12, pp. 377-388

While a natural fit for modeling and understanding mobile networks, time-varying graphs remain poorly understood. Indeed, many of the usual concepts of static graphs have no obvious counterpart in time-varying ones. In this paper, we introduce the notion of temporal reachability graphs. A (tau, sigma)-reachability graph is a time-varying directed graph derived from an existing connectivity graph. An edge exists from one node to another in the reachability graph at time t if there exists a journey (i.e., a spatiotemporal path) in the connectivity graph from the first node to the second, leaving after t, with a positive edge traversal time tau, and arriving within a maximum delay sigma. We make three contributions. First, we develop the theoretical framework around temporal reachability graphs. Second, we harness our theoretical findings to propose an algorithm for their efficient computation. Finally, we demonstrate the analytic power of the temporal reachability graph concept by applying it to synthetic and real-life data sets. On top of defining clear upper bounds on communication capabilities, reachability graphs highlight asymmetric communication opportunities and offloading potential.

Download

Towards multi-ego-centered communities: a node similarity approach

M. Danisch, J.-L. Guillaume and B. Le Grand

Int. J. of Web Based Communities, Vol. 9, No. 3, pp. 299-322, 2012

The community structure of a graph is defined in various ways in the literature: (i) Partition, where nodes can belong to only one community. This vision is unrealistic and may lead to poor results because most nodes belong to several communities in real-world networks. (ii) Overlapping community structure, which is the most natural view, but is often very difficult to identify in practice due to the complex structure of real-world networks, and the huge number of such possible communities. (iii) Ego-centered community which focuses on individual nodes’ communities and seems to be a good compromise. In this paper we investigate the third vision; we propose a new similarity measure between nodes based on opinion dynamics to unfold ego-centered communities. We call it the carryover opinion. In addition to be parameter-free, the carryover opinion can be calculated in a very time-efficient way and can thus be used in huge graphs. We also go further in the idea of ego-centered communities by introducing the new concept of multi-ego-centered communities, i.e., focusing on the communities of a set of nodes rather than of a single node. A key idea is that, although one node generally belongs to numerous communities, a small set of appropriate nodes can fully characterize a single community.

Download

Diffusion Cascades: Spreading Phenomena in Blog Network Communities

Abdelhamid Salah Brahim, Bénédicte Le Grand and Matthieu Latapy

Parallel Processing Letters 22(1): (2012)

A diffusion cascade occurs when information spreads from one node to the rest of the network through a succession of diffusion events. So far diffusion phenomena have been mostly considered at a macroscopic scale i.e. by studying all nodes of the network. We give a complementary way to analyse network interactions by considering the problem at different scales. To that purpose, we use the community structure of the network to characterize diffusion between nodes (and between communities) and to identify interactions behaviour patterns.

Download

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

Xiaomin Wang, Matthieu Latapy, Michèle Soria

International Journal of Computer Networks & Communications (IJCNC), May 2012, Volume 4. Number 3

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.

Download

Relevance of SIR Model for Real-world Spreading Phenomena: Experiments on a Large-scale P2P System

Daniel F. Bernardes, Matthieu Latapy, Fabien Tarissan

Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012), Istanbul, Turkey

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 also perform simulations to assess the relevance of the standard SIR model to mimic key properties of spreading cascade. We examine the impact of the network topology on observed properties and finally turn to the evaluation of two heterogeneous versions of the SIR model. We conclude that all the models tested failed to reproduce key properties of such cascades: typically real spreading cascades are relatively “elongated” compared to simulated ones. We have also observed some interesting similarities common to all SIR models tested.

Download

Outskewer: Using Skewness to Spot Outliers in Samples and Time Series

Sébastien Heymann, Matthieu Latapy, Clémence Magnien

Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2012), Istanbul, Turkey

Finding outliers in datasets is a classical problem of high interest for (dynamic) social network analysis. However, most methods rely on assumptions which are rarely met in practice, such as prior knowledge of some outliers or about normal behavior. We propose here Outskewer, a new approach based on the notion of skewness (a measure of the symmetry of a distribution) and its evolution when extremal values are removed one by one. Our method is easy to set up, it requires no prior knowledge on the system, and it may be used on-line. We illustrate its performance on two data sets representative of many use-cases: evolution of ego-centered views of the internet topology, and logs of queries entered into a search engine.

Download

How to detect causality effects on large dynamical communication networks: A case study

Tabourier, L. and Stoica, A. and Peruani, F.

Communication Systems and Networks (COMSNETS), 2012 Fourth International Conference on

Here we propose a set of dynamical measures to detect causality effects on communication datasets. Using appropriate comparison models, we are able to enumerate patterns containing causality relationships. This approach is illustrated on a large cellphone call dataset: we show that specific patterns such as short chain-like trees and directed loops are more frequent in real networks than in comparison models at short time scales. We argue that these patterns – which involve a node and its close neighborhood – constitute indirect evidence of active spreading of information only at a local level. This suggests that mobile phone networks are used almost exclusively to communicate information to a closed group of individuals. Furthermore, our study reveals that the bursty activity of the callers promotes larger patterns at small time scales.

Download

Stable community cores in complex networks

Massoud Seifi, Jean-Loup Guillaume, Ivan Junier, Jean-Baptiste Rouquier and Svilen Iskrov

Proceedings of the 3rd Workshop on Complex Networks (CompleNet 2012), Melbourne, Florida

Complex networks are generally composed of dense sub-networks called communities. Many algorithms have been proposed to automatically detect such communities. However, they are often unstable and behave non-deterministically. We propose here to use this non-determinism in order to compute groups of nodes on which community detection algorithms agree most of the time.We show that these groups of nodes, called community cores, are more similar to Ground Truth than communities in real and artificial networks. Furthermore, we show that in contrary to the classical approaches, we can reveal the absence of community structure in random graphs.

Download

↑