Name
Abstract | ||
|---|---|---|
In the past decade, tremendous research effort has been devoted to viral marketing. Most existing works on seed selection in social networks do not take into account the scenario when a profit can be generated from group activities. Each activity has a profit that can be measured by the excitement of the participants. The excitement about one piece of information can vary significantly among different groups of people. Given a social network and a profit function, how can we select the seed users to maximize the expected total amount of profit? This problem is essentially different from the classic influence maximization problem, and existing approaches cannot be directly applied to solve the problem. In this paper, we study the problem of activity profit maximization in social networks. We first prove that the maximizing activity profit problem is nondeterministic polynomial time-hard and cannot be approximated within a constant factor by the simple greedy algorithm. Supermodular degree of a function measures the extent to which it violates submodularity. We design an algorithm that achieves an approximation ratio of (
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${1}/({\Delta +2}))$ </tex-math></inline-formula>
provided that the supermodular degree of the social graph is bounded with
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Delta $ </tex-math></inline-formula>
. We then develop an exchange-based technique to further improve the quality of the solution. We also devise a randomized variation approach to overcome the computational burden of the proposed algorithms. Extensive experimental results on three real benchmark data sets demonstrate the efficacy and efficiency of our algorithms over several baseline heuristics. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1109/TCSS.2019.2891582 | IEEE Transactions on Computational Social Systems |
Keywords | Field | DocType |
Integrated circuit modeling,Approximation algorithms,Social networking (online),Computational modeling,Games,Linear programming | Approximation algorithm,Mathematical optimization,Social graph,Computer science,Greedy algorithm,Heuristics,Artificial intelligence,Linear programming,Profit maximization,Maximization,Machine learning,NP | Journal |
Volume | Issue | ISSN |
6 | 1 | 2329-924X |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenguo Yang | 1 | 4 | 6.81 |
| Nicholas Jing Yuan | 2 | 2617 | 128.44 |
| Weili Wu | 3 | 2093 | 170.29 |
| Jianmin Ma | 4 | 243 | 11.85 |
| Ding-Zhu Du | 5 | 3497 | 283.06 |