- Best Papers
Impact of Random Failures and Attacks on Poisson and Power-Law Random Networks
Clémence Magnien, Matthieu Latapy and Jean-Loup Guillaume
To appear in ACM Computing Surveys. Extended abstract published in LNCS, proceedings of the 8-th International Conference On Principles Of Distributed Systems OPODIS'04, 2004, Grenoble, France (title: Comparison of Failures and Attacks on Random and Scale-free Networks).
Abstract It appeared recently that the underlying degree distribution of a network may play a crucial role concerning its robustness. Empiric and analytic results have been obtained, based on asymptotic and mean-field approximations. Previous work insisted on the fact that power-law degree distributions induce a high resilience to random failure but a high sensitivity to some attack strategies, while Poisson degree distributions are quite sensitive in both cases. Then, much work has been done to extend these results.
We focus here on these basic results, with the aim of deepening significantly our understanding of their origin and their limitations. We review in detail previous contributions and we give full proofs in a unified framework, in which the approximations on which these results rely are well identified. We then add to these known results a set of new ones aimed at enlightening some important aspects. We also provide extensive and rigorous experiments which make it possible to evaluate the
relevance of the analytic results.
We reach the conclusion that, even if it is clear that the basic results of the ?eld are true and important, they are in practice much less striking than generally thought. The differences between random failures and attacks are not so huge and can be explained with simple facts. Likewise, the differences in the behaviors induced by power-law and Poisson distributions are not as striking as often claimed.
Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs
Clémence Magnien, Matthieu Latapy and Michel Habib
ACM Journal of Experimental Algorithmics (JEA), 13, 2009.
AbstractThe 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.
A Radar for the Internet
Matthieu Latapy, Clémence Magnien and Frédéric Ouédraogo
Proceedings of ADN'08:
1st International Workshop on Analysis of Dynamic Networks,
in conjonction with IEEE ICDM 2008.
AbstractIn contrast with most internet topology measurement research, our
concern here is not to obtain a map as complete and precise as
possible of the whole internet. Instead, we claim that each
machine's view of this topology, which we call ego-centered view, is
an object worth of study in itself. We design and implement an
ego-centered measurement tool, and perform radar-like measurements
consisting of repeated measurements of such views of the internet topology. We
conduct long-term (several weeks) and high-speed (one round every
few minutes) measurements of this kind from more than one hundred
monitors, and we provide the obtained data. We also show that these
data may be used to detect events in the dynamics of internet topology.
Fast unfolding of communities in large networks
Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre
J. Stat. Mech. (october 2008) P10008.
AbstractWe 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
Complex Network Measurements: Estimating the Relevance of Observed Properties
Matthieu Latapy and Clémence Magnien
Infocom'08 Proceedings, Phoenix, USA.
AbstractComplex networks, modeled as large graphs, received much
attention during these last years. However, data on such networks
is only available through intricate measurement procedures.
Until recently, most studies assumed that these procedures
eventually lead to samples large enough to be representative
of the whole, at least concerning some key properties.
This has crucial impact on network modeling and
simulation, which rely on these properties. Recent contributions proved that this approach may be
misleading, but no solution has been proposed. We provide
here the first practical way to distinguish between cases
where it is indeed misleading, and cases where the observed
properties may be trusted. It consists in studying how the
properties of interest evolve when the sample grows, and in
particular whether they reach a steady state or not. In order to illustrate this method and to demonstrate its
relevance, we apply it to data-sets on complex network measurements
that are representative of the ones commonly used.
The obtained results show that the method fulfills its goals
very well. We moreover identify some properties which
seem easier to evaluate in practice, thus opening interesting
perspectives.
- All Papers (by date)
Optimisation locale multi-niveaux de la modularité
Thomas Aynaud, Vincent Blondel, Jean-Loup Guillaume and Renaud Lambiotte
in Partitionnement de graphe : optimisation et applications, Traité IC2, Hermes-Lavoisier 2011.
AbstractDans 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.
Detecting Events in the Dynamics of Ego-centered Measurements of the Internet Topology
Assia Hamzaoui, Matthieu Latapy and Clémence Magnien
Proceedings of International Workshop on Dynamic Networks (WDN), in conjunction with WiOpt 2010.
AbstractDetecting events such as major routing changes or congestions in the dynamics of the internet topology is an important but challenging task. We explore here a {\em top-down} approach based on a notion of statistically
significant events. It consists in identifying statistics which exhibit a homogeneous distribution with outliers, which correspond to events.
We apply this approach to ego-centerd measurements of the internet topology (views obtained from a single monitor) and show that it succeeds in detecting meaningful events.
Finally, we give some hints for the interpretation of such events in terms of network events.
Static community detection algorithms for evolving networks
Thomas Aynaud and Jean-Loup Guillaume
Proceedings of International Workshop on Dynamic Networks (WDN), in conjunction with WiOpt 2010, pages 508-514.
AbstractComplex networks can often be divided in dense sub-networks called communities. We study, using a partition edit distance, how three community detection algorithms transform their outputs if the input network is sligthly modified. The instabilities appear to be important and we propose a modification of one algorithm to stabilize it and to allow the tracking of the communities in a dynamic network. This modification has one parameter which is a tradeoff between stability and quality. The resulting algorithm appears to be very effective. We finnaly use it on a dynamic network of blogs.
Structure multi-échelle de grands graphes de terrain
Thomas Aynaud and Jean-Loup Guillaume
to appear in Technique et science informatiques.
AbstractMost complex networks can be divided into dense sub-graphs called communities. These communities may also be divided recursively producing a hierarchical structure of communities, summarized in a tree named dendrogram. In this article we analyze this structure extracted from several complex networks. First we study the shape of the tree and, in particular, communities imbrications. Then we show that an excessive decomposition of communities can result in meaningless communities. We propose a couple of approaches to solve this problem.
Evaluation of a New Method for Measuring the Internet Degree Distribution: Simulation Results
Christophe Crespelle and Fabien Tarissan
To appear in Complex Networks, special issue of Computer Communications.
AbstractMany contributions rely on the degree distribution of the Internet topology. However, current knowledge of this property is based on biased and erroneous measurements and is subject to much debate. Recently, a new approach, referred to as the Neighborhood Flooding method, was proposed to avoid issues raised by classical measurements. It aims at measuring the neighborhood of Internet core routers by sending traceroute probes from many monitors distributed in the Internet towards a given target router. In this paper, we investigate the accuracy of this method with simulations. Our results show that Neighborhood Flooding is free from the bias highlighted in the classical approach and is able to observe properly the exact degree of a vast majority of nodes in the core of the network. We show how the quality of the estimation depends on the number of monitors used and we carefully examine the influence of parameters of the simulations on our results. We also point out some limitations of the Neighborhood Flooding method and discuss their impact on the observed distribution.
Impact of Sources and Destinations on the Observed Properties of the Internet Topology
Frédéric Ouédraogo, Clémence Magnien
To appear in Complex Networks, special issue of Computer Communications.
AbstractMaps of the internet topology are generally obtained by measuring the
routes from a given set of sources to a given set of destinations
(with tools such as traceroute). It has been shown that this
approach misses some links and nodes. Worse, in some cases it can
induce a bias in the obtained data, i.e. the properties of
the obtained maps are significantly different from those of the real
topology. In order to reduce this bias, the general approach
consists in increasing the number of sources. Some works have
studied the relevance of this approach. Most of them have used
theoretical results, or simulations on network models. Some papers
have used real data obtained from actual measurement
procedures to
evaluate the importance of the number of sources and
destinations, but no work to our knowledge has studied extensively
the importance of the choice of sources or destinations.
Here, we use real data from internet topology measurements to study this question: by comparing partial measurements to
our complete data, we can evaluate the impact of adding sources or
destinations on the observed properties.
We show that the number of sources and destinations used plays a
role in the observed properties, but that their choice, and not only
their number, also has a strong influence on the observations. We
then study common statistics used to describe the internet topology,
and show that they behave differently: some can be trusted once the
number of sources and destinations are not too small, while others
are difficult to evaluate.
Age, Gender and Communication Networks
Alina Stoica, Zbigniew Smoreda, Christophe Prieur and Jean-Loup Guillaume
Proceedings of the Workshop on the Analysis of Mobile Phone Networks, satellite workshop to NetSci 2010.
Estimating properties in dynamic systems: the case of churn in P2P networks
Lamia Benamara and Clémence Magnien
Proceedings of the Second International Workshop on Network Science for Communication Networks (Netscicom 2010), In Conjuction with IEEE Infocom 2010.
AbstractIn many systems, such as P2P systems, the dynamicity of participating elements, or churn, has a strong impact. As a consequence, many efforts have been made to characterize it, and in particular to capture the session length distribution. However in most cases, estimating it rigorously is difficult. One of the reasons is that, because the observation window is by definition finite, parts of the sessions
that begin before the window and/or end after it are missed. This induces a bias. Although it tends to decrease when the observation window length increases, it is difficult to quantify its importance, or how fast it decreases.
Here, we introduce a general methodology that allows us to know if the observation window is long enough to characterize a given property. This methodology is not specific to one study case and may be applied to any property in a dynamic system. We apply this methodology to the study of session lengths in a massive measurement of P2P activity in the eDonkey system. We show that the measurement needs to last for at least one week in order to obtain representative results. We also show that our methodology allows us to precisely characterize the shape of the session length distribution.
Interactive multiscale visualization of huge graphs: application to a network of weblogs
Massoud Seifi, Jean-loup Guillaume, Matthieu Latapy and Bénédicte Le Grand
Proceedings of the 8th Workshop on Visualization and Knowledge Extraction (EGC 2010).
AbstractDe nombreux réseaux du monde réel peuvent être modélisés par des
grands graphes. Réduire la complexité d'un graphe de manière à ce qu'il puisse
être facilement interprété par l'oeil humain est une aide précieuse pour com-
prendre et analyser ce type de données. Nous proposons une méthodologie de
visualisation interactive multi-échelle de grands graphes basée sur une classification des sommets qui nous permet de représenter ces graphes de manière lisible et interprétable. Nous appliquons notre méthodologie à un réseau de blogs
francophones.
Impact of Random Failures and Attacks on Poisson and Power-Law Random Networks
Clémence Magnien, Matthieu Latapy and Jean-Loup Guillaume
To appear in ACM Computing Surveys. Extended abstract published in LNCS, proceedings of the 8-th International Conference On Principles Of Distributed Systems OPODIS'04, 2004, Grenoble, France (title: Comparison of Failures and Attacks on Random and Scale-free Networks).
Abstract It appeared recently that the underlying degree distribution of a network may play a crucial role concerning its robustness. Empiric and analytic results have been obtained, based on asymptotic and mean-field approximations. Previous work insisted on the fact that power-law degree distributions induce a high resilience to random failure but a high sensitivity to some attack strategies, while Poisson degree distributions are quite sensitive in both cases. Then, much work has been done to extend these results.
We focus here on these basic results, with the aim of deepening significantly our understanding of their origin and their limitations. We review in detail previous contributions and we give full proofs in a unified framework, in which the approximations on which these results rely are well identified. We then add to these known results a set of new ones aimed at enlightening some important aspects. We also provide extensive and rigorous experiments which make it possible to evaluate the
relevance of the analytic results.
We reach the conclusion that, even if it is clear that the basic results of the ?eld are true and important, they are in practice much less striking than generally thought. The differences between random failures and attacks are not so huge and can be explained with simple facts. Likewise, the differences in the behaviors induced by power-law and Poisson distributions are not as striking as often claimed.
Mobile IPv6 Deployments: Graph-based Analysis and practical Guidelines
Guillaume Valadon, Clémence Magnien and Ryuji Wakikawa
Computer Communications, 32, 2009.
AbstractThe Mobile IPv6 protocol is a major solution to supply mobility services on the Internet. Many networking vendors have already implemented it in their operating systems and equipments. Moreover, it was recently selected to provide permanent IP addresses to end users of WiMAX and 3GPP2. Mobile IPv6 relies on a specific router called the home agent that hides location changes of the mobile nodes from the rest of the Internet. To do so, the mobile nodes' traffic must flow through the home agent. This mandatory deviation produces longer paths and higher communication delays.
In order to solve these problems, we describe a new approach to address deployments of Mobile IPv6 based on graph theory and could be applied to any operator's network. In particular, we use notions of centrality in graphs to quantify increases of communication distances induced by dogleg routing and identify relevant home agents locations. We evaluate this approach using real-world network topologies and show that the obtained Mobile IPv6 performance could be close to direct paths ones. The proposed algorithm is generic and can be used to achieve efficient deployments of Mobile IPv6 as well as Home Agent Migration: a new Mobile IPv6 architecture using several distributed home agents.
Efficient Measurement of Complex Networks Using Link Queries
Fabien Tarissan, Matthieu Latapy and Christophe Prieur
In Proceedings of the IEEE International Workshop on Network Science For Communication Networks (NetSciCom'09).
AbstractComplex networks are at the core of an intense research activity. However, in most cases, intricate and costly measurement procedures are needed to explore their structure. In some cases, these measurements rely on link queries: given two nodes, it is possible to test the existence of a link between them. These tests may be costly, and thus minimizing their number while maximizing the number of discovered links is a key issue. This is a challenging task, though, as initially no information is known on the network. This paper studies this problem: we observe that properties classically observed on real-world complex networks give hints for their efficient measurement; we derive simple principles and several measurement strategies based on this, and experimentally evaluate their efficiency on real-world cases. In order to do so, we introduce methods to evaluate the efficiency of strategies. We also explore the bias that different measurement strategies may induce.
Measurement of eDonkey Activity with Distributed Honeypots
Oussama Allali, Matthieu Latapy and Clémence Magnien
Hot-P2P Sixth International Workshop on Hot Topics in Peer-to-Peer Systems (Hot-P2P 2009), May 29, 2009, Rome, Italy.
AbstractCollecting information about user activity in
peer-to-peer systems is a key but challenging task. We describe
here a distributed platform for doing so on the eDonkey
network, relying on a group of honeypot peers which
claim to have certain files and log queries they receive for
these files. We then conduct some measurements with typical
scenarios and use the obtained data to analyze the impact
of key parameters like measurement duration, number
of honeypots involved, and number of advertised files. This
illustrates both the possible uses of our measurement system,
and the kind of data one may collect using it.
Ten weeks in the life of an eDonkey server
Frédéric Aidouni, Matthieu Latapy and Clémence Magnien
Sixth International Workshop on
Hot Topics in Peer-to-Peer Systems (Hot-P2P 2009), May 29, 2009, Rome, Italy.
AbstractCollecting information about user activity in peer-to-peer systems is a key but challenging task. We describe here a distributed platform for doing so on the eDonkey network. It relies on a group of honeypot peers, which claim to have certain files and log queries they receive for these files. We conduct some measurements and analyse the obtained data to illustrate our contribution.
Fast dynamics in Internet topology:
preliminary observations and explanations
Clémence Magnien, Frédéric Ouedraogo, Guillaume Valadon, Matthieu Latapy
Fourth International Conference on Internet Monitoring and Protection (ICIMP 2009), May 24-28, 2009, Venice, Italy.
AbstractBy focusing on what can be observed by running traceroute-like measurements at a high frequency from
a single monitor to a fixed destination set, we show that the
observed view of the topology is constantly evolving at a
pace much higher than expected. Repeated measurements
discover new IP addresses at a constant rate, for long period
of times (up to several months).
In order to provide explanations, we study this phenomenon
both at the IP, and at the Autonomous System levels.
We show that this renewal of IP addresses is partially
caused by a BGP routing dynamics, altering paths between
existing ASes. Furthermore, we conjecture that an intra AS
routing dynamics is another cause of this phenomenon.
Empreintes conceptuelles et spatiales pour la caractérisation des réseaux sociaux
Bénédicte Le Grand, Marie-Aude Aufaure et Michel Soto
Conférence EGC 2009 (Extraction et Gestion des Connaissances), Strasbourg, France, 27-30 janvier 2009.
AbstractIn this paper, Formal Concept Analysis and Galois lattices are used for the analysis of complex datasets, online social networks in particular. Lattice-inspired statistics computed on the objects of the lattice provide their "conceptual distribution". An experimentation conducted on four social networks' samples shows how these statistics may be used to characterize these networks and filter them automatically.
Main-memory Triangle Computations for Very Large (Sparse (Power-Law)) Graphs
Matthieu Latapy
Theoretical Computer Science (TCS) 407 (1-3), pages 458-473, 2008.
Abstract 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 uni?ed 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 ?nally show
with an experimental study that these two algorithms perform very well in practice, allowing to handle
cases which were previously out of reach.
Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs
Clémence Magnien, Matthieu Latapy and Michel Habib
ACM Journal of Experimental Algorithmics (JEA), 13, 2009.
AbstractThe 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.
A Radar for the Internet
Matthieu Latapy, Clémence Magnien and Frédéric Ouédraogo
Proceedings of ADN'08:
1st International Workshop on Analysis of Dynamic Networks,
in conjonction with IEEE ICDM 2008.
AbstractIn contrast with most internet topology measurement research, our
concern here is not to obtain a map as complete and precise as
possible of the whole internet. Instead, we claim that each
machine's view of this topology, which we call ego-centered view, is
an object worth of study in itself. We design and implement an
ego-centered measurement tool, and perform radar-like measurements
consisting of repeated measurements of such views of the internet topology. We
conduct long-term (several weeks) and high-speed (one round every
few minutes) measurements of this kind from more than one hundred
monitors, and we provide the obtained data. We also show that these
data may be used to detect events in the dynamics of internet topology.
Description and simulation of dynamic mobility networks.
Pierre Borgnat, Eric Fleury, Jean-Loup Guillaume, Céline Robardet and Antoine Scherrer
Computer Networks 52 (2008), pp. 2842-2858.
AbstractDuring the last decade, the study of large scale complex networks has attracted asubstantial amount of attention and works from several domains: sociology, biology,computer science, epidemiology. Most of such complex networks are inherently dy-namic, with new vertices and links appearing while some old ones disappear. Untilrecently, the dynamic of these networks was less studied and there is a strong needfor dynamic network models in order to sustain protocol performance evaluationsand fundamental analyzes in all the research domains listed above.We propose in this paper a novel framework for the study of dynamic mobilitynetworks. We address the characterization of dynamics by proposing an in-depthdescription and analysis of two real-world data sets. We show in particular thatlinks creation and deletion processes are independent of other graph properties andthat such networks exhibit a large number of possible con¯gurations, from sparse todense. From those observations, we propose simple yet very accurate models thatallow to generate random mobility graphs with similar temporal behavior as theone observed in experimental data.
Fast unfolding of communities in large networks
Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre
J. Stat. Mech. (october 2008) P10008.
AbstractWe 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
Detection, Understanding, and Prevention of Traceroute Measurement Artifacts
Fabien Viger, Brice Augustin, Xavier Cuvellier, Clémence Magnien, Matthieu Latapy, Timur Friedman, and Renata Teixeira
Computer Networks 52-5 (2008), pp. 998-1018. Extended abstract published in the proceedings of the 6-th Internet Measurement Conference IMC'06, 2006, Rio de Janeiro, Brazil.
AbstractTraceroute is widely used: from the diagnosis of network
problems to the assemblage of internet maps. Unfortu-
nately, there are a number of problems with traceroute
methodology, which lead to the inference of erroneous
routes. This paper studies particular structures arising
in nearly all traceroute measurements. We characterize
them as "loops", "cycles", and "diamonds". We iden-
tify load balancing as a possible cause for the appear-
ance of false loops, cycles and diamonds, i.e., artifacts
that do not represent the internet topology. We pro-
vide a new publicly-available traceroute, called Paris
traceroute, which, by controlling the packet header con-
tents, provides a truer picture of the actual routes that
packets follow. We performed measurements, from the
perspective of a single source tracing towards multiple
destinations, and Paris traceroute allowed us to show
that many of the particular structures we observe are
indeed traceroute measurement artifacts.
Basic Notions for the Analysis of Large Two-mode Networks
Matthieu Latapy, Clémence Magnien and Nathalie Del Vecchio
Social Networks (2008), vol. 30, no1, pp. 31-48.
AbstractMany large real-world networks actually have a 2-mode nature: their nodes may be
separated into two classes, the links being between nodes of different classes only.
Despite this, and despite the fact that many ad-hoc tools have been designed for the study
of special cases, very few exist to analyse (describe, extract relevant information) such
networks in a systematic way. We propose here an extension of the most basic notions
used nowadays to analyse large 1-mode networks (the classical case) to the 2-mode case.
To achieve this, we introduce a set of simple statistics, which we discuss by comparing
their values on a representative set of real-world networks and on their random versions.
This makes it possible to evaluate their relevance in capturing properties of interest in
2-mode networks.
Evolving networks
Pierre Borgnat, Eric Fleury, Jean-Loup Guillaume, Clémence Magnien, Céline Robardet et Antoine Scherrer
Proceedings of NATO Advanced Study Institute on Mining Massive Data Sets for Security, IOS Press, 2008.
AbstractMost real networks often evolve through time: changes of topology can
occur if some nodes and/or edges appear and/or disappear, and the types or weights
of nodes and edges can also change even if the topology stays static. Mobile devices
with wireless capabilities (mobile phones, laptops, etc.) are a typical example
of evolving networks where nodes or users are spread in the environment and
connections between users can only occur if they are near each other. This whois-
near-whom network evolves every time users move and communication services
(such as the spread of any information) will deeply rely on the mobility and on
the characteristics of the underlying network. This paper presents some recent results
concerning the characterization of the dynamics of complex networks through
three different angles: evolution of some parameters on snapshots of the network,
parameters describing the evolution itself, and intermediate approaches consisting
in the study of specific phenomena or users of interest through time.
Complex Network Measurements: Estimating the Relevance of Observed Properties
Matthieu Latapy and Clémence Magnien
Infocom'08 Proceedings, Phoenix, USA.
AbstractComplex networks, modeled as large graphs, received much
attention during these last years. However, data on such networks
is only available through intricate measurement procedures.
Until recently, most studies assumed that these procedures
eventually lead to samples large enough to be representative
of the whole, at least concerning some key properties.
This has crucial impact on network modeling and
simulation, which rely on these properties. Recent contributions proved that this approach may be
misleading, but no solution has been proposed. We provide
here the first practical way to distinguish between cases
where it is indeed misleading, and cases where the observed
properties may be trusted. It consists in studying how the
properties of interest evolve when the sample grows, and in
particular whether they reach a steady state or not. In order to illustrate this method and to demonstrate its
relevance, we apply it to data-sets on complex network measurements
that are representative of the ones commonly used.
The obtained results show that the method fulfills its goals
very well. We moreover identify some properties which
seem easier to evaluate in practice, thus opening interesting
perspectives.
Local leaders in random networks
Vincent D. Blondel, Jean-Loup Guillaume, Julien M. Hendrickx, Cristobald de Kerchove and Renaud Lambiotte
Phys. Rev. E 77, 036114 (2008).
AbstractWe consider local leaders in random uncorrelated networks, i.e., nodes whose degree is higher than or equal to the degree of all their neighbors. An analytical expression is found for the probability for a node of degree k to be a local leader. This quantity is shown to exhibit a transition from a situation where high-degree nodes are local leaders to a situation where they are not, when the tail of the degree distribution behaves like the power law ~k?c with c=3. Theoretical results are verified by computer simulations, and the importance of finite-size effects is discussed.
Describing and simulating routes on the Internet
Jérémie Leguay, Matthieu Latapy, Timur Friedman, Kavé Salamatian
Computer Networks 51, pages 2067-2087, 2007. Extended abstract published in LNCS, proceedings of the 4-th IFIP international conference on Networking, 2005, Waterloo, Canada.
AbstractThis 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.
Multi-level analysis of an interaction network between individuals in a mailing-list
Rémi Dorat, Matthieu Latapy, Bernard Conein and Nicolas Auray
Annals of Telecommunications (2007), vol. 62, no3-4, pp. 325-349 .
AbstractIt is well known now that most real-world complex networks have some properties
which make them very different from random networks. In the case of interactions
between authors of messages in a mailing-list, however, a multi-level structure may
be responsible for some of these properties. We propose here a rigorous but simple
formalism to investigate this question, and we apply it to an archive of the Debian user
mailing-list. This leads to the identification of some properties which may indeed be
explained this way, and of some properties which need deeper analysis.
Distance distribution in random graphs and application to network exploration
Vincent D. Blondel, Jean-Loup Guillaume, Julien M. Hendrickx, and Raphaël M. Jungers
Phys. Rev. E 76, 066101 (2007).
AbstractWe consider the problem of determining the proportion of edges that are discovered in an Erdös-Rényi graph when one constructs all shortest paths from a given source node to all other nodes. This problem is equivalent to the one of determining the proportion of edges connecting nodes that are at identical distance from the source node. The evolution of this quantity with the probability of existence of the edges exhibits intriguing oscillatory behavior. In order to perform our analysis, we introduce a different way of computing the distribution of distances between nodes. Our method outperforms previous similar analyses and leads to estimates that coincide remarkably well with numerical simulations. It allows us to characterize the phase transitions appearing when the connectivity probability varies.
Theoretical Computer Science special issue on Complex Networks - foreword
Ravi Kumar and Matthieu Latapy
Theoretical Computer Science, special issue on Complex Networks, Volume 355, Number 1, 6 April 2006.
Computing communities in large networks using random walks
Pascal Pons and Matthieu Latapy
Journal of Graph Algorithms and Applications (JGAA) vol. 10, no. 2, pages 191-218, 2006. Extended abstract published in LNCS, proceedings of the 20-th International Symposium on Computer and Information Sciences ISCIS'05, 2005, Istambul, Turquie.
AbstractDense subgraphs of sparse graphs (communities), which appear in most real-world complex
networks, play an important role in many contexts. Computing them however is generally expen-
sive. We propose here a measure of similarities between vertices based on random walks which
has several important advantages: it captures well the community structure in a network, it can
be computed e±ciently, and it can be used in an agglomerative algorithm to compute e±ciently
the community structure of a network. We propose such an algorithm, called Walktrap, which
runs in time O(mn²) and space O(n²) in the worst case, and in time O(n² log n) and space O(n²)
in most real-world cases (n and m are respectively the number of vertices and edges in the input
graph). Extensive comparison tests show that our algorithm surpasses previously proposed ones
concerning the quality of the obtained community structures and that it stands among the best
ones concerning the running time.
Dynamics of three-state excitable units on Poisson vs power-law random networks
Anne-Ruxandra Carvunis, Matthieu Latapy, Annick Lesne, Clémence Magnien and Laurent Pezard
Physica A 367, pages 585-612, 2006.
AbstractThe influence of the network topology on the dynamics of systems of coupled excitable
units is studied numerically and demonstrates a lower dynamical variability
for power-law networks than for Poisson ones. This effect which reflects a robust
collective excitable behavior is however lower than that observed for diffusion processes
or network robustness.Instead, the presence (and number) of triangles and
larger loops in the networks appears as a parameter with strong in
uence on the
considered dynamics.
Bipartite graphs as Models of Complex Networks
Jean-Loup Guillaume and Matthieu Latapy
Physica A 371, pages 795-813, 2006. Extended abstract published in LNCS, proceedings of the 1-st international workshop on Combinatorial and Algorithmic Aspects of Networking CAAN'04, 2004, Banff, Canada.
AbstractIt 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.
Random generation of large connected simple graphs with prescribed degree distribution
Fabien Viger and Matthieu Latapy
Submitted. Extended abstract published in LNCS, proceedings of the 11-th international conference on Computing and Combinatorics COCOON'05, 2005, Kunming, Yunnan, Chine.
AbstractWe 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.
Relevance of Massively Distributed Explorations of the Internet Topology: Qualitative Results
Jean-Loup Guillaume, Matthieu Latapy and Damien Magoni
Computer Networks 50, pages 3197-3224, 2006. Extended abstract published in the proceedings of the 24-th IEEE international conference Infocom'05, 2005, Miami, USA.
AbstractInternet maps are generally constructed using
the traceroute tool from a few sources to many destinations.
It appeared recently that this exploration process
gives a partial and biased view of the real topology, which
leads to the idea of increasing the number of sources to improve
the quality of the maps. In this paper, we present a set
of experiments we have conducted to evaluate the relevance
of this approach. It appears that the statistical properties
of the underlying network have a strong influence on the
quality of the obtained maps, which can be improved using
massively distributed explorations. Conversely, some statistical
properties are very robust, and so the known values
for the Internet may be considered as reliable. We validate
our analysis using real-world data and experiments, and we
discuss its implications.
Complex Network Metrology
Jean-Loup Guillaume and Matthieu Latapy
Complex Systems 16, pages 83-94, 2005.
AbstractIn order to study some complex networks like the Internet, the Web, social networks or biological networks, one first has to explore them. This gives a partial
and biased view of the real object, which is generally assumed to be representative
of the whole. However, up to now nobody knows how and how much the measure
influences the results.
Using the example of the Internet and a rough model of its exploration process,
we show that the way a given complex network is explored may strongly influence
the observed properties. This leads us to argue for the necessity of developing a
science of metrology of complex networks. Its aim would be to study how the partial
and biased view of a network relates to the properties of the whole network.
Combining the use of clustering and scale-free nature of user exchanges into a simple and efficient P2P system
Pierre Fraigniaud, Philippe Gauron and Matthieu Latapy
LNCS, proceedings of the 11-th international conference Euro-Par, 2005, Lisbonne, Portugal.
AbstractIt appeared recently that user interests in a P2P system
possess clustering properties that may be used to
reduce significantly the amount of traffic of floodingbased
search strategies. It was also observed that
they possess scale-free properties that may be used
for the design of efficient routing-based search strategies.
In this paper, we show that the combination of
these two properties make it possible to design an efficient
and simple fully decentralized search strategy.
Further, simulations processed on real-world traces
show that other unidentified properties hidden in actual
queries make our protocol even more efficient,
performing searches in logarithmic expected number
of steps.
Clustering in P2P exchanges and consequences on performances
Stevens Le Blond, Jean-Loup Guillaume and Matthieu Latapy
LNCS, proceedings of the 4-th International workshop on Peer-to-Peer Systems IPTPS'05, 2005, Ithaka, New York, USA.
AbstractWe 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.
Bipartite Structure of all Complex Networks
Jean-Loup Guillaume and Matthieu Latapy
Information Processing Letters (IPL) 90:5, pages 215-221, 2004.
AbstractThe 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.
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.
AbstractDespite 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.
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ï.
