Abstract
Motivated by the analysis of social networks, we study a model of random
networks that has both a given degree distribution and a tunable clustering
coefficient. We consider two types of growth processes on these graphs:
diffusion and symmetric threshold model. The diffusion process is inspired from
epidemic models. It is characterized by an infection probability, each neighbor
transmitting the epidemic independently. In the symmetric threshold process,
the interactions are still local but the propagation rule is governed by a
threshold (that might vary among the different nodes). An interesting example
of symmetric threshold process is the contagion process, which is inspired by a
simple coordination game played on the network. Both types of processes have
been used to model spread of new ideas, technologies, viruses or worms and
results have been obtained for random graphs with no clustering. In this paper,
we are able to analyze the impact of clustering on the growth processes. While
clustering inhibits the diffusion process, its impact for the contagion process
is more subtle and depends on the connectivity of the graph: in a low
connectivity regime, clustering also inhibits the contagion, while in a high
connectivity regime, clustering favors the appearance of global cascades but
reduces their size.
For both diffusion and symmetric threshold models, we characterize conditions
under which global cascades are possible and compute their size explicitly, as
a function of the degree distribution and the clustering coefficient. Our
results are applied to regular or power-law graphs with exponential cutoff and
shed new light on the impact of clustering.
Users
Please
log in to take part in the discussion (add own reviews or comments).