Skip to Main content Skip to Navigation
Conference papers

Far-out Vertices In Weighted Repeated Configuration Model

Bartlomiej Blaszczyszyn 1 Kumar Gaurav 1 
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique - ENS Paris, Inria Paris-Rocquencourt
Abstract : We consider an edge-weighted uniform random graph with a given degree sequence (Repeated Configuration Model) which is a useful approximation for many real-world networks. It has been observed that the vertices which are separated from the rest of the graph by a distance exceeding certain threshold play an important role in determining some global properties of the graph like diameter, flooding time etc., in spite of being statistically rare. We give a convergence result for the distribution of the number of such far-out vertices. We also make a conjecture about how this relates to the longest edge of the minimal spanning tree on the graph under consideration.
Complete list of metadata
Contributor : Bartlomiej Blaszczyszyn Connect in order to contact the contributor
Submitted on : Tuesday, September 18, 2012 - 3:58:44 PM
Last modification on : Thursday, March 17, 2022 - 10:08:30 AM

Links full text




Bartlomiej Blaszczyszyn, Kumar Gaurav. Far-out Vertices In Weighted Repeated Configuration Model. MAMA workshop, held in conjunction with ACM Sigmetrics/Performance, acm, Jun 2012, London, United Kingdom. pp.100-103, ⟨10.1145/2425248.2425276⟩. ⟨hal-00733414⟩



Record views