• 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).
Abstract
Complex 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.
Abstract
Collecting 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.
Abstract
Collecting 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.
Abstract
By 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.
Abstract
In 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.

>>> All Papers