  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), enable
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.
  In this paper,the problem is reformulated so that the search for solutions is
restricted to a class of optimal and "near" optimal subsets of the graph. We
introduce a submodular, non-decreasing rank function $\rho$, 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-\frac{1}{e})$ 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-\frac{1}{e})(1+\chi)$ where $\chi >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. When $F$ has
forward elemental curvature $\kappa$, we can provide a rough description of the
trade-off between solution quality and computational effort $m$ in terms of
$\kappa$.
