報告題目：An Efficient Randomized Algorithm for Rumor Blocking
報告人：堵丁柱 教授
單位：德克薩斯大學達拉斯分校
報告時間：2017年4月24日（周一）下午15:00-17:00
報告地點：逸夫科教樓408會議室
報告人簡介：1982年獲中國科學院碩士學位，1985年獲美國加利福利亞大學圣巴巴拉分校博士學位。1985年～1986年在美國加州伯克利數(shù)學科學研究院作博士后，1986～1987年在美國麻省理工大學數(shù)學系作訪問學者，1987年任中國科學院應(yīng)用數(shù)學所教授。先后在美國伯克利（Berkeley），麻省理工大學, 普林斯頓大學數(shù)學研究所工作。1991年和1995年成為明尼蘇達大學計算機系的副教授和教授。并于1998到1999年之間任職香港城市大學計算機科學系訪問教書。 1987-2002年為中國科學院應(yīng)用數(shù)學所研究員。
現(xiàn)任德克薩斯大學達拉斯分校（UTD）計算機系教授，西安交通大學教授。研究方向包括組合優(yōu)化，計算機網(wǎng)絡(luò)和計算理論。已經(jīng)發(fā)表論文60多篇，出版了20本書。組合優(yōu)化雜志和系列書籍《網(wǎng)絡(luò)理論和應(yīng)用》的主編，超過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
TOP
