The most tenuous group query

Finding the tenuous groups has been a hot topic in community search area, which refers to groups with few social interactions and weak relationships among members, for reviewer selection and psycho-educational group formation. The existing 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.

To solve the problem, a research team led by Huaijie Zhu published their new research on 15 April 2023 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.

The team proposed several approaches to tackle this problem. They 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, They 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,  they further develop an approximation algorithm, namely MTG-VDLT, which discards candidate attendees with high degree to reduce the number of vertices to be considered.

In the experiments, they compare the proposed algorithms with the following performance metrics: 1) query time, 2) distance of the result, 3) average group distance of the result, 4) the accuracy score S of the result of the approximation algorithm. They also conduct a case study to show the usefulness of MTG-VDLT and MTG-VDGE on LA dataset. Experimental results on real datasets manifest that MTG-VDGE outperforms MTG-VDIS in efficiency. For MTG-VDLT, compared with KLMA, the result obtained by MTG-VDLT has a higher accuracy score.

Future work can focus on finding more suitable and flexible metrics to obtain a tenuous group, such as using a machine-learning based method to learn the k value from users’ history data.

###

Research Article, Published: 15 April 2023

Na LI, Huaijie ZHU, Wenhao LU, Ningning CUI, Wei LIU, Jian YIN, Jianliang XU, Wang-Chien LEE. The most tenuous group query. Front. Comput. Sci., 2023, 17(2): 172605, https://doi.org/10.1007/s11704-022-1462-5

About Frontiers of Computer Science (FCS)

FCS was launched in 2007. It is published bimonthly both online and in print by HEP and Springer. Prof. Zhi-Hua Zhou from Nanjing University serves as the Editor-in-Chief. It aims to provide a forum for the publication of peer-reviewed papers to promote rapid communication and exchange between computer scientists. FCS covers all major branches of computer science, including: architecture, software, artificial intelligence, theoretical computer science, networks and communication, information systems, multimedia and graphics, information security, interdisciplinary, etc. The readers may be interested in the special columns "Perspective" and "Excellent Young Scholars Forum".

FCS is indexed by SCI(E), EI, DBLP, Scopus, etc. The latest IF is 2.669. FCS solicits the following article types: Review, Research Article, Letter.