Journal
THEORETICAL COMPUTER SCIENCE
Volume 857, Issue -, Pages 71-86Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2020.12.040
Keywords
Influence maximization; Online matching; Offline matching
Categories
Funding
- National Natural Science Foundation of China [12071478, 61972404]
- NSF [1907472]
Ask authors/readers for more resources
In this study, influence maximization in social networks was explored with the introduction of matching relationships. By proposing online and offline matching approaches to maximize the number of matched users, the algorithms were shown to outperform existing methods on real-world datasets in terms of accuracy.
Influence maximization (IM) is a widely studied problem in social networks, which aims at finding a seed set with limited size that can maximize the expected number of influenced users. However, existing studies haven't considered the matching relationship, which refers to such scenarios that influenced users seek matched partners among the influenced users, such as time matching with friends to watch movie, or matching for opposite sex in the blind date. In this paper, we investigate different matching scenarios and propose online-matching (offline-matching), in which the matching and influence propagation are simultaneous (asynchronous). For the matching result, we introduce two matched types 's -matched', i.e., i -> j and 'd -matched', i.e., i <-> j. Then, we formulate the matching influence maximization (MM) problem to optimize a limited seed set that maximizes the expected number of matched users. We prove that the MM problem is NP-hard and the computation of the matching influence is #P-hard. Next, we analyze the submodularity of the matching influence. To address the problem, we propose efficient methods OPMM (SAMM) to solve the MM in online-matching (offline-matching) with (1 - 1/e - epsilon) approximation (beta (1 - 1/e - epsilon)-approximation) guarantee. Experiments on the real-world datasets show our algorithms outperform state of the art algorithms in terms of more accurate matching propagation results. (c) 2020 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available