Optimal Spread in Network 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 communication 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. This problem was previously considered in [1] and in the context of consensus models in [3]. The set function F to be minimized is supermodular and therefore the greedy algorithm is a principal tool used for constructing optimal sets or their approximations. However the resulting set is not always optimal and the degree of optimality although guaranteed is limited by the factor (1 − 1/e). In this paper, the problem is reformulated by limiting the scope of sets to be considered based on specific structural features of the graph. We seek solutions of the optimization problem or approximations of solutions with cardinality p < K that are subsets of solutions of the optimization problem for cardinality K. Our main result is a theorem that gives sufficient conditions for a vertex cover to contain subsets that are optimal or near optimal approximations. Here optimality of a set is defined in terms of its F value relative to the F value of the solution of the problem for cardinality K. Each optimal or near optimal subset can be constructed element by element. Optimal and near optimal sets are solution candidates for the original problem. Although we do not specify an algorithm employing this methodology, greedoid theory is used to construct a greedoid graph whose nodes are optimal and near optimal feasible sets. This structure is amenable to the stepwise construction of approximations and local search for improvements by a sequence of moves to ”adjacent ” nodes. Thus this paper suggests that the connection between the network graph topology and the topology of the greedoid graph is a useful line of inquiry in the search for new approaches to the problem of optimal spread