Identification and Asymptotic Localization of Rumor Sources Using the Method of Types
Identification and Asymptotic Localization of Rumor Sources Using the Method of Types
复制标题
DOI：
10.1109/tnse.2019.2911275
复制
发表时间：
2020-07
影响因子：
6.6
通讯作者：
Himaja Kesavareddigari;Sam Spencer;A. Eryilmaz;R. Srikant
中科院分区：
文献类型：
--
作者：
Himaja Kesavareddigari;Sam Spencer;A. Eryilmaz;R. Srikant
我们感兴趣的是在树网络上识别谣言源。我们开始与扩展星星网络下的SI感染模型与指数等待时间。我们提出并分析了类型中心，一个高度听话的近似ML源估计，使用类型的方法获得。我们的经验表明，这种近似ML估计是精确的一些小的测试用例。我们证明了在大型网络上，近似误差在感染大小上至多是对数，提供了高效的源识别（特别是与类似问题的准确性相比，例如线性网络中的$\mathcal {O}（\sqrt{n}）$最佳准确性估计）。我们还表明，在扩展的星星网络上，谣言中心的类型和谣言中心的定性性质是不同的。我们进一步提出了一种基于启发式的将这种方法推广到树的方法：相对叶子计数算法。在对规则树和非规则树的模拟中，类型中心的性能与谣言中心性（对于$d$-规则树是最佳的）具有竞争力，同时需要更少的计算时间。除了提供更快（有时更准确）的替代方案外，我们的方法还可以与谣言中心一起使用，以不到总计算时间的两倍来改善结果。
We are interested in identifying a rumor source on a tree network. We begin with extended star networks under the SI infection model with exponential waiting times. We present and analyze the types center, a highly tractable approximation of the ML source estimate, obtained using the method of types. We empirically show that this approximate ML estimator is exact for some small test cases. We prove that the approximation error is at most logarithmic in infection size on large networks, providing highly efficient source identification (especially compared to the accuracy in similar problems, such as the $\mathcal {O}(\sqrt{n})$ best possible accuracy estimate in a line network). We also show that the qualitative properties of the types and rumor centers are different on extended star networks. We further propose a heuristic-based generalization of this approach to trees: the relative-leaf counting algorithm. In simulations on regular and nonregular trees, types center's performance is competitive with rumor centrality (which is optimal for $d$-regular trees), while requiring less computation time. In addition to providing a faster (and sometimes more accurate) alternative on its own, our approach could potentially be used with rumor centrality to improve results with less than twice the total computation time.