Optimization of Cascading Processes in Arbitrary Networks with Stochastic Interactions

We consider the problem of optimal propagation of cascades in a network, where the propagation process depends on the values that a decision-maker assigns to the network and independent influence rates. Assuming that there are costs associated with changing the values of these rates, we investigate the question of resource allocation that minimizes the time by which the cascading process reaches all nodes. To this end, we propose a model that represents the cascading process in the network as a continuous time Markov chain (CTMC). We show how the propagation problem can be framed as an eigenvalue optimization problem on the generator of the CTMC. In turn, this problem is successively transformed into a maximum minimum cut problem and into a generalized maximum flow problem on a linearly-sized auxiliary graph. Therefore, the optimization problem can be solved in strongly polynomial time in terms of the size of the network. In addition, whenever there are no preexisting influence rates, the problem can also be transformed into the problem of finding a minimum spanning arborescence on a similar auxiliary graph. In this setting the optimal solution provides a hierarchy that classifies the nodes in terms of their importance to the cascade propagation.