Influence Diffusion and Group Formation in Online Social Networks

Abstract

With the emergence of varied social networking services, now over 1.2 billion users around the world visit social networking websites everyday, and nearly 1 in every 5 minutes spent online is on social network applications. As reported by renowned media such as Bloomberg Businessweek, CNN, and New York, the impacts of social networks 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 diffusion of social influence and the formation of social groups in online social networks. We will present the diffusion problem of social influence and subgraph extraction problem for social groups, together with the corresponding hardness results of complexity theory in computer science. We will then introduce several approximation algorithms to solve the influence maximization problem and group formation problem. Applications with implementations on Facebook for active friending and detection of social mental disorder will be presented finally.