Penalising transmission to hubs in scale-free spatial random graphs

Abstract

We study the spread of information in finite and infinite inhomogeneous spatial random graphs. We assume that each edge has a transmission cost that is a product of an i.i.d. random variable L and a penalty factor: edges between vertices of expected degrees w1 and w2 are penalised by a factor of (w1w2)μ for all μ > 0. We study this process for scale-free percolation, for (finite and infinite) Geometric Inhomogeneous Random Graphs, and for Hyperbolic Random Graphs, all with power law degree distributions with exponent τ > 1. For τ < 3, we find a threshold behaviour, depending on how fast the cumulative distribution function of L decays at zero. If it decays at most polynomially with exponent smaller than (3 − τ)/(2μ) then explosion happens, i.e., with positive probability we can reach infinitely many vertices with finite cost (for the infinite models), or reach a linear fraction of all vertices with bounded costs (for the finite models). On the other hand, if the cdf of L decays at zero at least polynomially with exponent larger than (3 − τ)/(2μ), then no explosion happens. This behaviour is arguably a better representation of information spreading processes in social networks than the case without penalising factor, in which explosion always happens unless the cdf of L is doubly exponentially flat around zero. Finally, we extend the results to other penalty functions, including arbitrary polynomials in w1 and w2. In some cases the interesting phenomenon occurs that the model changes behaviour (from explosive to conservative and vice versa) when we reverse the role of w1 and w2. Intuitively, this could corresponds to reversing the flow of information: gathering information might take much longer than sending it out.