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 (96)
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
This page was built for publication: On the Approximability of Influence in Social Networks
