A New Approach to Finding Influential Spreaders in a Network

Suppose we seek a set of nodes in a network that will enable the fastest spread of information in a decentralized communication environment. If communication resources are limited there are constraints on the number of nodes that can be selected. In this presentation, communication is modeled as a random walk on an undirected graph to the set. The desired set minimizes $F(A)$, the sum of the mean first arrival times by walkers starting at nodes outside $A$. The function $F$ is supermodular and non-decreasing and thus it falls into the class of functions that are the subject of intense current research in combinatorial optimization and application areas including the security of sensor networks, machine learning and image analysis. The problem of node selection as originally stated is probably NP hard. We discuss a new approach that leverages properties of the underlying graph to produce exact or approximate solutions of pre-defined quality. The method requires some pre-processing and we provide a rough analysis that quantifies the tradeoff between solution quality and computational effort when $F$ has bounded curvature.

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance.