ARC Colloquium: Kyomin Jung, KAIST (South Korea)
Diffusion of information, new ideas or epidemics via various social networks has been extensively studied for decades. In particular, Kempe, Kleinberg, and Tardos (KDD '03) proposed the 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 (by Mossel-Roch (STOC '07)), homogeneous thresholds (by Whitney(Phys. Rev. E. '10)), and locally tree-likenetworks (by Watts(PNAS '02)). We first consider the general threshold model with arbitrary threshold distributions on arbitrary networks. We prove that only if (essentially) all nodes have degrees \omega(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 SIR-epidemic model, and the Katz-Shapiro pricing model. We also prove that in those cases, somewhat surprisingly, the expectation of the cascade size is asymptotically invariant of the network structure if initial adopters are chosen uniformly at random, and provide a formula to compute the average cascade size. Our formula allows us to compute when a phase transition for a large spreading (a tipping point) happens, and can be used for the influence maximization for social networks.
Then we consider the SIR-epidemic model with arbitrary contact rates when the initial adopters are any finite set. We compute asymptotically the tipping point and the sizes of the giant components on clustered and unclusterd random networks. We prove that for various contact rates the tipping point is strictly smaller in the clustered network than the unclusterd network, which quantitatively shows the positive effect of the community structure on the information diffusion. We confirm our results through extensive experiments on several real-world and synthetic networks.
Kyomin Jung is an assistant professor at KAIST Computer Science department. He has joint appointments in KAIST Math and EE departments. His main research interest includes social network modeling and analysis, and machine learning. He received his Ph.D. at MIT Mathematics in 2009. During his Ph.D., he worked at Microsoft Research Cambridge (2008), IBM T.J. Watson Research (2007), Bell Labs Murray Hill (2006) as research internships. He received his B.Sc. at Seoul National Univ. Mathematics in 2003, and he won a gold medal in IMO(International Mathematical Olympiad) 1995.