图 书 馆
多轮影响最大化Multi-Round Influence Maximization |
|
| 课程网址: | http://videolectures.net/kdd2018_sun_multi-round_maximization/ |
| 主讲教师: | Lichao Sun |
| 开课单位: | 伊利诺大学芝加哥分校 |
| 开课时间: | 2018-11-23 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | In this paper, we study the Multi-Round Influence Maximization (MRIM) problem, where influence propagates in multiple rounds independently from possibly different seed sets, and the goal is to select seeds for each round to maximize the expected number of nodes that are activated in at least one round. MRIM problem models the viral marketing scenarios in which advertisers conduct multiple rounds of viral marketing to promote one product. We consider two different settings: 1) the non-adaptive MRIM, where the advertiser needs to determine the seed sets for all rounds at the very beginning, and 2) the adaptive MRIM, where the advertiser can select seed sets adaptively based on the propagation results in the previous rounds. For the non-adaptive setting, we design two algorithms that exhibit an interesting tradeoff between efficiency and effectiveness: a cross-round greedy algorithm that selects seeds at a global level and achieves 1/2−ε approximation ratio, and a within-round greedy algorithm that selects seeds round by round and achieves 1−e −(1−1/e)−ε ≈ 0.46−ε approximation ratio but saves running time by a factor related to the number of rounds. For the adaptive setting, we design an adaptive algorithm that guarantees 1 − e −(1−1/e) − ε approximation to the adaptive optimal solution. In all cases, we further design scalable algorithms based on the reverse influence sampling approach and achieve near-linear running time. We conduct experiments on several real-world networks and demonstrate that our algorithms are effective for the MRIM task. |
| 关 键 词: | 多轮影响最大化; 节点的预期数量; 交叉循环贪婪算法; 轮内贪婪算法 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2023-03-09：cyh |
| 最后编审: | 2023-05-15：cyh |
| 阅读次数: | 26 |