CATS-Apr-8-2016
Title[edit]
An Algorithm for Identifying Optimal Spreaders in a Random Walk Model of Network Communication
Speaker[edit]
Fern Hunt
Abstract[edit]
In a model of network communication based on a random walk in an undirected graph, what subset of nodes (of some fixed 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 talk, the problem is reformulated so that the search for solutions to the optimization problem is restricted to a class of optimal and "near" optimal subsets of the graph. We introduce a submodular, nondecreasing 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 ratio of the rank of our solution is at least (1-(1/e)) times the rank of the optimal set and in the case our approximation has a higher rank than the greedy solution this constant can be improved.
