Recent Advancements in the Theory of Influence Maximization


Biaoshuai Tao,University of Michigan


2020-07-29 15:30:00 ~ 2020-07-29 17:00:00


Shuai Li


People often adopt improved behaviors, products, or ideas through the influence of friends.  One way to spread such positive elements through society is to identify those most influential agents, those that cause the maximum spread, and initiate the spread by seeding them. However, this strategy has a key difficulty: finding these influential seed nodes. This is difficult even if both the network structure and the way how the spread goes are known. In social networks, cascades model the phenomena that agents receive certain information, adopt certain products, or take up certain political opinions from their neighbors due to their influence. In the influence maximization problem, a central planner is given a graph and a limited budget k, and he needs to pick k seeds such that the expected total number of infected vertices in the graph at the end of the cascade is maximized. This problem plays a central role in viral marketing, outbreak detection, rumor controls, etc.


This talk will focus on computational complexity, approximability and algorithm design aspects of the influence maximization problem, with both submodular and nonsubmodular cascade models. Firstly, I will present my recent results about the algorithmic complexity of submodular influence maximization, which are breakthrough in understanding the approximability of submodular influence maximization during the last 15 years. Secondly, I will present a new sociologically founded nonsubmodular cascade model that I proposed and show that how the seeding strategy for nonsubmodular cascade models is fundamentally different compared to submodular cascade models.


Finally, I will survey some of my other work, especially, my work in the fair division problem.


Biaoshuai Tao received the Ph.D. degree in Computer Science and Engineering from the University of Michigan, Ann Arbor, in 2020. His research interests mainly include the interdisciplinary area between theoretical computer science and economics, including social network analyses, resource allocation problems and algorithmic game theory. Before joining the University of Michigan, Biaoshuai was employed as a project officer at Nanyang Technological University in Singapore from 2012 to 2015, and he received the B.S. degree in mathematical science with a minor in computing from Nanyang Technological University in 2012.

© John Hopcroft Center for Computer Science, Shanghai Jiao Tong University

邮箱:jhc@sjtu.edu.cn 电话:021-54740299