Contagion probability in linear threshold model.

We study a linear threshold model on a simple undirected connected network G where each non-seed becomes active if and only if the proportion of its active neighbors exceeds its adoption threshold. Each threshold function ϕ : V → [ 0 , 1 ] is viewed as a point (ϕ (v 1) , ... , ϕ (v n)) in the n -cube [ 0 , 1 ] n , where V = { v 1 , ... , v n } is the set of nodes in G. We define ϕ as a contagious point of a subset S of nodes if it can induce full contagion from S. Consequently, the volume of the set of contagious points of S in [ 0 , 1 ] n represents the probability of full contagion from S when the adoption threshold of each node is independently and uniformly distributed in [ 0 , 1 ] , which we term the contagion probability of S and denote by p c (S). We derive an explicit formula for p c (S) , showing that p c (S) is determined by how likely S can produce full contagion exclusively through each spanning tree of the quotient graph G S of G in which S is treated as a single node. Besides, we compare p c (S) with the contagion threshold of S , which is denoted by q c (S) and is the probability of full contagion from S when all nodes share a common adoption threshold q chosen uniformly at random from [ 0 , 1 ]. We show that the presence of a cycle in G S is necessary but not sufficient for p c (S) to exceed q c (S) , which indicates that allowing threshold heterogeneity may not always increase the chance of full contagion. Our framework can be extended to study contagion under various threshold settings. [ABSTRACT FROM AUTHOR]