A Spectral Decomposition Heuristic for Near Optimal Capture Sets In Consensus Models

Given a network G=(V,E), consider the problem of selecting a subset of nodes, A, of a fixed size, k, such that the sum expected walk length from V to A, or hitting time, is minimized. This study is motivated by modeling communication models as a random walk on a weighted loopless directed graph where the desired information is observed when a random walk reaches the chosen set. The origin of this problem is found in the study of how information or ``consensus" flows through a network, introduced by Borkar et al. in 2010. In general, this problem is NP-hard and as a result problems posed on large networks become quickly infeasible. The objective function of interest F(A) is supermodular and therefore, a greedy technique provides a ( 1 - 1/e) approximation to the optimal solution. While the greedy technique provides a guaranteed approximation it comes at the cost of being O(k n^4). This work develops the Spectral Decomposition heuristic for this problem based on spectral clustering. In general, this reduces the model to O(n^4/k^3). Analysis of this technique is completed on the Stochastic Block Model, and under the appropriate assumptions the method reduces to O(n^2.5). This approach is compared to previous approaches, including the greedy method, centrality measures, and more recent near-optimal subset techniques. The Spectral Decomposition heuristic greatly improves on the run-time of the greedy and near-optimal subset method, while maintaining quality of approximation. While the method cannot compete with the complexity of the centrality measures, frequently it greatly outperforms the approximation. Optimality is observed through two metrics; the value of the objective function and the value of the Perron-Frobenius eigenvalue of the Markov submatrix resulting from the capture set. Multiple examples illustrate the method and larger than prior networks are explored