搜尋散佈謠言者的數學模型

A Mathematical Model for Finding the Culprit Who Spreads Rumors

李姿慧(Zi-Hui Lee)

指導教授 ： 傅恆霖

國立交通大學/理學院/應用數學系暨研究所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00255

摘要

在這篇論文中，我們介紹謠言傳播模型，它的設計是根據一個在流行病學領域著名的易感–感染模型。我們描述在一個圖上散佈謠言的源頭的最大概似估計值並計算預測到散佈謠言的源頭的機率。我們發現：對於路徑的圖形，機率會隨著時間增加趨近到0，其關係為t^(-1/2)；對於正則樹，機率有一個明確的範圍。當d=3，其機率值會隨著時間增加趨近到1/4，此結果已利用隨機圖模型得到。

關鍵字

謠言傳播模型 ； 謠言中心 ； 預測機率

並列摘要

In this thesis, we introduce a rumor spreading model based on the common susceptible-infected (SI) model which is a well known epidemiological model. We describe the maximum likelihood estimators of graphs and we evaluate the detection probabilities of finding the rumor source in d-regular trees. We observe that: For paths, the detection probability of finding the rumor source scales as t^(-1/2), which approaches 0 as t approaches infinity. For regular trees, we find an explicit bound of the detection probabilities of finding the source in d-regular trees. As a consequence, for d=3, the detection probability approaches 1/4, this result has been obtained earlier by using a random graph model.

並列關鍵字

rumor spreading model ； rumor center ； detection probability

參考文獻

[1] N. T. J. Bailey, The Mathematical Theory of Infectious Diseases and its Applications, second edition, Griffin, London, 1975.

[3] C. Moore and M. E. J. Newman, ``Epidemics and percolation in small-world networks", Phys. Rev. E, vol. 61, pp. 5678-5682, May 2000.

[4] M. E. J. Newman, ``The spread of epidemic disease on networks", Phys. Rev. E, vol. 66, pp. 016128, July 2002.

[5] R. Pastor-Satorras and A. Vespignani, ``Epidemic spreading in scale-free networks", Phys. Rev. Lett., vol. 86, pp. 3200-3203, April 2001.

[6] D. Shah and T. Zaman, ``Rumors in a Network: Who's the Culprit?", IEEE Transactions on Information Theory, vol. 57, pp. 5163-5181, August 2011.