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

Abstract

在這篇論文中，我們介紹謠言傳播模型，它的設計是根據一個在流行病學領域著名的易感–感染模型。我們描述在一個圖上散佈謠言的源頭的最大概似估計值並計算預測到散佈謠言的源頭的機率。我們發現：對於路徑的圖形，機率會隨著時間增加趨近到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.