On some diffusion and spanning problems in configuration model

Kumar Gaurav 1
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : A number of real-world systems consisting of interacting agents can be usefully modelled by graphs, where the agents are represented by the vertices of the graph and the interactions by the edges. Such systems can be as diverse and complex as social networks (traditional or online), protein-protein interaction networks, internet, transport network and inter-bank loan networks. One important question that arises in the study of these networks is: to what extent, the local statistics of a network determine its global topology. This problem can be approached by constructing a random graph constrained to have some of the same local statistics as those observed in the graph of interest. One such random graph model is configuration model, which is constructed in such a way that a uniformly chosen vertex has a given degree distribution. This is the random graph which provides the underlying framework for this thesis. As our first problem, we consider propagation of influence on 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 and the number of neighbours it is able to influence. We give a tight condition, involving the joint distribution of these two degrees, which allows with high probability the influence to reach an essentially unique non-negligible set of the vertices, called a big influenced component, provided that the source vertex is chosen from a set of good pioneers. We explicitly evaluate the asymptotic relative size of the influenced component as well as of the set of good pioneers, provided it is non-negligible. Our proof uses the joint exploration of the configuration model and the propagation of the influence up to the time when a big influenced component is completed, a technique introduced in Janson and Luczak (2008). Our model can be seen as a generalization of the classical Bond and Node percolation on configuration model, with the difference stemming from the oriented conductivity of edges in our model. We illustrate these results using a few examples which are interesting from either theoretical or real-world perspective. The examples are, in particular, motivated by the viral marketing phenomenon in the context of social networks...
Document type :
Theses
Complete list of metadatas

Cited literature [54 references]  Display  Hide  Download

https://hal.inria.fr/tel-01400999
Contributor : Abes Star <>
Submitted on : Wednesday, March 1, 2017 - 11:38:23 AM
Last modification on : Thursday, February 7, 2019 - 1:32:51 AM
Long-term archiving on : Tuesday, May 30, 2017 - 4:03:12 PM

File

2016PA066362.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01400999, version 2

Citation

Kumar Gaurav. On some diffusion and spanning problems in configuration model. Dynamical Systems [math.DS]. Université Pierre et Marie Curie - Paris VI, 2016. English. ⟨NNT : 2016PA066362⟩. ⟨tel-01400999v2⟩

Share

Metrics

Record views

975

Files downloads

152