The Structure of Optimal and Near Optimal Target Sets in Consensus Models

We consider the problem of identifying a subset of nodes in a network that will enable the fastest spread of information in a decentralized environment.In a model of communication based on a random walk on an undirected graph, the optimal set over all sets of the same or smaller cardinality minimizes the sum of the mean first arrival times to the set by walkers starting at nodes outside the set. The problem originates from the study of the spread of information or consensus in a network and was introduced in this form by V.Borkar et al. in 2010. More generally, the work of A. Clark et al. in 2012 showed that estimating the fastest rate of convergence to consensus of so-called leader follower systems leads to a consideration of the same optimization problem. The set function F to be minimized is supermodular and therefore the greedy algorithm is commonly used to construct optimal sets or their approximations. In this paper, the problem is reformulated so that the search for solutions is restricted to optimal and near optimal subsets of the graph. We prove sufficient conditions for the existence of a greedoid structure that contains feasible optimal and near optimal sets. It is therefore possible we conjecture, to search for optimal or near optimal sets by local moves in a stepwise manner to obtain near optimal sets that are better approximations than the factor (1−1/e) degree of optimality guaranteed by the use of the greedy algorithm. A simple example illustrates aspects of the method. 1 Random Walk Consensus Model Given a connected graph G = (V,E), with vertices or nodes V and edges E, we imagine a random walker situated at a node i ∈ V, moving to another node j ∈ V in a single discrete time step. The choice of j is random and has probability, Prob{i → j} = pij> 0, if (i, j) ∈ E pij = 0 otherwise. (1) The matrix P = (pij)i,j=1···N is the transition matrix of a Markov chain which in this paper, is assumed to be irreducible and aperiodic ([7]). N is the number of nodes and as in [1] the spread of information is described in terms of a process that is dual to the movement from informed to uninformed nodes. A random walk begins outside a pre-determined set A of informed target nodes 1 ar X i