Publication:2941641
From MaRDI portal
DOI10.4086/toc.2015.v011a004zbMath1337.91069MaRDI 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
diffusion; submodular function; social networks; influence; approximation algorithms; viral marketing
68Q25: Analysis of algorithms and problem complexity
91D30: Social networks; opinion dynamics
90C59: Approximation methods and heuristics in mathematical programming
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Multi-pass streaming algorithms for monotone submodular function maximization, Private non-monotone submodular maximization, 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, 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, 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, Adaptive seeding for profit maximization in social networks, Minimum budget for misinformation detection in online social networks with provable guarantees, A graph theoretical approach to the firebreak locating problem, 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, 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, The differential of the line graph \(\mathcal{L} (G)\), Interaction-aware influence maximization and iterated sandwich method, Innovation adoption and collective experimentation, A typology of social capital and associated network measures, Research progress in enhancing the controllability of complex networks, Group conformity in social networks, A variation of DS decomposition in set function optimization, KATZ centrality with biogeography-based optimization for influence maximization problem, Spreading linear triple systems and expander triple systems, 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, 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, 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, Better streaming algorithms for the maximum coverage problem, \(\beta\)-differential of a graph, Cooperative and competitive dynamics model for information propagation in online social networks, The complexity of finding harmless individuals in social networks, Loyalty improvement beyond the seeds in social networks, A tight analysis of the submodular-supermodular procedure, Minimal contagious sets in random regular graphs, Better approximation algorithms for influence maximization in online social networks, Strategyproof mechanisms for competitive influence in networks, Competitive profit maximization in social networks, Centralized and decentralized rumor blocking problems, Burning a graph is hard, Privacy-constrained network formation, Influence prediction for continuous-time information propagation on networks, 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, Activity preserving graph simplification, Information diffusion on the iterated local transitivity model of online social networks, Logical dynamics of belief change in the community, Vaccinate your trees!, An Asynchronous Linear-Threshold Innovation Diffusion Model, Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem, Unnamed Item, Order optimal information spreading using algebraic gossip, 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, 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, Submodular Maximization Subject to a Knapsack Constraint Under Noise Models, The Limitations of Optimization from Samples, Submodular Optimization with Contention Resolution Extensions., Unnamed Item, Unnamed Item, 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, 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, Complexity of equilibrium in competitive diffusion games on social networks, Parallelization of game theoretic centrality algorithms, Sequential decision aggregation with social pressure, Social structure optimization in team formation, A tight upper bound on acquaintance time of graphs, 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, Combinatorial model and bounds for target set selection, New bounds for contagious sets, Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids, Polynomial time approximation scheme for \(t\)-latency bounded information propagation problem in wireless networks, On dynamic monopolies of graphs: the average and strict majority thresholds, Treewidth governs the complexity of target set selection, Data mining of social networks represented as graphs, A nature-inspired influence propagation model for the community expansion problem, An individual-based model of information diffusion combining friends' influence, Potential induced random teleportation on finite graphs, Assignment games with conflicts: robust price of anarchy and convergence results via semi-smoothness, Marketing impact on diffusion in social networks, Measuring the impact of MVC attack in large complex networks, Approximation algorithms for pricing with negative network externalities, The complexity of finding effectors, Irreversible conversion of graphs, Competitivity groups on social network sites, On dissemination thresholds in regular and irregular graph classes, Informational influence and informational control models in social networks, Reversible iterative graph processes, 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, 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, Galaxy cutsets in graphs, Minimizing the expected complete influence time of a social network, A note on competitive diffusion through social networks, Influence maximization in social networks under an independent cascade-based model, Discovering small target sets in social networks: a fast and effective algorithm, Identifying and tracking topic-level influencers in the microblog streams, Least cost influence propagation in (social) networks, A game-theoretic approach for modeling competitive diffusion over social networks, Contagious sets in dense graphs, Welfare maximization with friends-of-friends network externalities, On general threshold and general cascade models of social influence, Retracted article: ``A distance vector similarity metric for complex networks, Efficient influence maximization under TSCM: a suitable diffusion model in online social networks, Inhibiting diffusion of complex contagions in social networks: theoretical and experimental results, Beyond rankings: comparing directed acyclic graphs, Targeted influential nodes selection in location-aware social networks, Active influence spreading in social networks, Recommending links through influence maximization, Multipolar robust optimization, Influence minimization in linear threshold 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, A two-stage stochastic programming approach for influence maximization in social networks, An efficient algorithm for link prediction in temporal uncertain social networks, Integer programming approach to static monopolies in graphs, Maximizing misinformation restriction within time and budget constraints, Optimization of stochastic virus detection in contact networks, Maximizing monotone submodular functions over the integer lattice, Submodular unsplittable flow on trees, The complexity of influence maximization problem in the deterministic linear threshold model, 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, The firefighter problem with more than one firefighter on trees, PASS approximation: a framework for analyzing and designing heuristics, Containment of rumor spread by selecting immune nodes in social networks, 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, Election control through social influence with unknown preferences, A non-extendibility certificate for submodularity and applications, Robust budget allocation via continuous submodular functions, 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, 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 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, Computing Critical Nodes in Directed Graphs, Rumors Spread Slowly in a Small-World Spatial Network, Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback, Network Essence: PageRank Completion and Centrality-Conforming Markov Chains, The Zero Forcing Number of Graphs, Probabilistic Partial Set Covering with an Oracle for Chance Constraints, Invertibility of graph translation and support of Laplacian Fiedler vectors, Diffusion of Defaults Among Financial Institutions, Algorithmic Aspects of Private Bayesian Persuasion., Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, A classification for community discovery methods in complex networks, Non‐negative residual matrix factorization: problem definition, fast solutions, and applications, Voter Model on Signed Social Networks, Finding Safe Strategies for Competitive Diffusion on Trees, On the Power of Planned Infections in Networks, 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, Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model, Hardness Results for Seeding Complex Contagion with Neighborhoods, Graph representation learning for popularity prediction problem: A survey, A survey of graph burning, Target Set Selection in Dense Graph Classes, Unnamed Item, Edge Deletion Algorithms for Minimizing Spread in SIR Epidemic Models, Fairness in Influence Maximization through Randomization, Fortification Against Cascade Propagation Under Uncertainty, Structured Robust Submodular Maximization: Offline and Online Algorithms, Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem, Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint, 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, Seeding with Costly Network Information, Adaptive Submodular Ranking and Routing, 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, Approximating Robust Parameterized Submodular Function Maximization in Large-Scales, Spectral bounds in random graphs applied to spreading phenomena and percolation, 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, Some algebraic hyperstructures related to zero forcing sets and forcing digraphs, Stability and Recovery for Independence Systems, ChoiceGAPs: Competitive Diffusion as a Massive Multi-player Game in Social Networks, Semantics-aware influence maximization in social networks, Stochastic-lazier-greedy algorithm for monotone non-submodular maximization, Edge instability: a critical parameter for the propagation and robustness analysis of large networks, Influence analysis: A survey of the state-of-the-art, Higher order monotonicity and submodularity of influence in social networks: from local to global, Online risk-averse submodular maximization, Relationship externalities, Streaming submodular maximization under \(d\)-knapsack constraints, Solving target set selection with bounded thresholds faster than \(2^n\), 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, Precautionary rumor containment via trustworthy people in social networks, Acquaintance Time of Random Graphs Near Connectivity Threshold, PageRank Beyond the Web, The Routing of Complex Contagion in Kleinberg’s Small-World Networks, Absorption time of the Moran process, Evangelism in Social Networks, Finding Rumor Sources on Random Trees, Defending Planar Graphs against Star-Cutsets, A Nash Equilibrium Based Algorithm for Mining Hidden Links in Social Networks, Influence Diffusion in Social Networks under Time Window Constraints, Unnamed Item, The Small Community Phenomenon in Networks: Models, Algorithms and Applications, Optimizing Network Topology for Cascade Resilience, 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, 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, Multi-player Diffusion Games on Graph Classes, Complex Contagions on Configuration Model Graphs with a Power-Law Degree Distribution, Multi-level dynamo and opinion spreading, Maximizing Influence in Competitive Environments: A Game-Theoretic Approach, Submodular Unsplittable Flow on Trees, Influence Maximization in Social Networks, On irreversible spread of influence in edge-weighted graphs, Streaming Algorithms for Submodular Function Maximization, Normalization Phenomena in Asynchronous Networks, Competitive Diffusion on Weighted Graphs, Optimizing Spread of Influence in Social Networks via Partial Incentives, Adaptive Rumor Spreading, A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks, Word of Mouth: Rumor Dissemination in Social Networks
Uses Software
Cites Work
- Ergodic theorems for weakly interacting infinite systems and the voter model
- The statistical mechanics of strategic interaction
- From the Cover: The structure of scientific collaboration networks
- Price of Anarchy for the N-Player Competitive Cascade Game with Submodular Activation Functions
- A New Product Growth for Model Consumer Durables
- A simple model of global cascades on random networks
