TY - JOUR
T1 - Computational aspects of optimal strategic network diffusion
AU - Waniek, Marcin
AU - Elbassioni, Khaled
AU - Pinheiro, Flávio L.
AU - Hidalgo, César A.
AU - Alshamsi, Aamena
N1 - Waniek, M., Elbassioni, K., Pinheiro, F. L., Hidalgo, C. A., & Alshamsi, A. (2020). Computational aspects of optimal strategic network diffusion. Theoretical Computer Science, 814, 153-168. https://doi.org/10.1016/j.tcs.2020.01.027
PY - 2020/4/24
Y1 - 2020/4/24
N2 - Diffusion on complex networks is often modeled as a stochastic process. Yet, recent work on strategic diffusion emphasizes the decision power of agents [1] 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.
AB - Diffusion on complex networks is often modeled as a stochastic process. Yet, recent work on strategic diffusion emphasizes the decision power of agents [1] 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.
KW - Complex networks
KW - Influence maximization
KW - Network contagion
KW - Strategic diffusion
UR - http://www.scopus.com/inward/record.url?scp=85078763818&partnerID=8YFLogxK
UR - http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=Alerting&SrcApp=Alerting&DestApp=WOS_CPL&DestLinkType=FullRecord&UT=WOS:000524280500012
U2 - 10.1016/j.tcs.2020.01.027
DO - 10.1016/j.tcs.2020.01.027
M3 - Article
AN - SCOPUS:85078763818
VL - 814
SP - 153
EP - 168
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -