Viral Marketing On Configuration Model

Bartlomiej Blaszczyszyn 1 Kumar Gaurav 1, 2
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : We consider propagation of influence on a Configuration Model, where each vertex can be influenced by any of its neighbours but in its turn, it can only influence a random subset of its neighbours. Our (enhanced) model is described by the total degree of the typical vertex, representing the total number of its neighbours and the transmitter degree, representing the number of neighbours it is able to influence. We give a condition involving the joint distribution of these two degrees, which if satisfied would allow with high probability the influence to reach a non-negligible fraction of the vertices, called a big (influenced) component, provided that the source vertex is chosen from a set of good pioneers. We show that asymptotically the big component is essentially the same, regardless of the good pioneer we choose, and we explicitly evaluate the asymptotic relative size of this component. Finally, under some additional technical assumption we calculate the relative size of the set of good pioneers. The main technical tool employed is the "fluid limit" analysis of the joint exploration of the configuration model and the propagation of the influence up to the time when a big influenced component is completed. This method was introduced in Janson & Luczak (2008) to study the giant component of the configu\-ration model. Using this approach we study also a reverse dynamic, which traces all the possible sources of influence of a given vertex, and which by a new "duality" relation allows to characterise the set of good pioneers.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger
Contributeur : Bartlomiej Blaszczyszyn <>
Soumis le : lundi 23 septembre 2013 - 11:37:37
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : mardi 24 décembre 2013 - 04:30:59


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00864779, version 1
  • ARXIV : 1309.5779



Bartlomiej Blaszczyszyn, Kumar Gaurav. Viral Marketing On Configuration Model. 2013. 〈hal-00864779〉



Consultations de la notice


Téléchargements de fichiers