Influence Maximization on Undirected Graphs: Towards Closing the (1-1/e) Gap
- Biaoshuai Tao, University of Michigan, Ann Arbor
- Time: 2019-06-05 15:00
- Host: Dr. Yuqing Kong
- Venue: Room 102, Courtyard No.5, Jingyuan
Abstract
We study the influence maximization problem in undirected networks, specifically focusing on the independent cascade and linear threshold models. We prove APX-hardness (NP-hardness of approximation within factor (1-tau) for some constant tau>0) for both models, which improves the previous NP-hardness lower bound for the linear threshold model. No previous hardness result was known for the independent cascade model.
As part of the hardness proof, we show some natural properties of these cascades on undirected graphs. For example, we show that the expected number of infections of a seed set S is upper-bounded by the size of the edge cut of S in the linear threshold model and a special case of the independent cascade model, the weighted independent cascade model.
Motivated by our upper bounds, we present a suite of highly scalable local greedy heuristics for the influence maximization problem on both the linear threshold model and the weighted independent cascade model on undirected graphs that, in practice, find seed sets which on average obtain 97.52% of the performance of the much slower greedy algorithm for the linear threshold model, and 97.39% of the performance of the greedy algorithm for the weighted independent cascade model. Our heuristics also outperform other popular local heuristic, such as the degree discount heuristic by Chen et al..
Biography
Biaoshuai Tao received the B.S. degree in mathematical science with a minor in computing from Nanyang Technological University, Singapore, in 2012. He is currently working toward the Ph.D. degree with the Computer Science and Engineering Division, University of Michigan, Ann Arbor, MI, USA. His research interests mainly include the interdisciplinary area between theoretical computer science and economics, including social network, resource allocation and algorithmic game theory.