• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

Parameterized approximability of maximizing the spread of influence in networks

Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014), Parameterized approximability of maximizing the spread of influence in networks, Journal of Discrete Algorithms, 27, p. 54-65. 10.1016/j.jda.2014.05.001

Type
Article accepté pour publication ou publié
External document link
https://arxiv.org/abs/1303.6907v2
Date
2014
Journal name
Journal of Discrete Algorithms
Volume
27
Publisher
Elsevier
Pages
54-65
Publication identifier
10.1016/j.jda.2014.05.001
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Chopin, Morgan
Nichterlein, André
Sikora, Florian cc
Abstract (EN)
In this paper, we consider the problem of maximizing the spread of influence through a social network. Given a graph with a threshold value thr(v)thr(v) attached to each vertex v, the spread of influence is modeled as follows: A vertex v becomes “active” (influenced) if at least thr(v)thr(v) of its neighbors are active. In the corresponding optimization problem the objective is then to find a fixed number k of vertices to activate such that the number of activated vertices at the end of the propagation process is maximum. We show that this problem is strongly inapproximable in time f(k)⋅nO(1)f(k)⋅nO(1), for some function f , even for very restrictive thresholds. In the case that the threshold of each vertex equals its degree, we prove that the problem is inapproximable in polynomial time and it becomes r(n)r(n)-approximable in time f(k)⋅nO(1)f(k)⋅nO(1), for some function f, for any strictly increasing function r. Moreover, we show that the decision version parameterized by k is W[1]W[1]-hard but becomes fixed-parameter tractable on bounded degree graphs.
Subjects / Keywords
Parameterized complexity; Approximation; Parameterized approximation; Target set selection; Dynamic monopolies; Spread of information; Viral marketing

Related items

Showing items related by title and author.

  • Thumbnail
    Parameterized Approximability of Maximizing the Spread of Influence in Networks 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2013) Communication / Conférence
  • Thumbnail
    Parameterized Inapproximability of Target Set Selection and Generalizations 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Communication / Conférence
  • Thumbnail
    Parameterized Inapproximability of Target Set Selection and Generalizations 
    Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
  • Thumbnail
    The Complexity of Finding Harmless Individuals in Social Networks 
    Bazgan, Cristina; Chopin, Morgan (2014) Article accepté pour publication ou publié
  • Thumbnail
    Parameterized Complexity of the Firefighter Problem 
    Bazgan, Cristina; Chopin, Morgan; Fellows, Michael R. (2011) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo