A Community-Aware Framework for Social Influence Maximization
- URL: http://arxiv.org/abs/2207.08937v1
- Date: Mon, 18 Jul 2022 20:43:17 GMT
- Title: A Community-Aware Framework for Social Influence Maximization
- Authors: Abhishek Kumar Umrawal and Vaneet Aggarwal
- Abstract summary: We consider the Influence Maximization (IM) problem: 'if we can try to convince a subset of individuals in a social network to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target'
We propose a community-aware divide-and-conquer strategy that involves (i) learning the inherent community structure of the social network, (ii) generating candidate solutions by solving the influence problem for each community, and (iii) selecting the final set of individuals from the candidate solutions using a novel progressive budgeting scheme.
- Score: 40.842329580198324
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the Influence Maximization (IM) problem: 'if we can try to
convince a subset of individuals in a social network to adopt a new product or
innovation, and the goal is to trigger a large cascade of further adoptions,
which set of individuals should we target'? Formally, it is the task of
selecting $k$ seed nodes in a social network such that the expected number of
influenced nodes in the network (under some influence propagation model) is
maximized. This problem has been widely studied in the literature and several
solution approaches have been proposed. However, most simulation-based
approaches involve time-consuming Monte-Carlo simulations to compute the
influence of the seed nodes in the entire network. This limits the
applicability of these methods on large social networks. In the paper, we are
interested in solving the problem of influence maximization in a time-efficient
manner. We propose a community-aware divide-and-conquer strategy that involves
(i) learning the inherent community structure of the social network, (ii)
generating candidate solutions by solving the influence maximization problem
for each community, and (iii) selecting the final set of individuals from the
candidate solutions using a novel progressive budgeting scheme.
We provide experiments on real-world social networks, showing that the
proposed algorithm outperforms the simulation-based algorithms in terms of
empirical run-time and the heuristic algorithms in terms of influence. We also
study the effect of the community structure on the performance of our
algorithm. Our experiments show that the community structures with higher
modularity lead the proposed algorithm to perform better in terms of run-time
and influence.
Related papers
- DQSSA: A Quantum-Inspired Solution for Maximizing Influence in Online
Social Networks (Student Abstract) [17.756827206688364]
Influence Maximization is the task of selecting optimal nodes maximising the influence spread in social networks.
This study proposes a Discretized Quantum-based Salp Swarm Algorithm (DQSSA) for optimizing influence diffusion in social networks.
arXiv Detail & Related papers (2023-11-30T16:23:44Z) - A Survey on Influence Maximization: From an ML-Based Combinatorial
Optimization [2.9882027965916413]
Influence Maximization (IM) is a classical optimization problem, which can be widely used in mobile networks, social computing, and recommendation systems.
Main challenge comes from the NP-hardness of the IM problem and #P-hardness of estimating the influence spread.
We focus on summarizing the relevant background knowledge, basic principles, common methods, and applied research.
arXiv Detail & Related papers (2022-11-06T10:13:42Z) - 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) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems.
Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC.
We provide a practical parametrization of the core optimization problem.
arXiv Detail & Related papers (2021-07-08T18:01:02Z) - Contingency-Aware Influence Maximization: A Reinforcement Learning
Approach [52.109536198330126]
influence (IM) problem aims at finding a subset of seed nodes in a social network that maximize the spread of influence.
In this study, we focus on a sub-class of IM problems, where whether the nodes are willing to be the seeds when being invited is uncertain, called contingency-aware IM.
Despite the initial success, a major practical obstacle in promoting the solutions to more communities is the tremendous runtime of the greedy algorithms.
arXiv Detail & Related papers (2021-06-13T16:42:22Z) - ABEM: An Adaptive Agent-based Evolutionary Approach for Mining
Influencers in Online Social Networks [1.6128569396451058]
A key step in evolutionary influence in online social networks is the identification of a small number of users, known as influencers.
The evolving nature of the structure of these networks makes it difficult to locate and identify these influencers.
We propose an adaptive agent-based approach to address this problem in the context of both static and dynamic networks.
arXiv Detail & Related papers (2021-04-14T00:31:08Z) - Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding
Design for Multiuser MIMO Systems [59.804810122136345]
We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed.
An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed.
We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
arXiv Detail & Related papers (2020-06-15T02:57:57Z) - Decentralized MCTS via Learned Teammate Models [89.24858306636816]
We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search.
We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
arXiv Detail & Related papers (2020-03-19T13:10:20Z)
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.