Viral Marketing On Configuration Model

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.

Data and Resources

Additional Info

Field Value
Source https://inria.hal.science/hal-00864779
Author Blaszczyszyn, Bartlomiej, Gaurav, Kumar
Maintainer CCSD
Last Updated May 9, 2026, 15:48 (UTC)
Created May 9, 2026, 15:48 (UTC)
Identifier hal-00864779
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Dynamics of Geometric Networks (DYOGENE) ; Département d'informatique - ENS-PSL (DI-ENS) ; École normale supérieure - Paris (ENS-PSL) ; Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL) ; Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt ; Institut National de Recherche en Informatique et en Automatique (Inria)
creator Blaszczyszyn, Bartlomiej
date 2013-09-23T00:00:00
harvest_object_id 92abca3b-9ea0-4985-b0ef-4d4c5138b7ec
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-10-27T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1309.5779
set_spec type:UNDEFINED