Measuring and Modeling the Cascades/Diffusions through Online Social Networks

Understanding how information, product adoption, trends, etc., diffuse among users in online social networks (OSNs) is crucial for many applications, such as viral marketing, online advertising, content ranking, and recommendation filtering. We start our work by measuring and modeling a very popular kind of diffusions (or cascades) through OSNs: installation of OSN based applications. While various models have been proposed for generating static OSN-like topologies, the dynamics of user interactions through OSN based applications remain largely unexplored. We present a new continuous graph evolution model aimed to capture microscopic user-level behaviors that govern the growth of applications' user population (cascade size) and collectively define the cascade topology. We demonstrate the utility of our model by applying it to estimate the number of active users over time as the application transitions from initial growth to peak/mature and decline/fatique phase. Using empirical evaluations, we show that our model can accurately reproduce the evolution trend of active user population for gifting applications, or other OSN applications that employ similar growth mechanisms. We also demonstrate that the user population estimated by our model can guide further analysis of user behaviors based on the user activity graph (UAG), a graphical tools that captures temporal user-to-user interactions.;Continuing this dissertation, we investigate deeper into the expansion of diffusions/cascades based on invitations: users actively invite their neighbors to join a cascade, by sending (possibly) multiple invitation messages. Utilizing large scale empirical data from Twitter, as well as a very popular Facebook gifting application, we identify salient properties of the process through which invitations sent by users lead to successful recruitments. Based on our empirical observations, we derive a cascade model that describes the invitation-based diffusion, and formulate a maximum likelihood estimation to infer the model's parameters from real traces. We extensively evaluate the accuracy of our inference methodology on the Twitter and Facebook datasets.;We also study the problem of inferring the topology of user interaction network, among which the diffusions/cascades expand from current users to a larger user basis. We propose a framework of introducing graph structural priors into the inference process. This framework allows us to capture a wide array of priors on the graph's degree distribution, including, e.g., power-law, which is important due to the natural prevalence of such structure in complex networks. We show that network inference under our model is amenable to the so-called majorize-minimize method, and that its implementation is tractable, as each step amounts to solving a convex optimization problem. We extensively evaluate our method over synthetic datasets as well as real-world datasets from Twitter and a Facebook app, iHeart. We observe that network inference incorporating our structural priors significantly outperforms state-of-the-art prior-free approaches incorporating arbitrary regularization term.