Approximation algorithm for partial positive influence problem in social network

Yingli Ran, Zhao Zhang (), Hongwei Du and Yuqing Zhu
Additional contact information
Yingli Ran: Xinjiang University
Zhao Zhang: Zhejiang Normal University
Hongwei Du: Harbin Institute of Technology
Yuqing Zhu: California State University

Journal of Combinatorial Optimization, 2017, vol. 33, issue 2, No 24, 802 pages

Abstract: Abstract Influence problem is one of the central problems in the study of online social networks, the goal of which is to influence all nodes with the minimum number of seeds. However, in the real world, it might be too expensive to influence all nodes. In many cases, it is satisfactory to influence nodes only up to some percent p. In this paper, we study the minimum partial positive influence dominating set (MPPIDS) problem. In fact, we presented an approximation algorithm for a more general problem called minimum partial set multicover problem. As a consequence, the MPPIDS problem admits an approximation with performance ratio $$\gamma H(\Delta )$$ γ H ( Δ ) , where $$H(\cdot )$$ H ( · ) is the Harmonic number, $$\gamma =1/(1-(1-p)\eta ),\eta \approx \Delta ^2/\delta $$ γ = 1 / ( 1 - ( 1 - p ) η ) , η ≈ Δ 2 / δ , and $$\Delta ,\delta $$ Δ , δ are the maximum degree and the minimum degree of the graph, respectively. For power-law graphs, we show that our algorithm has a constant performance ratio.

Keywords: Partial positive influence dominating set; Partial set multicover; Power-law graph; Social network (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0005-0 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:33:y:2017:i:2:d:10.1007_s10878-016-0005-0

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

DOI: 10.1007/s10878-016-0005-0

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 ().