Computational aspects of optimal strategic network diffusion

Marcin Waniek, Khaled Elbassioni, Flávio L. Pinheiro, César A. Hidalgo, Aamena Alshamsi

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
JournalTheoretical Computer Science
DOIs
Publication statusE-pub ahead of print - 30 Jan 2020

Fingerprint

Logarithmic
Optimal Solution
Treewidth
Complex networks
Approximation algorithms
Heuristic algorithms
Approximation
Random processes
Dynamic programming
Maximum Degree
Heuristic algorithm
Complex Networks
Dynamic Programming
Approximation Algorithms
Stochastic Processes
Computational complexity
Efficient Algorithms
NP-complete problem
Vertex of a graph

Keywords

  • Complex networks
  • Influence maximization
  • Network contagion
  • Strategic diffusion

Cite this

Waniek, Marcin ; Elbassioni, Khaled ; Pinheiro, Flávio L. ; Hidalgo, César A. ; Alshamsi, Aamena. / Computational aspects of optimal strategic network diffusion. In: Theoretical Computer Science. 2020.
@article{d7cae421088346e891e861abcb5b7fd0,
title = "Computational aspects of optimal strategic network diffusion",
abstract = "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.",
keywords = "Complex networks, Influence maximization, Network contagion, Strategic diffusion",
author = "Marcin Waniek and Khaled Elbassioni and Pinheiro, {Fl{\'a}vio L.} and Hidalgo, {C{\'e}sar A.} and Aamena Alshamsi",
note = "Waniek, M., Elbassioni, K., Pinheiro, F. L., Hidalgo, C. A., & Alshamsi, A. (2020). Computational aspects of optimal strategic network diffusion. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2020.01.027",
year = "2020",
month = "1",
day = "30",
doi = "10.1016/j.tcs.2020.01.027",
language = "English",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

Computational aspects of optimal strategic network diffusion. / Waniek, Marcin; Elbassioni, Khaled; Pinheiro, Flávio L.; Hidalgo, César A.; Alshamsi, Aamena.

In: Theoretical Computer Science, 30.01.2020.

Research output: Contribution to journalArticle

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. https://doi.org/10.1016/j.tcs.2020.01.027

PY - 2020/1/30

Y1 - 2020/1/30

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

U2 - 10.1016/j.tcs.2020.01.027

DO - 10.1016/j.tcs.2020.01.027

M3 - Article

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -