Abstract:Influence maximization is the task of selecting k seed nodes in a social network such that the influence spread of the seeds is maximized. It models the viral marketing scenario, and can also be applied to other scenarios such as cascade monitoring and rumor control. Since proposed in 2003, influence maximization and its variants have been extensively studied, and the area is still actively growing. Influence maximization is also a nice demonstration of how classical algorithms could be integrated into the social network context. In this talk, I will first introduce the core research problems and major results in influence maximization. Then through several examples, I will demonstrate how classical algorithms, such as the greedy algorithm, Dijkstra’s shortest path algorithm, UCB for multi-armed bandit are integrated into influence maximization algorithms, and how new research challenges are raised during this integration and how we address these challenges, and in some cases by expanding the classical algorithms to fit into the new settings.
Personal introduction: Wei Chen is a Principal Researcher at Microsoft Research Asia, an Adjunct Professor at Tsinghua University, and an Adjunct Researcher at Chinese Academy of Sciences. He is a fellow of IEEE. His main research interests include social and information networks, online learning, network game theory and economics, distributed computing, and fault tolerance. He has conducted extensive research work on the modeling and algorithmic studies on information and influence propagation in social networks, coauthored a monograph in 2013, “Information and Influence Propagation in Social Networks”, and just published a single-authored monograph “Big Data Network Diffusion Models and Algorithms” (in Chinese). He is the member of CCF Task Force on Big Data and Technical Committee on Theoretical Computer Science. He has served on the program committees of many top conferences in data mining, machine learning, and artificial intelligence. Wei Chen has Bachelor and Master degrees in computer science from Tsinghua University and a Ph.D. degree in computer science from Cornell University. For more information, you are welcome to visit his home page at http://research.microsoft.com/en-us/people/weic/.