scientific article

DOI10.4086/toc.2015.v011a004zbMath1337.91069OpenAlexW2402962589MaRDI QIDQ2941641

David Kempe, Éva Tardos, Jon M. Kleinberg

Publication date: 21 August 2015

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2015.v011a004

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

diffusion submodular function social networks influence approximation algorithms viral marketing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Submodular Maximization Subject to a Knapsack Constraint Under Noise Models, The Limitations of Optimization from Samples, Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree, Average Sensitivity of Graph Algorithms, Centrality measures in networks, CasTformer: a novel cascade transformer towards predicting information diffusion, Establishing herd immunity is hard even in simple geometric networks, Immune sets in monotone infection rules. Characterization and complexity, Immunization in the threshold model: a parameterized complexity study, Misinformation influence minimization problem based on group disbanded in social networks, Groups burning: analyzing spreading processes in community-based networks, Flight from COVID-19: multiscale and multilayer analyses of the epidemic-induced network adaptations, On approximating the rank of graph divisors, Percolation and epidemic processes in one-dimensional small-world networks (extended abstract), Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints, Target set selection with maximum activation time, Maximizing approximately non-$k$-submodular monotone set function with matroid constraint, Competition-based generalized self-profit maximization in dual-attribute networks, Contagion risks and security investment in directed networks, NP-Hardness and Approximation Algorithms for Iterative Pricing on Social Networks with Externalities, Locality of random digraphs on expanders, Opinion influence maximization problem in online social networks based on group polarization effect, Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity, Influence maximization in social networks using role-based embedding, Rumor transmission in online social networks under Nash equilibrium of a psychological decision game, Modeling information diffusion in social networks with ordinary linear differential equations, Improved deterministic algorithms for non-monotone submodular maximization, Robust networked multiagent optimization: designing agents to repair their own utility functions, Better bounds on the adaptivity gap of influence maximization under full-adoption feedback, Fast convergence of optimistic gradient ascent in network zero-sum extensive form games, Streaming algorithms for maximizing the difference of submodular functions and the sum of submodular and supermodular functions, Streaming submodular maximization with the chance constraint, Bicriteria algorithms for maximizing the difference between submodular function and linear function under noise, Profit maximization for multiple products in community-based social networks, Heuristics for opinion diffusion via local elections, Asynchronous Semianonymous Dynamics over Large-Scale Networks, Unnamed Item, Target set selection in social networks with tiered influence and activation thresholds, Targeting in social networks with anonymized information, Information diffusion-aware likelihood maximization optimization for community detection, IM2Vec: representation learning-based preference maximization in geo-social networks, Game-theoretic modeling and analysis of cyberbullying spreading on OSNs, Unnamed Item, Unnamed Item, An Asynchronous Linear-Threshold Innovation Diffusion Model, Order optimal information spreading using algebraic gossip, Submodular Optimization with Contention Resolution Extensions., Eigenvector-Based Centrality Measures for Temporal Networks, Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis, Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint, An exact algorithm for robust influence maximization, Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem, How to Burn a Graph, A Theory of Network Security: Principles of Natural Selection and Combinatorics, Multi-Player Diffusion Games on Graph Classes, Time bounded adaptive information coverage in social networks, Pairwise influences in dynamic choice: network-based model and application, Fuzzification of Zero Forcing Process, A New Fuzzy Propagation Model for Influence Maximization in Social Networks, Complexity of equilibrium in competitive diffusion games on social networks, Influence maximization in social networks under an independent cascade-based model, A parameterized complexity view on collapsing $k$-cores, Streaming algorithms for robust submodular maximization, Bounded confidence dynamics and graph control: enforcing consensus, Influence maximization problem: properties and algorithms, Burning grids and intervals, Parallelization of game theoretic centrality algorithms, Discovering small target sets in social networks: a fast and effective algorithm, Identifying and tracking topic-level influencers in the microblog streams, Sequential decision aggregation with social pressure, Least cost influence propagation in (social) networks, A game-theoretic approach for modeling competitive diffusion over social networks, Social structure optimization in team formation, A tight upper bound on acquaintance time of graphs, Contagious sets in dense graphs, The complexity of influence maximization problem in the deterministic linear threshold model, A note on the acquaintance time of random graphs, Staying safe and visible via message sharing in online social networks, On dynamic monopolies of graphs with general thresholds, Competitivity groups on social network sites, Combinatorial model and bounds for target set selection, Welfare maximization with friends-of-friends network externalities, On dissemination thresholds in regular and irregular graph classes, New bounds for contagious sets, On general threshold and general cascade models of social influence, A note on maximizing the spread of influence in social networks, Triggering cascades on undirected connected graphs, Actively learning to infer social ties, Learning influence from heterogeneous social networks, Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids, Retracted article: ``A distance vector similarity metric for complex networks, Efficient influence maximization under TSCM: a suitable diffusion model in online social networks, The firefighter problem with more than one firefighter on trees, PASS approximation: a framework for analyzing and designing heuristics, Polynomial time approximation scheme for $t$-latency bounded information propagation problem in wireless networks, Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results, On dynamic monopolies of graphs: the average and strict majority thresholds, Beyond rankings: comparing directed acyclic graphs, Treewidth governs the complexity of target set selection, Informational influence and informational control models in social networks, Data mining of social networks represented as graphs, Targeted influential nodes selection in location-aware social networks, Active influence spreading in social networks, Recommending links through influence maximization, Multipolar robust optimization, A nature-inspired influence propagation model for the community expansion problem, An individual-based model of information diffusion combining friends' influence, Influence minimization in linear threshold networks, Potential induced random teleportation on finite graphs, Containment of rumor spread by selecting immune nodes in social networks, Locating the contagion source in networks with partial timestamps, Measuring and moderating opinion polarization in social networks, Dynamic monopolies for interval graphs with bounded thresholds, Assignment games with conflicts: robust price of anarchy and convergence results via semi-smoothness, Marketing impact on diffusion in social networks, A two-stage stochastic programming approach for influence maximization in social networks, Measuring the impact of MVC attack in large complex networks, Approximation algorithms for pricing with negative network externalities, An efficient algorithm for link prediction in temporal uncertain social networks, The complexity of finding effectors, Integer programming approach to static monopolies in graphs, Maximizing misinformation restriction within time and budget constraints, Reversible iterative graph processes, Dynamic epistemic logics of diffusion and prediction in social networks, On some tractable and hard instances for partial incentives and target set selection, TIFIM: a two-stage iterative framework for influence maximization in social networks, Irreversible conversion of graphs, Galaxy cutsets in graphs, Election control through social influence with unknown preferences, A non-extendibility certificate for submodularity and applications, Robust budget allocation via continuous submodular functions, Minimizing the expected complete influence time of a social network, On strict submodularity of social influence, The $t$-latency bounded strong target set selection problem in some kinds of special family of graphs, Discount allocation for cost minimization in online social networks, Optimization of stochastic virus detection in contact networks, A note on competitive diffusion through social networks, Large-scale influence maximization via maximal covering location, Inequity aversion pricing over social networks: approximation algorithms and hardness results, Community-based rumor blocking maximization in social networks, Facets of the dynamic monopoly polytope: linear ordering formulation, Maximizing monotone submodular functions over the integer lattice, Submodular unsplittable flow on trees, Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint, Generalized budgeted submodular set function maximization, Maximizing positive influence in competitive social networks: a trust-based solution, Attribute based diversification of seeds for targeted influence maximization, Blocking adversarial influence in social networks, Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph, Pareto optimization for subset selection with dynamic cost constraints, An exact cutting plane method for $k$-submodular function maximization, Some bounds for the $Z$-eigenpair of nonnegative tensors, On the influence maximization problem and the percolation phase transition, Bounding the inefficiency of compromise in opinion formation, Estimating user influence ranking in independent cascade model, Adaptive rewiring of random neural networks generates convergent-divergent units, Ranking by inspiration: a network science approach, On the complexity of reasoning about opinion diffusion under majority dynamics, Social network discovery by mining spatio-temporal events, The Small Community Phenomenon in Networks: Models, Algorithms and Applications, Streaming Algorithms for Submodular Function Maximization, Normalization Phenomena in Asynchronous Networks, Hardness Results for Seeding Complex Contagion with Neighborhoods, Competitive Diffusion on Weighted Graphs, Algorithmic Aspects of Private Bayesian Persuasion., Graph representation learning for popularity prediction problem: A survey, A survey of graph burning, Target Set Selection in Dense Graph Classes, Optimizing Spread of Influence in Social Networks via Partial Incentives, Adaptive Rumor Spreading, Submodular Unsplittable Flow on Trees, Unnamed Item, Optimizing Network Topology for Cascade Resilience, Computing Critical Nodes in Directed Graphs, A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks, Edge Deletion Algorithms for Minimizing Spread in SIR Epidemic Models, Fairness in Influence Maximization through Randomization, Unnamed Item, Semantics-aware influence maximization in social networks, Fortification Against Cascade Propagation Under Uncertainty, Structured Robust Submodular Maximization: Offline and Online Algorithms, Price of Anarchy for the N-Player Competitive Cascade Game with Submodular Activation Functions, An L p Norm Relaxation Approach to Positive Influence Maximization in Social Network under the Deterministic Linear Threshold Model, Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem, Stochastic-lazier-greedy algorithm for monotone non-submodular maximization, Edge instability: a critical parameter for the propagation and robustness analysis of large networks, Optimal Containment of Misinformation in Social Media: A Scenario-Based Approach, A Fast Greedy Algorithm for the Critical Node Detection Problem, Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotoneSubmodular Maximization, Influence analysis: A survey of the state-of-the-art, Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint, Higher order monotonicity and submodularity of influence in social networks: from local to global, Multi-player Diffusion Games on Graph Classes, Rumors Spread Slowly in a Small-World Spatial Network, Multi-winner Election Control via Social Influence, Network Creation Games with Local Information and Edge Swaps, Social network analysis and applications: A review of the broad research aspects of social network structure, Online risk-averse submodular maximization, Seeding with Costly Network Information, Relationship externalities, Streaming submodular maximization under $d$-knapsack constraints, Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback, Unnamed Item, Solving target set selection with bounded thresholds faster than $2^n$, Complex Contagions on Configuration Model Graphs with a Power-Law Degree Distribution, Word of Mouth: Rumor Dissemination in Social Networks, A central limit theorem for diffusion in sparse random graphs, Targeted influence maximization in complex networks, Domination and convexity problems in the target set selection model, A general higher-order supracentrality framework based on motifs of temporal networks and multiplex networks, Unnamed Item, Network Essence: PageRank Completion and Centrality-Conforming Markov Chains, Multi-level dynamo and opinion spreading, The Zero Forcing Number of Graphs, Adaptive Submodular Ranking and Routing, Probabilistic Partial Set Covering with an Oracle for Chance Constraints, Influence Maximization in Social Networks, Coalition formation in social environments with logic-based agents1, Tunable Eigenvector-Based Centralities for Multiplex and Temporal Networks, Solving Target Set Selection with Bounded Thresholds Faster than 2^n, Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition, Unnamed Item, Unnamed Item, Approximating Robust Parameterized Submodular Function Maximization in Large-Scales, Unnamed Item, Unnamed Item, Invertibility of graph translation and support of Laplacian Fiedler vectors, Diffusion of Defaults Among Financial Institutions, Precautionary rumor containment via trustworthy people in social networks, Acquaintance Time of Random Graphs Near Connectivity Threshold, Unnamed Item, PageRank Beyond the Web, Spectral bounds in random graphs applied to spreading phenomena and percolation, A classification for community discovery methods in complex networks, Non‐negative residual matrix factorization: problem definition, fast solutions, and applications, The Routing of Complex Contagion in Kleinberg’s Small-World Networks, Absorption time of the Moran process, Evangelism in Social Networks, Opinion Forming in Erdös-Rényi Random Graph and Expanders, A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint, A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints, Maximizing Influence in Competitive Environments: A Game-Theoretic Approach, Finding Rumor Sources on Random Trees, Voter Model on Signed Social Networks, Finding Safe Strategies for Competitive Diffusion on Trees, On the Power of Planned Infections in Networks, Some algebraic hyperstructures related to zero forcing sets and forcing digraphs, Stability and Recovery for Independence Systems, Defending Planar Graphs against Star-Cutsets, Schemes of propagation models and source estimators for rumor source detection in online social networks: A short survey of a decade of research, k-Submodular maximization with two kinds of constraints, Parameter Estimation in Epidemic Spread Networks Using Limited Measurements, VAIM: Visual Analytics for Influence Maximization, A Nash Equilibrium Based Algorithm for Mining Hidden Links in Social Networks, Influence Diffusion in Social Networks under Time Window Constraints, Unnamed Item, On irreversible spread of influence in edge-weighted graphs, ChoiceGAPs: Competitive Diffusion as a Massive Multi-player Game in Social Networks, Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model, A graph theoretical approach to the firebreak locating problem, Strategyproof mechanisms for competitive influence in networks, Influence percolation method for overlapping community detection, An approximate marginal spread computation approach for the budgeted influence maximization with delay, Multi-attribute based influence maximization in social networks: algorithms and analysis, Vaccinate your trees!, A new greedy strategy for maximizing monotone submodular function under a cardinality constraint, Ranking with submodular functions on a budget, The modeling and analysis of the word-of-mouth marketing, Reasoning in large games with unboundedly many players, A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions, Maximize the probability of union-influenced in social networks, Generalized self-profit maximization in attribute networks, Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice, Influence control method on directed weighted signed graphs with deterministic causality, Streaming algorithms for maximizing DR-submodular functions with $d$-knapsack constraints, Fixed observation time-step: adaptive influence maximization, Measured continuous greedy with differential privacy, Multi-attribute based influence maximization in social networks, On the harmless set problem parameterized by treewidth, Parameterized complexity of immunization in the threshold model, Maximizing a non-decreasing non-submodular function subject to various types of constraints, Positive influence maximization in signed social networks under independent cascade model, SFTRD: A novel information propagation model in heterogeneous networks: modeling and restraining strategy, The neighborhood role in the linear threshold rank on social networks, A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems, Election control through social influence with voters' uncertainty, Maximizing $k$-submodular functions under budget constraint: applications and streaming algorithms, Harmless sets in sparse classes, Maximizing influence in social networks by distinguishing the roles of seeds, Consensus reaching with the externality effect of social network for three-way group decisions, On the conditions for the passage of a signal through a chain of asynchronous threshold elements, Competitive profit maximization in social networks, The differential of the line graph $\mathcal{L} (G)$, Interaction-aware influence maximization and iterated sandwich method, Innovation adoption and collective experimentation, Centralized and decentralized rumor blocking problems, Burning a graph is hard, A typology of social capital and associated network measures, Privacy-constrained network formation, Research progress in enhancing the controllability of complex networks, Group conformity in social networks, Influence prediction for continuous-time information propagation on networks, A variation of DS decomposition in set function optimization, KATZ centrality with biogeography-based optimization for influence maximization problem, Competitive and collaborative influence in social networks, Maximizing profit of multiple adoptions in social networks with a martingale approach, Dynamic monopolies and feedback vertex sets in hexagonal grids, Spreading linear triple systems and expander triple systems, Activity preserving graph simplification, A discount strategy in word-of-mouth marketing, Influence maximization by rumor spreading on correlated networks through community identification, CrawISN: community-aware data acquisition with maximum willingness in online social networks, Information diffusion on the iterated local transitivity model of online social networks, Model-free inference of diffusion networks using RKHS embeddings, A neighbour scale fixed approach for influence maximization in social networks, Efficiency centrality in time-varying graphs, An efficient linear programming based method for the influence maximization problem in social networks, Target set selection for conservative populations, A survey on meta-heuristic algorithms for the influence maximization problem in the social networks, Parameterized approximability of maximizing the spread of influence in networks, Critical nodes in interdependent networks with deterministic and probabilistic cascading failures, Minimum budget for misinformation blocking in online social networks, A random algorithm for profit maximization in online social networks, Functional immunization of networks based on message passing, Competitive diffusion in signed social networks: a game-theoretic perspective, A polyhedral study of dynamic monopolies, Logical dynamics of belief change in the community, Whom to befriend to influence people, Fast and frugal targeting with incentives, Partial immunization of trees, Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, A primal-dual algorithm for the minimum partial set multi-cover problem, Non-submodular maximization on massive data streams, Deterministic versus stochastic consensus dynamics on graphs, Complete submodularity characterization in the comparative independent cascade model, Multi-pass streaming algorithms for monotone submodular function maximization, Better streaming algorithms for the maximum coverage problem, $\beta$-differential of a graph, Private non-monotone submodular maximization, Cooperative and competitive dynamics model for information propagation in online social networks, The complexity of finding harmless individuals in social networks, Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems, Greedy guarantees for minimum submodular cost submodular/non-submodular cover problem, Sequential competition and the strategic origins of preferential attachment, Loyalty improvement beyond the seeds in social networks, A tight analysis of the submodular-supermodular procedure, Exploiting social influence to control elections based on positional scoring rules, Who should get vaccinated? Individualized allocation of vaccines over SIR network, Bootstrap percolation on the stochastic block model, Minimal contagious sets in random regular graphs, On reconfigurability of target sets, Diversified-profit maximization in competitive social advertising, A polyhedral approach to least cost influence maximization in social networks, Two approximation algorithms for maximizing nonnegative weakly monotonic set functions, Prioritization of candidate genes through Boolean networks, Kernel-based models for influence maximization on graphs based on Gaussian process variance minimization, Better approximation algorithms for influence maximization in online social networks, Adaptive seeding for profit maximization in social networks, Minimum budget for misinformation detection in online social networks with provable guarantees

Uses Software

Cites Work