报告题目：An Efficient Randomized Algorithm for Rumor Blocking

报告人：堵丁柱 教授

单位：德克萨斯大学达拉斯分校

报告时间：2017年4月24日（周一）下午15:00-17:00

报告地点：逸夫科教楼408会议室

报告人简介：1982年获中国科学院硕士学位，1985年获美国加利福利亚大学圣巴巴拉分校博士学位。1985年～1986年在美国加州伯克利数学科学研究院作博士后，1986～1987年在美国麻省理工大学数学系作访问学者，1987年任中国科学院应用数学所教授。先后在美国伯克利（Berkeley），麻省理工大学, 普林斯顿大学数学研究所工作。1991年和1995年成为明尼苏达大学计算机系的副教授和教授。并于1998到1999年之间任职香港城市大学计算机科学系访问教书。 1987-2002年为中国科学院应用数学所研究员。

现任德克萨斯大学达拉斯分校（UTD）计算机系教授，西安交通大学教授。研究方向包括组合优化，计算机网络和计算理论。已经发表论文60多篇，出版了20本书。组合优化杂志和系列书籍《网络理论和应用》的主编，超过15个杂志的编委。1998年获得美国INFORMS的CSTS奖，1993年获得中国自然科学二等奖，1992年获得中国科学院自然科学一等奖。

报告摘要：Abstract: Social networks allow rapid spread of ideas and innovations while the negative information also propagates widely. Once misinformation or rumor is detected, a natural containment method is to introduce a positive cascade competing against the rumor. Given a budget k, the rumor blocking problem asks for k seed users to trigger the spread of the positive cascade such that the number of the rumor-activated users can be minimized. The prior works have shown that the rumor blocking problem can be approximated within a factor of 1-1/e by a classic greedy algorithm combined with Monte Carlo simulation with the running time of , where and are thenumber of users and edges, respectively. Unfortunately, the Monte-Carlo-simulation-based methods are extremely time consuming and the existing algorithms either trade performance guarantees for practical efficiency or vice versa. In this paper, we present a randomized algorithm running in expected time and providing an-approximation with a high probability. The experimentally results have shown that the proposed randomized rumor blocking algorithm is much more efficient than the state-of-the-art method and it is able to find the seed nodes which are effective in limiting the spread of rumor.

太阳集团tyc5997