Matching influence maximization in social networks (Q2220781)

This paper studies the matching influence maximization in social networks by proposing two diffusion matching processes, namely online matching and offline matching. The matching influence maximization problem is to find \(k\) seeds such that the number of agents matched in the network can be maximized. The problem is shown to be NP-hard and the calculation of influence turns out to be \#P-hard. The submodularity of the matching influence is analyzed through an equivalent generating model and some basic properties are derived. In the case of online matching, efficient approaches for \(s\)-matched and \(d\)-matched types problems are proposed. Here, \(s\)-matched problem indicates unilateral match and \(d\)-matched problem indicates bilateral match. In the case of offline matching, the analogous algorithms have been proposed for both types of problems. The results have been tested on some real networks including Facebook, Twitter and Gplus.