2021
Vitoropoulou, M.; Tsitseklis, K.; Karyotis, V.; Papavassiliou, S.
CoveR: An Information Diffusion Aware Approach for Efficient Recommendations under User Coverage Constraints Journal Article
In: IEEE Transactions on Computational Social Systems, vol. 8, no. 4, pp. 894-905, 2021, ISSN: 2329924X, (cited By 2).
Abstract | Links | BibTeX | Tags: Approximation algorithms; Heuristic methods; Linear programming; NP-hard; Social networking (online), Coverage constraints; Extensive simulations; Influence networks; Information diffusion; Integer programming problems; Online social networks (OSN); Set cover problem; Weighted set covers, Integer programming
@article{Vitoropoulou2021894,
title = {CoveR: An Information Diffusion Aware Approach for Efficient Recommendations under User Coverage Constraints},
author = {M. Vitoropoulou and K. Tsitseklis and V. Karyotis and S. Papavassiliou},
url = {https://www.scopus.com/inward/record.uri?eid=2-s2.0-85103753269&doi=10.1109%2fTCSS.2021.3067711&partnerID=40&md5=24ae5598764569c3f5f8bd69b762c4fb},
doi = {10.1109/TCSS.2021.3067711},
issn = {2329924X},
year = {2021},
date = {2021-01-01},
journal = {IEEE Transactions on Computational Social Systems},
volume = {8},
number = {4},
pages = {894-905},
publisher = {Institute of Electrical and Electronics Engineers Inc.},
abstract = {In this article, we consider the problem of recommendations to the users of an online social network (OSN), through an information diffusion aware recommender system (IDARS). We map the assignment of recommendations in influence networks to a problem of selecting an $ell $ -cover of the minimum total cost, which is defined to be a set of assignments such that each user in the OSN is recommended of at least $ell $ different items at the minimum defined cost. This corresponds to a special case of the minimum weighted partition set cover problem, which is a generalization of the minimum weighted set cover problem, both of which are proven to be NP-hard. We formulate a corresponding integer programming problem and we apply a linear programming (LP)-based branch and bound (BnB) methodology for its solution. We also propose a greedy algorithm, denoted as CoveR, which we show to be an $O((Delta /delta )cdot H(Delta))$ -approximation for the $ell $ -coverage problem, where $Delta $ and $delta $ are the maximum and minimum degree of an influence network, respectively, and $H(Delta)$ is the $Delta text th$ harmonic number. We investigate CoveR's performance through extensive simulations on both synthetic and real networks, which indicate that the quality of its solution is comparable to the one obtained by the BnB method, while at the same time outperforms other information diffusion-aware recommendation heuristics. © 2014 IEEE.},
note = {cited By 2},
keywords = {Approximation algorithms; Heuristic methods; Linear programming; NP-hard; Social networking (online), Coverage constraints; Extensive simulations; Influence networks; Information diffusion; Integer programming problems; Online social networks (OSN); Set cover problem; Weighted set covers, Integer programming},
pubstate = {published},
tppubtype = {article}
}
In this article, we consider the problem of recommendations to the users of an online social network (OSN), through an information diffusion aware recommender system (IDARS). We map the assignment of recommendations in influence networks to a problem of selecting an $ell $ -cover of the minimum total cost, which is defined to be a set of assignments such that each user in the OSN is recommended of at least $ell $ different items at the minimum defined cost. This corresponds to a special case of the minimum weighted partition set cover problem, which is a generalization of the minimum weighted set cover problem, both of which are proven to be NP-hard. We formulate a corresponding integer programming problem and we apply a linear programming (LP)-based branch and bound (BnB) methodology for its solution. We also propose a greedy algorithm, denoted as CoveR, which we show to be an $O((Delta /delta )cdot H(Delta))$ -approximation for the $ell $ -coverage problem, where $Delta $ and $delta $ are the maximum and minimum degree of an influence network, respectively, and $H(Delta)$ is the $Delta text th$ harmonic number. We investigate CoveR's performance through extensive simulations on both synthetic and real networks, which indicate that the quality of its solution is comparable to the one obtained by the BnB method, while at the same time outperforms other information diffusion-aware recommendation heuristics. © 2014 IEEE.