Title: Normalization Phenomena in Asynchronous Networks.

Authors: Amin Karbasi, Johannes Lengler, Angelika Steger:


In this work we study a diffusion process in a network that consists of two types of vertices: inhibitory vertices (those obstructing the diffusion) and excitatory vertices (those facilitating the diffusion). We consider a continuous time model in which every edge of the network draws its transmission time randomly. For such an asynchronous diffusion process it has been recently proven that in Erdős-Rényi random graphs a normalization phenomenon arises: whenever the diffusion starts from a large enough (but still tiny) set of active vertices, it only percolates to a certain level that depends only on the activation threshold and the ratio of inhibitory to excitatory vertices. In this paper we extend this result to all networks in which the percolation process exhibits an explosive behaviour. This includes in particular inhomogeneous random networks, as given by Chung-Lu graphs with degree parameter 𝛽∈(2,3) .

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale