Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Viral Marketing On Configuration Model

Bartlomiej Blaszczyszyn 1 Kumar Gaurav 1, 2 
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique - ENS Paris, 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Bartlomiej Blaszczyszyn Connect in order to contact the contributor
Submitted on : Monday, September 23, 2013 - 11:37:37 AM
Last modification on : Thursday, March 17, 2022 - 10:08:44 AM
Long-term archiving on: : Tuesday, December 24, 2013 - 4:30:59 AM


Files produced by the author(s)


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


Bartlomiej Blaszczyszyn, Kumar Gaurav. Viral Marketing On Configuration Model. 2013. ⟨hal-00864779⟩



Record views


Files downloads