INFLUENCE MAXIMIZATION UNDERCOMPOUNDED UNCERTAINTIES: EFFICIENTALGORITHMS WITH PROVABLE GUARANTEES

The Hong Kong University of Science and Technology (Guangzhou)

数据科学与分析学域

PhD Thesis Proposal Examination

By Mr. CHEN Xiaolong

摘要

Influence Maximization (IM) stands as a pivotal algorithmic problem within the domain of social network analysis, boasting considerable applicability across diverse sectors including viral marketing and political campaigning. The IM problem aims to maximize the expected number of influenced users. Underscored by its practical utility and the profound complexities inherent in its resolution, IM has catalyzed two decades of scholarly examination. In this report, we delve into several problems to incorporate more un certainties into the problem in addition to the uncertainty of influence propagation, and propose efficient algorithms with provable guarantees. Specifically, we commence by considering the scenario where users have a fixed probability to propagate negative opinions. Then we move from node selection to probabilistic edge insertion and study the influence maximization with augmentation problem, with two newly proposed algorithms. Subsequently, we consider the seeds to augment are inherently uncertain and propose efficient algorithms to recommend links for such uncertain seeds. Extensive experiments are conducted to validate the effectiveness and efficiency of our algorithms.

TPE Committee

Chair of Committee: Prof. LUO Qiong

Prime Supervisor: Prof. TANG Jing

Co-Supervisor: Prof. WANG Wei

Examiner: Prof. ZHANG Yongqi