Diffusion of new ideas, technologies or epidemics via various social networks has been extensively studied for decades. In particular, Kempe, Kleinberg, and Tardos proposed the \emph{general threshold model}, a generalization of many diffusion models on networks which is based on utility maximization of individuals in game theoretic consideration. Despite its importance, the analysis under the threshold model, however, has concentrated on special cases such as the submodular influence, homogeneous thresholds, and locally tree-like networks. In this paper, we consider the general threshold model~ with arbitrary threshold distributions on arbitrary networks. We prove that only if (essentially) all nodes have degrees ω(log n), the final cascade size is highly concentrated around its mean with high probability for a large class of general threshold models including the linear threshold model, the independent cascade model, and the Katz-Shapiro pricing model. We also prove that in those cases, the expectation of the cascade size is asymptotically invariant of the network structures and provide a formula to compute the average cascade size, if initial adopters are chosen uniformly at random. Hence, even if network structures are not known, we can still estimate the final cascade size. We also extend our results to arbitrary general threshold models and provide upper and lower bounds for the cascade size. We then provide an efficient algorithm that estimates the average cascade size for the general threshold model. Our algorithm also computes the probability of being influenced for each individual. Our results allow us to predict when a phase transition for a large spreading happens. Since our algorithm estimates the final cascade size efficiently, it can be also used as a subroutine in many algorithms for the influence maximization problem. Through extensive experiments on several real-world and synthetic networks, we confirm that the cascade size is actually concentrated around its mean and a phase transition appears at the predicted point even though the degree of each individual are not large.
기술, 새로운 관념 또는 전염병이 소셜 네트워크로 퍼져 나가는 현상은 특히 입소문 마케팅, 전염병 확산 방지 등의 다양한 응용 분야에서 수십년간 활발히 연구되어왔다. 여러 확산 모델들의 일반화된 형태이며, 게임 이론적인 관점에서 각 개인의 효용의 극대화에 기반하여 제시된 general threshold model은 다양한 상황에 적용가능하지만 분석이 어렵기 때문에 제한적인 조건하에서만 연구되어왔다. 특히 linear threshold model은 general threshold의 특별한 경우로 threshold 함수가 linear한 형태인 것으로 정보확산 현상을 설명하는 가장 중요한 모델 중 하나이다. 이 논문에서는 네트워크의 모든 node가 ω(log n) 보다 degree가 클 때, 임의의 threshold 분포를 허용하는 linear threshold model에 의해 정보 확산이 일어나면 최종 확산 규모가 매우 높은 확률로 평균값 근처에 집중된다는 것을 보인다. 또한 정보의 초기 수용자가 전체 인구중에서 uniform random하게 선택될 때, 확산 규모의 기대값이 점근적으로 네트워크 구조에 영향을 받지 않는다는 것을 보이며 그 값을 계산하는 식을 제시하여 네트워크 구조가 알려지지 않아도 확산 규모를 예측 할 수 있도록 한다. 이 결과를 더 확장하여, general threshold model에서 확산 규모의 상한값과 하한값을 구하며 많은 경우에 그 값이 같아짐을 증명한다. 또한 이 경우에 평균 확산 규모를 예측하는 효율적이 알고리즘을 제시한다. 이 결과를 통해 정보 확산 규모와 최종 확산 규모가 급격히 증가하게되는 tipping point를 빠른 시간에 계산한다. 우리는 실제 온라인 소셜 네트워크와 synthetic 네트워크상에서의 다양한 실험을 통해 최종확산규모가 실제로 그 평균값에 집중되어있으며 tipping point가 예상한 지점에서 나타난 것을 보인다. 네트워크에 ω(log n) 보다 degree가 작은 node를 포함하더라도 비슷한 결과를 보인다.
