Hunt Fern Y, Pozo Roldan
National Institute of Standards and Technology, Gaithersburg, MD 20899, USA.
J Res Natl Inst Stand Technol. 2020 Dec 31;125:125036. doi: 10.6028/jres.125.036. eCollection 2020.
We present scalable first hitting time methods for finding a collection of nodes that enables the fastest time for the spread of consensus in a network. That is, given a graph = () and a natural number , these methods find vertices in that minimize the sum of hitting times (expected number of steps of random walks) from all remaining vertices. Although computationally challenging for general graphs, we exploited the characteristics of real networks and utilized Monte Carlo methods to construct fast approximation algorithms that yield near-optimal solutions.
我们提出了可扩展的首次到达时间方法，用于找到一组节点，以实现网络中共识传播的最快时间。也就是说，给定一个图 (G=(V, E)) 和一个自然数 (k)，这些方法在 (V) 中找到 (k) 个顶点，使所有其余顶点的到达时间（随机游走的期望步数）之和最小。尽管对于一般图来说计算具有挑战性，但我们利用了真实网络的特征，并使用蒙特卡罗方法构建了能产生近似最优解的快速近似算法。
