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.
