Whom to befriend to influence people

DOI10.1016/j.tcs.2018.05.030zbMath1444.91174arXiv1611.08687OpenAlexW2548497170MaRDI QIDQ2292915

Adele A. Rescigno, Kangkang Wu, Ugo Vaccaro, Luisa Gargano, Manuel Lafond, Gennaro Cordasco, Lata Narayanan

Publication date: 6 February 2020

Published in: Theoretical Computer Science, Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.08687

zbMATH Keywords

NP-completenessgraphssocial networkssocial networkgreedy algorithmslinear time algorithmsinfluence maximizationminimum links problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

Dual domination problems in graphs ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives ⋮ Groups burning: analyzing spreading processes in community-based networks ⋮ Pervasive domination ⋮ Recommending links through influence maximization ⋮ Target set selection for conservative populations ⋮ How to choose friends strategically ⋮ Whom to befriend to influence people ⋮ Fast and frugal targeting with incentives

Uses Software

• CELF++

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact solutions for latency-bounded target set selection problem on some special families of graphs
• On dynamic monopolies of graphs with general thresholds
• Combinatorial model and bounds for target set selection
• Treewidth governs the complexity of target set selection
• Irreversible conversion of graphs
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Local majorities, coalitions and monopolies in graphs: A review
• Contagious sets in dense graphs
• Recommending links through influence maximization
• Triggering cascades on undirected connected graphs
• Some results on the target set selection problem
• Parameterized approximability of maximizing the spread of influence in networks
• Constant thresholds can make target set selection tractable
• Whom to befriend to influence people
• Influence diffusion in social networks under time window constraints
• Spread of influence in weighted networks under time and budget constraints
• Minimal contagious sets in random regular graphs
• Latency-bounded target set selection in social networks
• A global optimization algorithm for target set selection problems
• Influence Diffusion in Social Networks under Time Window Constraints
• On the Non-progressive Spread of Influence through Social Networks
• On Tractable Cases of Target Set Selection
• Optimizing Spread of Influence in Social Networks via Partial Incentives
• A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks
• On the Approximability of Influence in Social Networks
• Analytical approach to parallel repetition
• Target Set Selection Problem for Honeycomb Networks
• Latency-Bounded Target Set Selection in Social Networks
• Contagious Sets in Expanders
• Maximizing Social Influence in Nearly Optimal Time
• Automata, Languages and Programming
• Variants of Spreading Messages
• How to choose friends strategically

This page was built for publication: Whom to befriend to influence people