Viral Marketing On Configuration Model

Bartlomiej Blaszczyszyn 1 Kumar Gaurav 1, 2
1 DYOGENE - Dynamics of Geometric Networks
CNRS - Centre National de la Recherche Scientifique : UMR8548, Inria Paris-Rocquencourt, DI-ENS - Département d'informatique de l'École normale supérieure
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 metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00864779
Contributor : Bartlomiej Blaszczyszyn <>
Submitted on : Monday, September 23, 2013 - 11:37:37 AM
Last modification on : Wednesday, January 30, 2019 - 11:08:04 AM
Long-term archiving on : Tuesday, December 24, 2013 - 4:30:59 AM

Files

Viral2.pdf
Files produced by the author(s)

Identifiers

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

Citation

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

Share

Metrics

Record views

452

Files downloads

209