Paper Info
Title
Matching Influence Maximization In Social Networks
Abstract
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.
Year
DOI
Venue
2021
10.1016/j.tcs.2020.12.040
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Influence maximization, Online matching, Offline matching
Journal
857
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
5
Name
Order
Citations
PageRank
Guoyao Rao100.34
Yongcai Wang2168.38
Wenping Chen332.07
Deying Li4238.79
Weili Wu52093170.29