Abstract
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 A minimizes the sum of the expected first hitting times F(A), 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. F 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 F are used to show that the rank of our solution is at least (1 - 1/) times the rank of the optimal set. When the solution has a higher rank than the greedy solution this. constant can be improved to (1 + χ)(1 - 1/) where χ > 0 is determined a posteriori. The method requires the evaluation of F for sets of some fixed cardinality m, where m is much smaller than the cardinality of the optimal set. Given ν = ρ(A), a class of examples is presented that illustrate the tradeoff between m and solution quality ν.