Eur. Phys. J. B (2016) 89: 188
https://doi.org/10.1140/epjb/e2016-60612-y

Regular Article

Phase transitions for information diffusion in random clustered networks

¹ Graduate School of Knowledge Service Engineering, KAIST, 34141 Daejeon, Republic of Korea
² Department of Electrical and Computer Engineering, Seoul National University, 08826 Seoul, Republic of Korea
³ Korea Development Bank, 07242 Seoul, Republic of Korea

^a e-mail: kjung@snu.ac.kr

Received: 29 July 2015
Received in final form: 10 December 2015
Published online: 5 September 2016

Abstract

We study the conditions for the phase transitions of information diffusion in complex networks. Using the random clustered network model, a generalisation of the Chung-Lu random network model incorporating clustering, we examine the effect of clustering under the Susceptible-Infected-Recovered (SIR) epidemic diffusion model with heterogeneous contact rates. For this purpose, we exploit the branching process to analyse information diffusion in random unclustered networks with arbitrary contact rates, and provide novel iterative algorithms for estimating the conditions and sizes of global cascades, respectively. Showing that a random clustered network can be mapped into a factor graph, which is a locally tree-like structure, we successfully extend our analysis to random clustered networks with heterogeneous contact rates. We then identify the conditions for phase transitions of information diffusion using our method. Interestingly, for various contact rates, we prove that random clustered networks with higher clustering coefficients have strictly lower phase transition points for any given degree sequence. Finally, we confirm our analytical results with numerical simulations of both synthetically-generated and real-world networks.