Computational Aspects of Optimal Strategic Network Diffusion
arXiv:1809.03141 · doi:10.1016/j.tcs.2020.01.027
Abstract
Diffusion on complex networks is often modeled as a stochastic process. Yet, recent work on strategic diffusion emphasizes the decision power of agents and treats diffusion as a strategic problem. Here we study the computational aspects of strategic diffusion, i.e., finding the optimal sequence of nodes to activate a network in the minimum time. We prove that finding an optimal solution to this problem is NP-complete in a general case. To overcome this computational difficulty, we present an algorithm to compute an optimal solution based on a dynamic programming technique. We also show that the problem is fixed parameter-tractable when parametrized by the product of the treewidth and maximum degree. We analyze the possibility of developing an efficient approximation algorithm and show that two heuristic algorithms proposed so far cannot have better than a logarithmic approximation guarantee. Finally, we prove that the problem does not admit better than a logarithmic approximation, unless P=NP.
arXiv comment21 pages, 5 figures
References in corpus (10)
- Epidemic spreading in scale-free networks
- The Product Space Conditions the Development of Nations
- The Dynamics of Viral Marketing
- Influence maximization in complex networks through optimal percolation
- Adaptive Influence Maximization in Dynamic Social Networks
- Optimal diversification strategies in the networks of related products and of related research areas
- Consensus and Polarisation in Competing Complex Contagion Processes
- Scalable Methods for Adaptively Seeding a Social Network
- Shooting High or Low: Do Countries Benefit from Entering Unrelated Activities?
- Balancing Speed and Coverage by Sequential Seeding in Complex Networks