TY - JOUR
T1 - The most tenuous group query
AU - Li, Na
AU - Zhu, Huaijie
AU - Lu, Wenhao
AU - Cui, Ningning
AU - Liu, Wei
AU - Yin, Jian
AU - Xu, Jianliang
AU - Lee, Wang Chien
N1 - Funding Information:
This work was partially supported by the Key-Area Research and Development Program of Guangdong Province (2020B0101100001), Guangdong Basic and Applied Basic Research Foundation (2019B1515130001), the National Natural Science Foundation of China (Grant Nos. 61902438 and 61902439), and Natural Science Foundation of Guangdong Province (2019A1515011704 and 2019A1515011159). Jianliang Xu’s work is supported by HK-RGC (12201018).
Publisher Copyright:
Copyright © 2022, Higher Education Press
PY - 2023/4
Y1 - 2023/4
N2 - Recently a lot of works have been investigating to find the tenuous groups, i.e., groups with few social interactions and weak relationships among members, for reviewer selection and psycho-educational group formation. However, the metrics (e.g., k-triangle, k-line, and k-tenuity) used to measure the tenuity, require a suitable k value to be specified which is difficult for users without background knowledge. Thus, in this paper we formulate the most tenuous group (MTG) query in terms of the group distance and average group distance of a group measuring the tenuity to eliminate the influence of parameter k on the tenuity of the group. To address the MTG problem, we first propose an exact algorithm, namely MTG-VDIS, which takes priority to selecting those vertices whose vertex distance is large, to generate the result group, and also utilizes effective filtering and pruning strategies. Since MTG-VDIS is not fast enough, we design an efficient exact algorithm, called MTG-VDGE, which exploits the degree metric to sort the vertexes and proposes a new combination order, namely degree and reverse based branch and bound (DRBB). MTG-VDGE gives priority to those vertices with small degree. For a large p, we further develop an approximation algorithm, namely MTG-VDLT, which discards candidate attendees with high degree to reduce the number of vertices to be considered. The experimental results on real datasets manifest that the proposed algorithms outperform existing approaches on both efficiency and group tenuity.
AB - Recently a lot of works have been investigating to find the tenuous groups, i.e., groups with few social interactions and weak relationships among members, for reviewer selection and psycho-educational group formation. However, the metrics (e.g., k-triangle, k-line, and k-tenuity) used to measure the tenuity, require a suitable k value to be specified which is difficult for users without background knowledge. Thus, in this paper we formulate the most tenuous group (MTG) query in terms of the group distance and average group distance of a group measuring the tenuity to eliminate the influence of parameter k on the tenuity of the group. To address the MTG problem, we first propose an exact algorithm, namely MTG-VDIS, which takes priority to selecting those vertices whose vertex distance is large, to generate the result group, and also utilizes effective filtering and pruning strategies. Since MTG-VDIS is not fast enough, we design an efficient exact algorithm, called MTG-VDGE, which exploits the degree metric to sort the vertexes and proposes a new combination order, namely degree and reverse based branch and bound (DRBB). MTG-VDGE gives priority to those vertices with small degree. For a large p, we further develop an approximation algorithm, namely MTG-VDLT, which discards candidate attendees with high degree to reduce the number of vertices to be considered. The experimental results on real datasets manifest that the proposed algorithms outperform existing approaches on both efficiency and group tenuity.
KW - group query
KW - pruning strategy
KW - social network
KW - tenuous group
UR - http://www.scopus.com/inward/record.url?scp=85135609287&partnerID=8YFLogxK
U2 - 10.1007/s11704-022-1462-5
DO - 10.1007/s11704-022-1462-5
M3 - Journal article
AN - SCOPUS:85135609287
SN - 2095-2228
VL - 17
JO - Frontiers of Computer Science
JF - Frontiers of Computer Science
IS - 2
M1 - 172605
ER -