Beyond Sigmoids: the NetTide Model for Social Network Growth, and its Applications
Chengxi Zang*, Tsinghua University; Peng Cui, Tsinghua University; Christos Faloutsos, Carnegie Mellon University
What is the growth pattern of social networks, like Facebook and WeChat? Does it truly exhibit exponential early growth, as predicted by textbook models like the Bass model, SI, or the Branching Process? How about the count of links, over time, for which there are few published models?
We examine the growth of several real networks, including one of the world’s largest online social network, “WeChat”, with 300 million nodes and 4.75 billion links by 2013; and we observe power law growth for both nodes and links, a fact that completely breaks the sigmoid models (like SI, and Bass). In its place, we propose NETTIDE, along with differential equations for the growth of the count of nodes, as well as links. Our model accurately fits the growth patterns of real graphs; it is general, encompassing as special cases all the known, traditional models (including Bass, SI, log-logistic growth); while still remaining parsimonious, requiring only a handful of parameters. Moreover, our NETTIDE for link growth is the first one of its kind, accurately fitting real data, and naturally leading to the densification phenomenon. We validate our model with four real, time-evolving social networks, where NET-TIDE gives good fitting accuracy, and, more importantly, applied on the WeChat data, our NETTIDE model forecasted more than 730 days into the future, with 3% error.
Filed under: Mining Rich Data Types