Institute of Information Science, Academia Sinica

With the emergence of varied social networking services, now over 1.4 billion users around the world visit social networking websites everyday, and nearly 1 in every 5 minutes spent online is for social network applications. As reported by renowned media such as Bloomberg Businessweek, CNN, and New York, the impacts of social influence have penetrated not only in business and politics but also in everyday life. The study in Nature 2012 also demonstrated that people decisions are indeed affected by social influence passing through online social networks. In this talk, therefore, we will introduce the optimization for diffusion of social influence in online social networks. We will first present the diffusion models of social influence and the corresponding hardness results of complexity theory in computer science. We will then introduce several approximation algorithms to solve the influence maximization problems based the above models, where two of them are from our ACM SIGKDD papers. Several innovative social applications based on social influence and their implementations on Facebook will be presented finally.