Approximation algorithm for partial positive influence problem in social network

详细信息    查看全文

• 作者：Yingli Ran ; Zhao Zhang ; Hongwei Du ; Yuqing Zhu
• 关键词：Partial positive influence dominating set ; Partial set multicover ; Power ; law graph ; Social network
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：33
• 期：2
• 页码：791-802
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

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 )\), where \(H(\cdot )\) is the Harmonic number, \(\gamma =1/(1-(1-p)\eta ),\eta \approx \Delta ^2/\delta \), 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.