On the Approximability of Influence in Social Networks
From MaRDI portal
Publication:3583313
DOI10.1137/08073617XzbMath1203.68314OpenAlexW2058486861MaRDI QIDQ3583313
Publication date: 27 August 2010
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/08073617x
Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
A parameterized complexity view on collapsing \(k\)-cores, New trends in influence maximization models, Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available, Cooperation through social influence, Discovering small target sets in social networks: a fast and effective algorithm, Vaccinate your trees!, The Vertex Cover Game, Micro- and macromodels of social networks. I: Theory fundamentals, Diffusion centrality: a paradigm to maximize spread in social networks, Target Set Selection in Dense Graph Classes, Optimizing Spread of Influence in Social Networks via Partial Incentives, Information diffusion in social sensing, On the harmless set problem parameterized by treewidth, Least cost influence propagation in (social) networks, A game-theoretic approach for modeling competitive diffusion over social networks, A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks, Generalized threshold processes on graphs, Harmless sets in sparse classes, ON DYNAMIC MONOPOLIES OF GRAPHS WITH PROBABILISTIC THRESHOLDS, Influence Maximization with Latency Requirements on Social Networks, Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem, Optimal Containment of Misinformation in Social Media: A Scenario-Based Approach, Contagious sets in dense graphs, Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems, The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results, Higher order monotonicity and submodularity of influence in social networks: from local to global, Unique key Horn functions, A note on the acquaintance time of random graphs, The maximum time of 2-neighbor bootstrap percolation: complexity results, Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree, Establishing herd immunity is hard even in simple geometric networks, New computational approaches for the power dominating set problem: Set covering and the neighborhoods of zero forcing forts, Weighted target set selection on trees and cycles, Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives, A branch‐and‐cut approach for the least cost influence problem on social networks, On dynamic monopolies of graphs with general thresholds, New ordering methods to construct contagious sets and induced degenerate subgraphs, Target set selection with maximum activation time, Complexity analysis of \(P_3\)-convexity problems on bounded-degree and planar graphs, Solving target set selection with bounded thresholds faster than \(2^n\), Fair Influence Maximization in Large-scale Social Networks Based on Attribute-aware Reverse Influence Sampling, Target set selection on generalized pancake graphs, New bounds for contagious sets, Heuristics for opinion diffusion via local elections, Target set selection in social networks with tiered influence and activation thresholds, Spreading linear triple systems and expander triple systems, Domination and convexity problems in the target set selection model, Multi-level dynamo and opinion spreading, Computing the hull number in \(\Delta \)-convexity, A cutting-plane algorithm for solving a weighted influence interdiction problem, Some results on the target set selection problem, On dynamic monopolies of graphs: the average and strict majority thresholds, Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs, Latency-bounded target set selection in social networks, Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks, Computing the \(\mathcal{P}_3\)-hull number of a graph, a polyhedral approach, Active influence spreading in social networks, Target set selection for conservative populations, Dynamic monopolies for interval graphs with bounded thresholds, Solving Target Set Selection with Bounded Thresholds Faster than 2^n, Approximation algorithms for pricing with negative network externalities, Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees, Deprecation based greedy strategy for target set selection in large scale social networks, A computational study of \(f\)-reversible processes on graphs, Parameterized approximability of maximizing the spread of influence in networks, Reversible iterative graph processes, Constant thresholds can make target set selection tractable, On some tractable and hard instances for partial incentives and target set selection, The \(t\)-latency bounded strong target set selection problem in some kinds of special family of graphs, A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem, Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis, Acquaintance Time of Random Graphs Near Connectivity Threshold, Whom to befriend to influence people, Fast and frugal targeting with incentives, Schedules for marketing products with negative externalities, On the \(P_3\)-hull number of Kneser graphs, Partial immunization of trees, Least-Cost Influence Maximization on Social Networks, Evangelism in Social Networks, A primal-dual algorithm for the minimum partial set multi-cover problem, The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results, Finding Safe Strategies for Competitive Diffusion on Trees, Target set selection parameterized by vertex cover and more, Measuring the influence and amplification of users on social network with unsupervised behaviors learning and efficient interaction-based knowledge graph, On the complexity of reasoning about opinion diffusion under majority dynamics, The complexity of finding harmless individuals in social networks, Influence diffusion in social networks under time window constraints, The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects, The acquaintance time of (percolated) random geometric graphs, Spread of influence in weighted networks under time and budget constraints, Influence Diffusion in Social Networks under Time Window Constraints, On irreversible spread of influence in edge-weighted graphs, On reconfigurability of target sets, A polyhedral approach to least cost influence maximization in social networks, An inclusion hierarchy of irreversible dynamos, Exact solutions for latency-bounded target set selection problem on some special families of graphs
