Influence Maximization Under Generic Threshold-based Non-submodular Model

• URL: http://arxiv.org/abs/2012.12309v1
• Date: Fri, 18 Dec 2020 16:14:49 GMT
• Title: Influence Maximization Under Generic Threshold-based Non-submodular Model
• Authors: Liang Ma
• Abstract summary: Concept of social influence is coined, where the goal is to select a number of most influential nodes (seed nodes) from a social network so that they can jointly trigger the maximal influence diffusion. In this paper, we propose seed selection strategies using network graphical in a generalized threshold-based model, called influence barricade model, which is non-submodular. To the best of our knowledge, this is the first graph-based approach that directly tackles non-submodular influence.
• Score: 1.5780411262109524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As a widely observable social effect, influence diffusion refers to a process where innovations, trends, awareness, etc. spread across the network via the social impact among individuals. Motivated by such social effect, the concept of influence maximization is coined, where the goal is to select a bounded number of the most influential nodes (seed nodes) from a social network so that they can jointly trigger the maximal influence diffusion. A rich body of research in this area is performed under statistical diffusion models with provable submodularity, which essentially simplifies the problem as the optimal result can be approximated by the simple greedy search. When the diffusion models are non-submodular, however, the research community mostly focuses on how to bound/approximate them by tractable submodular functions so as to estimate the optimal result. In other words, there is still a lack of efficient methods that can directly resolve non-submodular influence maximization problems. In this regard, we fill the gap by proposing seed selection strategies using network graphical properties in a generalized threshold-based model, called influence barricade model, which is non-submodular. Specifically, under this model, we first establish theories to reveal graphical conditions that ensure the network generated by node removals has the same optimal seed set as that in the original network. We then exploit these theoretical conditions to develop efficient algorithms by strategically removing less-important nodes and selecting seeds only in the remaining network. To the best of our knowledge, this is the first graph-based approach that directly tackles non-submodular influence maximization.

Related papers

• Influence Maximization via Graph Neural Bandits [54.45552721334886]
  We set the IM problem in a multi-round diffusion campaign, aiming to maximize the number of distinct users that are influenced. We propose the framework IM-GNB (Influence Maximization with Graph Neural Bandits), where we provide an estimate of the users' probabilities of being influenced.
  arXiv  Detail & Related papers  (2024-06-18T17:54:33Z)
• Multiple-Source Localization from a Single-Snapshot Observation Using Graph Bayesian Optimization [10.011338977476804]
  Multi-source localization from a single snap-shot observation is especially relevant due to its prevalence. Current methods typically utilizes and greedy selection, and they are usually bonded with one diffusion model. We propose a simulation-based method termed BOSouL to approximate the results for its sample efficiency.
  arXiv  Detail & Related papers  (2024-03-25T14:46:24Z)
• DSCom: A Data-Driven Self-Adaptive Community-Based Framework for Influence Maximization in Social Networks [3.97535858363999]
  We reformulate the problem on the attributed network and leverage the node attributes to estimate the closeness between connected nodes. Specifically, we propose a machine learning-based framework, named DSCom, to address this problem. Compared to the previous theoretical works, we carefully designed empirical experiments with parameterized diffusion models based on real-world social networks.
  arXiv  Detail & Related papers  (2023-11-18T14:03:43Z)
• Model-based Causal Bayesian Optimization [74.78486244786083]
  We introduce the first algorithm for Causal Bayesian Optimization with Multiplicative Weights (CBO-MW) We derive regret bounds for CBO-MW that naturally depend on graph-related quantities. Our experiments include a realistic demonstration of how CBO-MW can be used to learn users' demand patterns in a shared mobility system.
  arXiv  Detail & Related papers  (2023-07-31T13:02:36Z)
• Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization [53.11458949694947]
  We consider an adaptive version of content-dependent online influence problem where seed nodes are sequentially activated based on realtime feedback. Our algorithm maintains a network model estimate and selects seed adaptively, exploring the social network while improving the optimal policy optimistically.
  arXiv  Detail & Related papers  (2022-06-29T18:17:28Z)
• On the Generalization and Adaption Performance of Causal Models [99.64022680811281]
  Differentiable causal discovery has proposed to factorize the data generating process into a set of modules. We study the generalization and adaption performance of such modular neural causal models. Our analysis shows that the modular neural causal models outperform other models on both zero and few-shot adaptation in low data regimes.
  arXiv  Detail & Related papers  (2022-06-09T17:12:32Z)
• How Tempering Fixes Data Augmentation in Bayesian Neural Networks [22.188535244056016]
  We show that tempering implicitly reduces the misspecification arising from modeling augmentations as i.i.d. data. The temperature mimics the role of the effective sample size, reflecting the gain in information provided by the augmentations.
  arXiv  Detail & Related papers  (2022-05-27T11:06:56Z)
• Preference Enhanced Social Influence Modeling for Network-Aware Cascade Prediction [59.221668173521884]
  We propose a novel framework to promote cascade size prediction by enhancing the user preference modeling. Our end-to-end method makes the user activating process of information diffusion more adaptive and accurate.
  arXiv  Detail & Related papers  (2022-04-18T09:25:06Z)
• Network Inference and Influence Maximization from Samples [20.916163957596577]
  We study the task of selecting a small number of seed nodes in a social network to maximize the spread of the influence from these seeds. We provide a novel solution to the cascade to the network inference problem, that is, learning diffusion parameters and the network structure from the data. Our IMS algorithms enhance the learning-and-then-optimization approach by allowing a constant approximation ratio even when the diffusion parameters are hard to learn.
  arXiv  Detail & Related papers  (2021-06-07T08:06:36Z)
• Loss Bounds for Approximate Influence-Based Abstraction [81.13024471616417]
  Influence-based abstraction aims to gain leverage by modeling local subproblems together with the 'influence' that the rest of the system exerts on them. This paper investigates the performance of such approaches from a theoretical perspective. We show that neural networks trained with cross entropy are well suited to learn approximate influence representations.
  arXiv  Detail & Related papers  (2020-11-03T15:33:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.