Abstract
Socially tenuous groups (or simply tenuous groups) in a social network/graph refer to subgraphs with few social interactions and weak relationships among members. However, existing studies on tenuous group queries do not consider the user profiles (keywords) of the members whereas in many social network applications, e.g., finding reviewers for paper selection and recommending seed users in social advertising, keywords also need to be considered. Thus, in this paper, we investigate the problem of keywords-based socially tenous group (KTG) queries. A KTG query is to find top N tenuous groups in which the members of each group jointly cover the most number of query keywords. To address the KTG problem, we first propose two exact algorithms, namely KTG-VKC and KTG-VKC-DEG, which give priority to the valid keyword coverage and the combination of valid keyword coverage and degree, respectively, to select members to form a feasible group by adopting a branch and bound (BB) strategy. Moreover, we propose keyword pruning and k-line filtering to accelerate the algorithms. To yield diversified KTG results, we also study the problem of diversified keywords-based socially tenous group (DKTG) queries. To deal with the DKTG problem, we propose a DKTG-Greedy algorithm by exploiting a greedy heuristic in combination with KTG-VKC-DEG. Furthermore, we design two alternative indexes, namely NL and NLRNL, to efficiently check whether the social distance of any two members is greater than the social constraint k in the above algorithms. We conduct extensive experiments using real datasets to validate our ideas and evaluate the proposed algorithms. Experimental results show that the NLRNL index achieves a better performance than the NL index.
Original language | English |
---|---|
Title of host publication | Proceedings - 2023 IEEE 39th International Conference on Data Engineering, ICDE 2023 |
Publisher | IEEE |
Pages | 965-977 |
ISBN (Electronic) | 9798350322279 |
ISBN (Print) | 9798350322286 |
DOIs | |
Publication status | Published - 3 Apr 2023 |
Event | 39th IEEE International Conference on Data Engineering, ICDE 2023 - Anaheim, United States Duration: 3 Apr 2023 → 7 Apr 2023 https://icde2023.ics.uci.edu/ https://ieeexplore.ieee.org/xpl/conhome/10184508/proceeding |
Publication series
Name | Proceedings - International Conference on Data Engineering |
---|---|
Volume | 2023-April |
ISSN (Print) | 1063-6382 |
ISSN (Electronic) | 2375-026X |
Competition
Competition | 39th IEEE International Conference on Data Engineering, ICDE 2023 |
---|---|
Country/Territory | United States |
City | Anaheim |
Period | 3/04/23 → 7/04/23 |
Internet address |
User-Defined Keywords
- keyword
- social network
- Tenuous group queries