Hunt Fern Y
National Institute of Standards and Technology, Gaithersburg, MD 20899.
J Res Natl Inst Stand Technol. 2016 May 10;121:180-195. doi: 10.6028/jres.121.008. eCollection 2016.
In a model of network communication based on a random walk in an undirected graph, what subset of nodes (subject to constraints on the set size), enables the fastest spread of information? The dynamics of spread is described by a process dual to the movement from informed to uninformed nodes. In this setting, an optimal set minimizes the sum of the expected first hitting times (), of random walks that start at nodes outside the set. Identifying such a set is a problem in combinatorial optimization that is probably NP hard. has been shown to be a supermodular and non-increasing set function and fortunately some results on optimization of such functions exist, e.g., in the work of Ilev. In this paper, the problem is reformulated so that the search for solutions to the problem is restricted to a class of optimal and "near" optimal subsets of the graph. We introduce a submodular, non-decreasing rank function , that permits some comparison between the solution obtained by the classical greedy algorithm and one obtained by our methods. The supermodularity and non-increasing properties of are used to show that the rank of our solution is at least times the rank of the optimal set. When the solution has a higher rank than the greedy solution this. constant can be improved to where > 0 is determined a posteriori. The method requires the evaluation of for sets of some fixed cardinality , where is much smaller than the cardinality of the optimal set. Given = (), a class of examples is presented that illustrate the tradeoff between and solution quality .
在基于无向图中随机游走的网络通信模型中，受集合大小限制的哪些节点子集能使信息传播最快？传播动态由从已通知节点到未通知节点的移动对偶过程描述。在此设定下，最优集能使从该集合外节点出发的随机游走的预期首次到达时间（）之和最小化。识别这样一个集合是一个组合优化问题，可能是NP难问题。已证明它是一个超模且非递增的集合函数，幸运的是，关于此类函数的优化有一些结果，例如在伊列夫的工作中。在本文中，对问题进行了重新表述，以便将问题的解搜索限制在图的一类最优和“近”最优子集中。我们引入一个次模、非递减的秩函数，它允许对经典贪心算法得到的解与我们的方法得到的解进行一些比较。利用的超模性和非递增性质表明，我们的解的秩至少是最优集秩的倍。当解的秩高于贪心解时，这个常数可以改进为，其中>0是事后确定的。该方法需要对一些固定基数的集合评估，其中远小于最优集的基数。给定=（），给出了一类示例来说明与解质量之间的权衡。
