Leveraging the power of social propagations: Algorithm designs for social marketing

Social propagation is a fundamental and prevalent process taking place in social networks, where due to the peer influence of social network users, behaviors of a few influential users can spread widely in a network. Leveraging the social propagation effect lies at the core of mining the marketing values of social networks, and has been extensively studied in the past decade. Most existing studies aim at identifying influential users in a social network, the first step of making good use of propagation in applications like viral marketing and computational advertising. However, in many deeper marketing applications, such as personalized pricing in promotional campaign planning and real-time recommendation of influential bloggers, effectively exploiting social propagations faces many unsettled and challenging algorithmic problems. In this thesis, we investigate some crucial algorithmic problems in leveraging the propagation effect of social networks in social marketing. In particular, we first discuss how to efficiently monitor top influential users in a rapidly evolving social network. Then we investigate how to spend a budget wisely to motivate influential users to trigger large-scale propagations for marketing purposes. We also study how to schedule an effective propagation to maximize the interaction activities of users influenced, which aims at the marketing effect after the propagation is finished. Our work provides powerful algorithmic tools to solve these problems effectively, which at the same time are efficient and can deal with large networks containing millions or even tens of millions of vertices in a single machine. We conclude this thesis by discussing some future directions in mining social propagations.