WANG Xiaomin
Supervision : Michèle SORIA
Co-supervision : LATAPY Matthieu
Deciding on the type of the degree distribution of a graph (network) from traceroute-like measurements
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 powerlaw) of the degree distribution from such a limited knowledge. We design procedures which estimate the degree distribution of a graph from a BFS or multi-BFS trees, and show experimentally (on models and real world data) that our approaches succeed in making the difference between Poisson and power law degree distribution and in some cases can also estimate the number of links. In addition, we establish a method, which is a diminishing urn, to analyze the procedure of the queue. We analyze the profile of the BFS tree from a random graph with a given degree distribution. The expected number of nodes and the expected number of invisible links at each level of BFS tree are two main results that we obtain. Using these informations, we propose two new methodologies to decide on the type of the underlying graph.
Defence : 12/13/2011
Jury members :
Mme. Delporte-Gallet Carole, Professeur, Université de Paris 7-Denis Diderot [Rapporteur]
M. Hwang Hsien-kuei, Senior Researcher, Institute of Statistical Science Academia Sinica [Rapporteur]
M. Crespelle Christophe, Maître de conférences, Université Claude Bernard Lyon 1
M. Latapy Matthieu, Directeur de recherche, CNRS affecté au LIP6
Mme. Legrand Bénédicte, Maître de conférences (HDR), Université Pierre et Marie Curie, LIP6
Mme. Soria Michèle, Professeur, Université Pierre et Marie Curie, LIP6
2010-2012 Publications
-
2012
- X. Wang, M. Latapy, M. Soria : “Deciding on the type of the degree distribution of a graph from traceroute-like measurements”, International Journal of Computer Networks & Communications, vol. 4 (3), pp. 151-167, (AIRCC Publishing Corporation) (2012)
-
2011
- X. Wang : “Deciding on the type of the degree distribution of a graph (network) from traceroute-like measurements”, thesis, defence 12/13/2011, supervision Soria, Michèle, co-supervision : Latapy, Matthieu (2011)
-
2010
- X. Wang, M. Latapy, M. Soria : “Deciding on the type of a graph from a BFS”, Workshop on Complex Networks CompleNet 2010, vol. 116, Communications in Computer and Information Science, Rio de Janeiro, Brazil, pp. 68-74, (Springer) (2010)