This paper presents the formal and computational analysis for designed manipulation of a particular case of adaptable networks. It is increasingly being recognized that many networks, including social networks, can be influenced by designed interventions, such as a deliberate creation of certain connections in the network. We address the problem of finding the cost-effective seeds and potential new connections so that message propagation in an adaptable network with probabilistic cascade propagation is improved. While considering that new connections can be created at a cost, we use the hop-constrained minimum spanning tree (HMST) model to find possible new connections. The HMST model can simultaneously find the seeds and the connection enhancements at minimum cost with performance guarantees on propagation performance. We present new heuristic algorithms for improving the solution efficiency for the HMST problem and provide extensive numerical experiments for random and real world networks that demonstrate significant solution quality improvements with our method. We also analyze how such improvements are translated into propagation improvement through simulation analysis. Our results demonstrate that the implementation of designed interventions in a network can greatly improve propagation performance.
Paper Submission number: 35