Influence Maximization with Unknown Individual Effect on General Network
- URL: http://arxiv.org/abs/2301.12226v2
- Date: Wed, 1 May 2024 14:56:39 GMT
- Title: Influence Maximization with Unknown Individual Effect on General Network
- Authors: Xinyan Su, Zhiheng Zhang, Jiyan Qiu, Jun Li,
- Abstract summary: The identification of a seed set to maximize information spread in a network is crucial, a concept known as Influence Maximization (IM)
IM algorithms could naturally extend to cases where each node is equipped with specific weight, referred to as individual effect, to measure the node's importance.
In our paper, we address this through the development of a Causal Influence Maximization (CauIM) algorithm.
- Score: 3.4049427793086324
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The identification of a seed set to maximize information spread in a network is crucial, a concept known as Influence Maximization (IM). Elegant IM algorithms could naturally extend to cases where each node is equipped with specific weight, referred to as individual effect, to measure the node's importance. Prevailing literature has typically assumed that the individual effect remains constant during the cascade process. However, this assumption is not always feasible, as the individual effect of each node is primarily evaluated by the difference between the outputs in the activated and non-activated states, with one of these states always being unobservable after propagation. Moreover, the individual effect is sensitive to the environmental information provided by surrounding nodes. To address these challenges, we extend the consideration of IM to a broader scenario involving general networks with dynamic node individual effects, leveraging causality techniques. In our paper, we address this through the development of a Causal Influence Maximization (CauIM) algorithm. Theoretically, for CauIM, we present the generalized lower bound of influence spread and provide robustness analysis. Empirically, in synthetic and real-world experiments, we demonstrate the effectiveness and robustness of CauIM, along with a novel acceleration technique.
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) - Influence Maximization in Hypergraphs Using A Genetic Algorithm with New Initialization and Evaluation Methods [6.315027378756443]
Influence (IM) is a crucial optimization task related to analyzing complex networks in the real world.
We propose a novel model that integrates the influences of both node and hyperedge failures.
We then introduce genetic algorithms (GA) to identify the most influential nodes that leverage hypergraph collective influences.
arXiv Detail & Related papers (2024-05-15T08:46:33Z) - ACE : Off-Policy Actor-Critic with Causality-Aware Entropy Regularization [52.5587113539404]
We introduce a causality-aware entropy term that effectively identifies and prioritizes actions with high potential impacts for efficient exploration.
Our proposed algorithm, ACE: Off-policy Actor-critic with Causality-aware Entropy regularization, demonstrates a substantial performance advantage across 29 diverse continuous control tasks.
arXiv Detail & Related papers (2024-02-22T13:22:06Z) - dugMatting: Decomposed-Uncertainty-Guided Matting [83.71273621169404]
We propose a decomposed-uncertainty-guided matting algorithm, which explores the explicitly decomposed uncertainties to efficiently and effectively improve the results.
The proposed matting framework relieves the requirement for users to determine the interaction areas by using simple and efficient labeling.
arXiv Detail & Related papers (2023-06-02T11:19:50Z) - Understanding Influence Maximization via Higher-Order Decomposition [6.542119695695405]
Influence Maximization (IM) has garnered considerable attention over the last couple of decades.
This work dissects the influence exerted on individual seeds and their higher-order interactions utilizing the Sobol index.
An IM algorithm dubbed SIM is proposed to improve the performance of current IM algorithms by over-selecting nodes.
arXiv Detail & Related papers (2022-07-16T04:44:16Z) - GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence
Maximization [1.7311053765541482]
Influence (IM) is a problem of identifying a subset of nodes called the seed nodes in a network (graph)
IM has numerous applications such as viral marketing, epidemic control, sensor placement and other network-related tasks.
We develop a generic IM problem as a Markov decision process that handles both intrinsic and influence activations.
arXiv Detail & Related papers (2022-05-30T03:48:51Z) - 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) - Localisation determines the optimal noise rate for quantum transport [68.8204255655161]
Localisation and the optimal dephasing rate in 1D chains are studied.
A simple power law captures the interplay between size-dependent and size-independent responses.
Relationship continues to apply at intermediate and high temperature but breaks down in the low temperature limit.
arXiv Detail & Related papers (2021-06-23T17:52:16Z) - On Dynamic Noise Influence in Differentially Private Learning [102.6791870228147]
Private Gradient Descent (PGD) is a commonly used private learning framework, which noises based on the Differential protocol.
Recent studies show that emphdynamic privacy schedules can improve at the final iteration, yet yet theoreticals of the effectiveness of such schedules remain limited.
This paper provides comprehensive analysis of noise influence in dynamic privacy schedules to answer these critical questions.
arXiv Detail & Related papers (2021-01-19T02:04:00Z) - Influence Maximization Under Generic Threshold-based Non-submodular
Model [1.5780411262109524]
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.
arXiv Detail & Related papers (2020-12-18T16:14:49Z)
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.