Anzeige
Erschienen in:
05.03.2016
Approximation algorithm for partial positive influence problem in social network
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2017
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 )\), 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.