On positive influence dominating sets in social networks

Feng Wang; Hongwei Du; Erika Camacho; Kuai Xu; Wonjun Lee; Yan Shi; Shan Shan

doi:10.1016/j.tcs.2009.10.001

On positive influence dominating sets in social networks

Feng Wang^*
, Hongwei Du
, Erika Camacho
, Kuai Xu
, Wonjun Lee
, Yan Shi
, Shan Shan

^*Corresponding author for this work

Arizona State University
Illinois Institute of Technology
Korea University
University of Texas at Dallas

Research output: Contribution to journal › Article › peer-review

87 Scopus citations

Abstract

In this paper, we investigate the positive influence dominating set (PIDS) which has applications in social networks. We prove that PIDS is APX-hard and propose a greedy algorithm with an approximation ratio of H(δ) where H is the harmonic function and δ is the maximum vertex degree of the graph representing a social network.

Original language	English
Pages (from-to)	265-269
Number of pages	5
Journal	Theoretical Computer Science
Volume	412
Issue number	3
DOIs	https://doi.org/10.1016/j.tcs.2009.10.001
State	Published - 21 Jan 2011
Externally published	Yes

Keywords

APX-hard
Dominating set
Positive influence dominating set
Social networks

Access to Document

10.1016/j.tcs.2009.10.001

Cite this

@article{88ffbd8672724d759c3c3bfcae98131f,

title = "On positive influence dominating sets in social networks",

abstract = "In this paper, we investigate the positive influence dominating set (PIDS) which has applications in social networks. We prove that PIDS is APX-hard and propose a greedy algorithm with an approximation ratio of H(δ) where H is the harmonic function and δ is the maximum vertex degree of the graph representing a social network.",

keywords = "APX-hard, Dominating set, Positive influence dominating set, Social networks",

author = "Feng Wang and Hongwei Du and Erika Camacho and Kuai Xu and Wonjun Lee and Yan Shi and Shan Shan",

year = "2011",

month = jan,

day = "21",

doi = "10.1016/j.tcs.2009.10.001",

language = "英语",

volume = "412",

pages = "265--269",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - On positive influence dominating sets in social networks

AU - Wang, Feng

AU - Du, Hongwei

AU - Camacho, Erika

AU - Xu, Kuai

AU - Lee, Wonjun

AU - Shi, Yan

AU - Shan, Shan

PY - 2011/1/21

Y1 - 2011/1/21

N2 - In this paper, we investigate the positive influence dominating set (PIDS) which has applications in social networks. We prove that PIDS is APX-hard and propose a greedy algorithm with an approximation ratio of H(δ) where H is the harmonic function and δ is the maximum vertex degree of the graph representing a social network.

AB - In this paper, we investigate the positive influence dominating set (PIDS) which has applications in social networks. We prove that PIDS is APX-hard and propose a greedy algorithm with an approximation ratio of H(δ) where H is the harmonic function and δ is the maximum vertex degree of the graph representing a social network.

KW - APX-hard

KW - Dominating set

KW - Positive influence dominating set

KW - Social networks

UR - https://www.scopus.com/pages/publications/78650587288

U2 - 10.1016/j.tcs.2009.10.001

DO - 10.1016/j.tcs.2009.10.001

M3 - 文章

AN - SCOPUS:78650587288

SN - 0304-3975

VL - 412

SP - 265

EP - 269

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -

On positive influence dominating sets in social networks

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this