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

• Diffusion Model Agnostic Social Influence Maximization in Hyperbolic Space [0.0]
  The Influence Maximization (IM) problem aims to find a small set of influential users to maximize their influence spread in a social network. Traditional methods rely on fixed diffusion models with known parameters, limiting their generalization to real-world scenarios. We propose HIM, a novel diffusion model agnostic method that leverages hyperbolic representation learning to estimate users' potential influence spread.
  arXiv  Detail & Related papers  (2025-02-19T09:24:28Z)
• DeepSN: A Sheaf Neural Framework for Influence Maximization [7.2716257100195385]
  Influence is key topic in data mining, with broad applications in social network analysis and viral marketing. In recent years, researchers have increasingly turned to machine learning techniques to address this problem. DeepSN employs sheaf neural diffusion to learn diverse influence patterns in a data-driven end-to-end manner.
  arXiv  Detail & Related papers  (2024-12-16T23:49:51Z)
• Diffusion Models as Network Optimizers: Explorations and Analysis [71.69869025878856]
  generative diffusion models (GDMs) have emerged as a promising new approach to network optimization. In this study, we first explore the intrinsic characteristics of generative models. We provide a concise theoretical and intuitive demonstration of the advantages of generative models over discriminative network optimization.
  arXiv  Detail & Related papers  (2024-11-01T09:05:47Z)
• 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)
• 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)
• 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.