On the approximability of positive influence dominating set in social networks

Thang N. Dinh (), Yilin Shen (), Dung T. Nguyen () and My T. Thai ()
Additional contact information
Thang N. Dinh: University of Florida
Yilin Shen: University of Florida
Dung T. Nguyen: University of Florida
My T. Thai: University of Florida

Journal of Combinatorial Optimization, 2014, vol. 27, issue 3, No 5, 487-503

Abstract: Abstract In social networks, there is a tendency for connected users to match each other’s behaviors. Moreover, a user likely adopts a behavior, if a certain fraction of his family and friends follows that behavior. Identifying people who have the most influential effect to the others is of great advantages, especially in politics, marketing, behavior correction, and so on. Under a graph-theoretical framework, we study the positive influence dominating set (PIDS) problem that seeks for a minimal set of nodes $\mathcal{P}$ such that all other nodes in the network have at least a fraction ρ>0 of their neighbors in $\mathcal{P}$ . We also study a different formulation, called total positive influence dominating set (TPIDS), in which even nodes in $\mathcal{P}$ are required to have a fraction ρ of neighbors inside $\mathcal{P}$ . We show that neither of these problems can be approximated within a factor of (1−ϵ)lnmax{Δ,|V|1/2}, where Δ is the maximum degree. Moreover, we provide a simple proof that both problems can be approximated within a factor lnΔ+O(1). In power-law networks, where the degree sequence follows a power-law distribution, both problems admit constant factor approximation algorithms. Finally, we present a linear-time exact algorithms for trees.

Keywords: Hardness of approximation; Approximation algorithm; Social networks; Information diffusion (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9530-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:27:y:2014:i:3:d:10.1007_s10878-012-9530-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9530-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().