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

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

76 Citations (Scopus)

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
Publication status	Published - 2011 Jan 21

Bibliographical note

Funding Information:
✩ This research was jointly supported by MEST, Korea under WCU (R33-2008-000-10044-0), and National Science Foundation of USA under grants

Keywords

APX-hard
Dominating set
Positive influence dominating set
Social networks

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2009.10.001

Cite this

@article{4bcf708a43864f6b92f41b3e7f47ab10,

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",

note = "Funding Information: ✩ This research was jointly supported by MEST, Korea under WCU (R33-2008-000-10044-0), and National Science Foundation of USA under grants",

year = "2011",

month = jan,

day = "21",

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

language = "English",

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

N1 - Funding Information: ✩ This research was jointly supported by MEST, Korea under WCU (R33-2008-000-10044-0), and National Science Foundation of USA under grants

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 - http://www.scopus.com/inward/record.url?scp=78650587288&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2009.10.001

DO - 10.1016/j.tcs.2009.10.001

M3 - Article

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

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this