Positive Evaluation Maximization in Social Networks: Model and Algorithm

Shengminjie Chen, Wenguo Yang, Suixiang GaoIEEE Transactions on Computational Social Systems 2022 · DOI

Abstract

Influence maximization (IM) is a classical and heated issue in online social networks. Although some works have studied multifeature IM, they do not consider this problem from the perspective of users’ preferences. In this article, we construct a novel multifeature spreading model that considers users’ different preferences, namely, the MFP-independent cascade (IC) model, which uses the IC model as the basic propagation model. Some features are positive or negative depending on users’ preferences. According to this spreading model, we consider a novel problem that focuses on the influence gap between positive features and negative features, namely, positive evaluation maximization (PEM). This problem is NP-hard and nonsubmodular. Fortunately, PEM can be expressed as DS decomposition because the positive influence and the negative influence are both monotone submodular. Based on DS decomposition, we design some special greedy strategies, namely, the parametric conditioned greedy (PCG). To reduce the computational cost of our method, we design fast PCG (FPCG) algorithm using the sampling technique. In addition, the approximation ratio of the PCG and FPCG approaches is only the gap between their <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\epsilon)$ </tex-math></inline-formula> values. Finally, we evaluate our algorithms by performing massive experiments on real datasets.
BibTeX
@article{chen2022positive,
  author = {Shengminjie Chen and Wenguo Yang and Suixiang Gao},
  title = {{Positive Evaluation Maximization in Social Networks: Model and Algorithm}},
  journal = {IEEE Transactions on Computational Social Systems},
  year = {2022},
  doi = {10.1109/tcss.2022.3188519},
}

Loading related content...

Figure