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 de l'École normale supérieure, 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.
Type de document :
Communication dans un congrès
MAMA workshop, held in conjunction with ACM Sigmetrics/Performance, Jun 2012, London, United Kingdom. acm, 4, pp.100-103, 2012, Performance Evaluation Review. 〈10.1145/2425248.2425276〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00733414
Contributeur : Bartlomiej Blaszczyszyn <>
Soumis le : mardi 18 septembre 2012 - 15:58:44
Dernière modification le : vendredi 25 mai 2018 - 12:02:04

Lien texte intégral

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

294