On the Approximability of Influence in Social Networks
From MaRDI portal
Publication:3583313
DOI10.1137/08073617XzbMath1203.68314MaRDI 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
91D30: Social networks; opinion dynamics
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Finding Safe Strategies for Competitive Diffusion on Trees, The Vertex Cover Game, Target Set Selection in Dense Graph Classes, Influence Maximization with Latency Requirements on Social Networks, Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem, Solving Target Set Selection with Bounded Thresholds Faster than 2^n, Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis, 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, A branch‐and‐cut approach for the least cost influence problem on social networks, New ordering methods to construct contagious sets and induced degenerate subgraphs, Target set selection with maximum activation time, Fair Influence Maximization in Large-scale Social Networks Based on Attribute-aware Reverse Influence Sampling, Heuristics for opinion diffusion via local elections, Target set selection in social networks with tiered influence and activation thresholds, Exact solutions for latency-bounded target set selection problem on some special families of graphs, Micro- and macromodels of social networks. I: Theory fundamentals, Diffusion centrality: a paradigm to maximize spread in social networks, Information diffusion in social sensing, A note on the acquaintance time of random graphs, On dynamic monopolies of graphs with general thresholds, New bounds for contagious sets, On dynamic monopolies of graphs: the average and strict majority thresholds, Approximation algorithms for pricing with negative network externalities, Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees, Reversible iterative graph processes, Schedules for marketing products with negative externalities, On the complexity of reasoning about opinion diffusion under majority dynamics, 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, Complexity analysis of \(P_3\)-convexity problems on bounded-degree and planar graphs, Discovering small target sets in social networks: a fast and effective algorithm, Least cost influence propagation in (social) networks, A game-theoretic approach for modeling competitive diffusion over social networks, Contagious sets in dense graphs, The maximum time of 2-neighbor bootstrap percolation: complexity results, Computing the \(\mathcal{P}_3\)-hull number of a graph, a polyhedral approach, Active influence spreading in social networks, Dynamic monopolies for interval graphs with bounded thresholds, Deprecation based greedy strategy for target set selection in large scale social networks, A computational study of \(f\)-reversible processes on graphs, Some results on the target set selection problem, 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, On the \(P_3\)-hull number of Kneser graphs, 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 reconfigurability of target sets, A polyhedral approach to least cost influence maximization in social networks, On the harmless set problem parameterized by treewidth, Harmless sets in sparse classes, Target set selection on generalized pancake graphs, Spreading linear triple systems and expander triple systems, Computing the hull number in \(\Delta \)-convexity, Target set selection for conservative populations, Parameterized approximability of maximizing the spread of influence in networks, Constant thresholds can make target set selection tractable, A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem, Whom to befriend to influence people, Fast and frugal targeting with incentives, Partial immunization of trees, A primal-dual algorithm for the minimum partial set multi-cover problem, 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, An inclusion hierarchy of irreversible dynamos, Generalized threshold processes on graphs, Bounds and extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives, A cutting-plane algorithm for solving a weighted influence interdiction problem, 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, Cooperation through social influence, Vaccinate your trees!, Generalizations, formulations and subgradient based heuristic with dynamic programming procedure for target set selection problems, Higher order monotonicity and submodularity of influence in social networks: from local to global, Unique key Horn functions, Solving target set selection with bounded thresholds faster than \(2^n\), Domination and convexity problems in the target set selection model, Acquaintance Time of Random Graphs Near Connectivity Threshold, Evangelism in Social Networks, The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results, Influence Diffusion in Social Networks under Time Window Constraints, ON DYNAMIC MONOPOLIES OF GRAPHS WITH PROBABILISTIC THRESHOLDS, Optimal Containment of Misinformation in Social Media: A Scenario-Based Approach, The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results, Multi-level dynamo and opinion spreading, Least-Cost Influence Maximization on Social Networks, On irreversible spread of influence in edge-weighted graphs, Optimizing Spread of Influence in Social Networks via Partial Incentives, A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks
