637 research outputs found
Measured impact of crooked traceroute
No full textData collected using traceroute-based algorithms underpins research into the Internet’s router-level topology, though it is possible to infer false links from this data. One source of false inference is the combination of per-flow load-balancing, in which more than one path is active from a given source to destination, and classic traceroute, which varies the UDP destination port number or ICMP checksum of successive probe packets, which can cause per-flow load-balancers to treat successive packets as distinct flows and forward them along different paths. Consequently, successive probe packets can solicit responses from unconnected routers, leading to the inference of false links. This paper examines the inaccuracies induced from such false inferences, both on macroscopic and ISP topology mapping. We collected macroscopic topology data to 365k destinations, with techniques that both do and do not try to capture load balancing phenomena.We then use alias resolution techniques to infer if a measurement artifact of classic traceroute induces a false router-level link. This technique detected that 2.71% and 0.76% of the links in our UDP and ICMP graphs were falsely inferred due to the presence of load-balancing. We conclude that most per-flow load-balancing does not induce false links when macroscopic topology is inferred using classic traceroute. The effect of false links on ISP topology mapping is possibly much worse, because the degrees of a tier-1 ISP’s routers derived from classic traceroute were inflated by a median factor of 2.9 as compared to those inferred with Paris traceroute
Relevance of Massively Distributed Explorations of the Internet Topology: Qualitative Results
No full text20 pages extended version of "Guillaume, Latapy - Relevance of Massively Distributed Explorations of the Internet Topology: Simulation Results - Infocom 2005"International audienceInternet 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 tatistical 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
Social Network Analysis of Developers' and Users' Mailing Lists of Some Free Open Source Software
No full textInternational audienceAs reported by Kevin Crowston and co-authors in a recent paper, free open source software is a very important social phenomenon that involves nearly one million programmers, a myriad of software development firms, millions of users, and its financial impact is huge since for instance the cost of recreating available free software is estimated in tens of billions of euros. Free open source software projects generally have one mailing list for developers and another one for users. This large number of mailing lists changes constantly and shows a great variety with respect to membership and topics covered. This makes them very difficult to monitor. One way of overcoming this Big Data Challenge is to identify some easily computable global indicators that can be used for instance to detect important events. We illustrate this approach here by making a social network analysis and comparison of developers' and users' mailing lists of four free open source software projects: CentOS, GnuPG, Mailman and Samba. We show that these mailing lists have some common characteristics : the number of messages, the time durations and the interlink times can be fitted using power and lognormal laws with suitable scales and parameters ; for the interlink time, the analysis is done using the temporal delta density inspired by the delta density introduced by Viard and Latapy. This similarity between the characteristics of mailing lists also applies to the structure of dominant groups. For the time evolution of the number of messages, GnuPG exhibits a particular behavior. The interpretation of the different parameters gives very interesting insights into the membership and the type of topics covered by the mailing lists. The analysis carried out here and similar studies cited in this paper can therefore be considered as a first step towards the designing of building blocks for monitoring mailing lists
Partitions of an Integer into Powers
No full textInternational audienceIn this paper, we use a simple discrete dynamical model to study partitions of integers into powers of another integer. We extend and generalize some known results about their enumeration and counting, and we give new structural results. In particular, we show that the set of these partitions can be ordered in a natural way which gives the distributive lattice structure to this set. We also give a tree structure which allow efficient and simple enumeration of the partitions of an integer
Integer partitions, tilings of -gons and lattices
No full textIn this paper, we study two kinds of combinatorial
objects, generalized integer partitions and tilings of 2D-gons
(hexagons, octagons, decagons, etc.).
We show that the sets of partitions,
ordered with a simple dynamics, have the distributive lattice structure.
Likewise, we show that the set of tilings of a 2D-gon
is the disjoint union of distributive
lattices which we describe.
We also discuss the special case of linear integer
partitions, for which other dynamical models exist
Groups and communities in link streams : from data to algorithms
No full textLes interactions sont partout : il peut s'agir de contacts entre individus, d'emails, d'appels téléphoniques, etc. Toutes ces interactions sont définies par deux entités interagissant sur un intervalle de temps: par exemple, deux individus se rencontrant entre 12h et 14h. Nous modélisons ces interactions par des flots de liens qui sont des ensembles de quadruplets (b, e, u, v), où chaque quadruplet représente un lien entre les noeuds u et v existant durant l'intervalle [b,e]. Dans un graphe, une communauté est un sous-ensemble plus densément connecté qu’une référence. Dans le formalisme de flot de liens, les notions même de densité et de référence sont à définir. Nous étudions donc comment étendre la notion de communauté aux flots de liens. Pour ce faire, nous nous appuyons sur des données réel où une structure communautaire est connue. Puis, nous développons une méthode permettant de trouver automatiquement des sous-flots qui sont jugés pertinents. Ces sous-flots, c’est-à-dire des sous-ensembles de liens, sont trouvés grâce à une méthode de détection de communautés appliquée sur une projection du flot sur un graphe statique. Un sous-flot est jugé pertinent s’il est plus dense que les sous-flots qui lui sont proches temporellement et topologiquement. Ainsi nous approfondissons les notions de voisinage et référence dans les flots de liens. Nous appliquons cette méthode sur plusieurs jeux de données d’interactions réelles et obtenons des groupes pertinents qui n’auraient pas pu être détectés par les méthodes existantes. Enfin, nous abordons la génération de flots de liens avec une structure communautaire donnée et à la manière d'évaluer une telle partition.Interactions are everywhere: in the contexts of face-to-face contacts, emails, phone calls, IP traffic, etc. In all of them, an interaction is characterized by two entities and a time interval: for instance, two individuals meet from 1pm to 3pm. We model them as link stream which is a set of quadruplets (b,e,u,v) where each quadruplet means that a link exists between u and v from time b to time e. In graphs, a community is a subset which is more densely connected than a reference. Within the link stream formalism, the notion of density and reference have to be redefined. Therefore, we study how to extend the notion of density for link streams. To this end, we use a real data set where a community structure is known. Then, we develop a method that finds automatically substream which are considered relevant. These substream, defined as subsets of links, are discovered by a classical community detection algorithm applied on the link stream the transformed into a static graph. A substream is considered relevant, if it is denser than the substreams which are close temporally and structurally. Thus, we deepen the notion of neighbourhood and reference in link streams. We apply our method on several real world interaction networks and we find relevant substream which would not have been found by existing methods. Finally, we discuss the generation of link streams having a given community structure and also a proper way to evaluate such community structure
An approach for a reliable estimation of the properties of the internet topology
No full textCette thèse propose une nouvelle approche pour estimer des propriétés de la topologie d’Internet. Contrairement aux approches historiques, qui se bases sur des données déclaratives très peu fiables, ou sur la lecture de cartes mesurées avec des outils de diagnostic, notre approche consiste à mettre au point des primitives de mesures très fiables, dont le fonctionnement, les hypothèses et les résultats sont bien définis formellement. Notre premier cas d’étude est celui de la distribution de degré de la topologie logique, ou L3. Nous utilisons l’outil traceroute dont nous étudions le fonctionnement, pour en déduire une primitive de mesure. Cette primitive de mesure, qui repose sur l’utilisation d’un ensemble de moniteurs distribué dans le réseau, permet d’obtenir une estimation du nombre de voisins dans la topologie logique, d’un routeur du cœur. Nous utilisons cette primitive vers un échantillon aléatoire de cibles, pour obtenir une estimation de la distribution de degré recherchée et établir les limites de cette approche. Notre deuxième cas d’étude est celui de la distribution de degré de la topologie physique, ou L2-L3. Nous utilisons l’outil UDP Ping, dont nous étudions le fonctionnement, pour en déduire une primitive de mesure. Elle est semblable à l’outil utilisé pour la topologie logique, mais repose sur des hypothèses bien plus clairement établies et vérifiées, et validée par des simulations très détaillées. Nous intégrons également au protocole de mesure, des garanties statistiques sur l’uniformité de l’échantillon de cibles, des routeurs du cœur, que nous mesurons. Nous obtenons une évaluation de la distribution de degré recherchée, d’une très grande fiabilité. Nous complétons ce cas d’étude par un travail complémentaire sur les tables de transmission des routeurs du cœur. Enfin, nous dressons un tableau assez large des perspectives qui s’ouvrent en se basant sur cette approche, par exemple en l’appliquant à d’autres types de réseaux (réseaux sociaux, etc.).This thesis proposes a novel approach to reliably estimate properties of the Internet topology. Unlike historical approaches, based on declarative, hardly reliable data, or on readings from maps measured with diagnostic tools, our approach is to develop very reliable measure primitives, of which the operation, the hypotheses, and the results are well defined. Our first case study is the degree distribution of the logical topology, or L3. We use the traceroute tool, of which we study the operation, to derive a measurement primitive. This measurement primitive, which relies on using a distribution set of monitors over the network, allows us to get an estimation of the number of neighbors in L3 of a target core router. We use this primitive against a random sample of targets and obtain the sought distribution, and establish limits to this method. Our second case study is the degree distribution of the physical topology, or L2-L3. We use the UDP Ping tool, of which we study the operation, to derive a measurement primitive. It is alike the tool we used for the logical topology, but relies on much more clearly established and verified hypotheses, and is validated by very detailed simulations. We also include statistical guarantees of the sampling uniformity of the target core routers to the measurement protocol. We obtain an evaluation of the sought degree distribution, of an unprecedented reliability. We complete this case study by a complimentary study over the forwarding tables of the core routers. Finally, we picture the many perspectives opened by this approach, eg. By applying it to other types of networks (social networks, etc.)
Link stream graph for temporal recommendations
No full textSeveral researches on recommender systems are based on explicit rating data, but in many real world e-commerce platforms, ratings are not always available, and in those situations, recommender systems have to deal with implicit data such as users' purchase history, browsing history and streaming history. In this context, classical bipartite user-item graphs (BIP) are widely used to compute top-N recommendations. However, these graphs have some limitations, particularly in terms of taking temporal dynamic into account. This is not good because users' preference change over time. To overcome this limit, the Session-based Temporal Graph (STG) was proposed by Xiang et al. to combine long-and short-term preferences in a graph-based recommender system. But in the STG, time is divided into slices and therefore considered discontinuously. This approach loses details of the real temporal dynamics of user actions. To address this challenge, we propose the Link Stream Graph (LSG) which is an extension of link stream representation proposed by Latapy et al. and which allows to model interactions between users and items by considering time continuously. Experiments conducted on four real world implicit datasets for temporal recommendation, with 3 evaluation metrics, show that LSG is the best in 9 out of 12 cases compared to BIP and STG which are the most used state-of-the-art recommender graphs
Importance of temporality in spreading phenomena. A case study of cattle trade movements
No full textLes échanges d'animaux d'élevages entre exploitations agricoles favorisent la diffusion à grande échelle des maladies. L’enjeu est non seulement économique, de par les répercussions fortes sur les marchés de produits d’origine animale en cas de crise, mais également de santé publique, de nombreuses maladies animales étant transmissibles à l’homme (comme la tuberculose bovine). La traçabilité des animaux devient alors une question de plus en plus importante pour retrouver les foyers infectieux, et lutter contre la propagation des maladies. Le développement de ce type de données et leur accessibilité grandissante a permis l’émergence d’études sur leur organisation et leur dynamique. Les outils et modèles développés pour l’étude des réseaux sociaux ont été adaptés à l’étude de ces données. L'apport de cette thèse réside dans l’utilisation de mesures et de modèles intégrant l’information temporelle sur les échanges d’animaux. En effet, le développement des réseaux temporels est relativement récent, et peu d’études les ont à ce jour appliqué échanges d’animaux. L’objectif est donc double, participer au développement des outils d’analyse des réseaux temporels, et en déduire des pistes de développement de mesures de surveillance et de lutte contre la propagation des maladies entre exploitations.Disease spread among agricultural premises is greatly enhanced by cattle trade movements. Preventing spreading is a key issue for economical issues, for instance to prevent trade restrictions, but also for public health. Indeed, many animal diseases affect human beings, such as bovine tuberculosis. Tracing cattle trade movements is aiming at detecting the sources of infection, and thus, helps fighting against disease spread. Accessing databases recording cattle trade movements allows to study the structure and dynamic of the exchanges. To do so, methods developed for Social Network Analysis are more and more adapted and use for these purposes. The aim of this work is to use temporal models and methods to study cattle trade movements. As the development of temporal networks is relatively recent, few analyzes using these methods have been conduct on cattle trade data. Thus, contributions are twofold in this work: taking part to the development of analysis tools of temporal networks, and then, deducting potential ways of enhancement to control and fight against disease spread among holdings
Link streams for modelling interactions over time and application to the analysis of ip traffic
No full textLes interactions sont partout : il peut s'agir de contacts entre individus, d'emails, d'appels téléphoniques, de trafic IP, d'achats en ligne, d'exécution de code, etc. Les interactions peuvent être dirigées, pondérées, enrichies d'informations supplémentaires, cependant, dans tous les cas, une interaction signifie que deux entités u et v ont interagi du temps b au temps e : par exemple, deux individus u et v se rencontrent du temps b au temps e, deux machines sur un réseau démarrent une session IP du temps b au temps e, deux personnes u et v se téléphonent du temps b au temps e, etc.Dans cette thèse, nous explorons une nouvelle approche visant à modéliser les interactions directement comme des flots de liens, c'est-à-dire des séquences de quadruplets (b,e,u,v) signifiant que u et v ont interagi du temps b au temps e. Nous posons les fondations du formalisme correspondant. Afin de valider notre travail théorique, nous nous concentrons sur l'analyse de trafic IP. Il est en effet crucial pour nous d'effectuer des aller-retours constants entre théorie et pratique : les cas pratiques doivent nourrir notre réflexion théorique, et, en retour, les outils formels doivent être conçus de façon à être appliqués de la manière la plus générale.Nous appliquons notre formalisme à l'analyse de trafic IP, dans le but de valider la pertinence de notre formalisme for l'analyse de trafic IP, ainsi que comme méthodologie de détection d'événements. Nous élaborons une méthode permettant d'identifier des événements recouvrant plusieurs échelles de temps, et l'appliquons à une trace de trafic issue du jeu de données MAWI.Interactions are everywhere: in the contexts of face-to-face contacts, emails, phone calls, IP traffic, online purchases, running code, and many others. Interactions may be directed, weighted, enriched with supplementary information, yet the baseline remains: in all cases, an interaction means that two entities u and v interact together from time b to time e: for instance, two individuals u and v meet from time b to time e, two machines on a network start an IP session from time b to time e, two persons u and v phone each other from time b to time e, and so on.In this thesis, we explore a new approach consisting in modelling interactions directly as link streams, i.e. series of quadruplets ( b, e, u, v ) meaning that u and v interacted from time b to time e, and we develop the basis of the corresponding formalism. In order to guide and assess this fundamental work, we focus on the analysis of IP traffic. It is particularly important to us that we make both fundamental and applied progress: application cases should feed our theoretical thoughts, and formal tools are designed to have meaning on application cases in the most general way.We apply our framework to the analysis of IP traffic, with the aim of assessing the relevance of link streams for describing IP traffic as well as finding events inside the traffic. We devise a method to identify events at different scales, and apply it to a trace of traffic from the MAWI dataset
- …
