Maximizing Social Influence in Nearly Optimal Time

DOI10.1137/1.9781611973402.70zbMath1420.68248arXiv1212.0884OpenAlexW2160411082MaRDI QIDQ5384031

Michael Brautbar, Brendan Lucier, Christian Borgs, Jennifer T. Chayes

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.0884

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.) (60J70)

Related Items

New trends in influence maximization models ⋮ Submodular Maximization Subject to a Knapsack Constraint Under Noise Models ⋮ The Limitations of Optimization from Samples ⋮ Influence maximization problem: properties and algorithms ⋮ Profit maximization for competitive social advertising ⋮ Union acceptable profit maximization in social networks ⋮ Maximize the probability of union-influenced in social networks ⋮ Fixed observation time-step: adaptive influence maximization ⋮ Edge Deletion Algorithms for Minimizing Spread in SIR Epidemic Models ⋮ Fairness in Influence Maximization through Randomization ⋮ Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms ⋮ Semantics-aware influence maximization in social networks ⋮ Influence Maximization with Latency Requirements on Social Networks ⋮ Exact stochastic constraint optimisation with applications in network analysis ⋮ Influence analysis: A survey of the state-of-the-art ⋮ A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality ⋮ Higher order monotonicity and submodularity of influence in social networks: from local to global ⋮ Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint ⋮ Uncertainty in Study of Social Networks: Robust Optimization and Machine Learning ⋮ Online conflict resolution: algorithm design and analysis ⋮ Seeding with Costly Network Information ⋮ Opinion influence maximization problem in online social networks based on group polarization effect ⋮ Maximizing the influence with \(\kappa\)-grouping constraint ⋮ Fair Influence Maximization in Large-scale Social Networks Based on Attribute-aware Reverse Influence Sampling ⋮ Better bounds on the adaptivity gap of influence maximization under full-adoption feedback ⋮ IM2Vec: representation learning-based preference maximization in geo-social networks ⋮ Math‐based reinforcement learning for the adaptive budgeted influence maximization problem ⋮ A neighbour scale fixed approach for influence maximization in social networks ⋮ Targeted influential nodes selection in location-aware social networks ⋮ Matching influence maximization in social networks ⋮ An efficient linear programming based method for the influence maximization problem in social networks ⋮ The Complexity of Partial Function Extension for Coverage Functions ⋮ A two-stage stochastic programming approach for influence maximization in social networks ⋮ Rumor correction maximization problem in social networks ⋮ TIFIM: a two-stage iterative framework for influence maximization in social networks ⋮ Robust budget allocation via continuous submodular functions ⋮ Boosting node activity by recommendations in social networks ⋮ Finding top-\(k\) influential users in social networks under the structural diversity model ⋮ Viral marketing of online game by DS decomposition in social networks ⋮ Profit maximization problem with coupons in social networks ⋮ A random algorithm for profit maximization in online social networks ⋮ General rumor blocking: an efficient random algorithm with martingale approach ⋮ How to choose friends strategically ⋮ Two-stage pricing strategy with price discount in online social networks ⋮ Whom to befriend to influence people ⋮ Attribute based diversification of seeds for targeted influence maximization ⋮ On the influence maximization problem and the percolation phase transition ⋮ Adaptive influence maximization under fixed observation time-step ⋮ Nonsubmodular constrained profit maximization from increment perspective ⋮ Transmission errors and influence maximization in the voter model ⋮ Time bounded adaptive information coverage in social networks ⋮ Kernel-based models for influence maximization on graphs based on Gaussian process variance minimization ⋮ Minimum budget for misinformation detection in online social networks with provable guarantees