We consider the problem of modeling and optimization of cascading, or “domino”-like processes in networks under the presences of uncertainties, such as spread of failures in physical networks, propagation of viruses in computer networks, massive changes in political or consumer preferences in social networks, and so on. To this end, we propose a general model that represents a cascading process in a network as a Markov process on a multiscale graph. Assuming that the parameters governing this Markov process can be modified at certain costs, we investigate the question of optimal resource allocation that would minimize the time by which the cascading process reaches all the nodes in the network. Under some natural assumptions, we derive analytical solutions for an optimal resource allocation that optimizes the spread of the cascade. These expressions explicitly elucidate the importance of network interactions in the context of the rate at which the cascade spreads. We show that an optimal resource allocation can be computed in a strongly polynomial time in terms of the size of the network. Importantly, the obtained solution is expressed via a minimum spanning arborescence on an auxiliary graph and provides a hierarchy that classifies the clusters of the network in terms of their importance with respect to the cascade propagation.
