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