The most tenuous group query

Abstract

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.

Graphical abstract

Keywords

tenuous group / pruning strategy / social network / group query

References

[1] Cui W, Xiao Y, Wang H, Wang W. Local search of communities in large graphs. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 2014, 991– 1002

[2] Li R H, Qin L, Yu J X, Mao R . Influential community search in large networks. Proceedings of the VLDB Endowment, 2015, 8( 5): 509– 520

[3] Seidman S B . Network structure and minimum degree. Social Networks, 1983, 5( 3): 269– 287

[4] Sozio M, Gionis A. The community-search problem and how to plan a successful cocktail party. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2010, 939– 948

[5] Zheng D, Liu J, Li R H, Aslay C, Chen Y C, Huang X. Querying intimate-core groups in weighted graphs. In: Proceedings of the 11th IEEE International Conference on Semantic Computing (ICSC). 2017, 156– 163

[6] Ebadian S, Huang X. Fast algorithm for K-truss discovery on public-private graphs. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 2258– 2264

[7] Huang X, Cheng H, Qin L, Tian W, Yu J X. Querying k-truss community in large and dynamic graphs. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 2014, 1311– 1322

[8] Huang X, Lakshmanan L V S, Yu J X, Cheng H . Approximate closest community search in networks. Proceedings of the VLDB Endowment, 2015, 9( 4): 276– 287

[9] Hu J, Cheng R, Chang K C C, Sankar A, Fang Y, Lam B Y H. Discovering maximal motif cliques in large heterogeneous information networks. In: Proceedings of the 35th IEEE International Conference on Data Engineering (ICDE). 2019, 746– 757

[10] Ma C, Cheng R, Lakshmanan L V S, Grubenmann T, Fang Y, Li X . LINC: a motif counting algorithm for uncertain graphs. Proceedings of the VLDB Endowment, 2019, 13( 2): 155– 168

[11] Hou B, Wang Z, Chen Q, Suo B, Fang C, Li Z, Ives Z G . Efficient maximal clique enumeration over graph data. Data Science and Engineering, 2016, 1( 4): 219– 230

[12] Li W. Finding tenuous groups in social networks. In: Proceedings of the 2018 IEEE International Conference on Data Mining Workshops (ICDMW). 2018, 284– 291

[13] Li Y, Sun H, He L, Huang J, Chen J, He H, Jia X . Querying tenuous group in attributed networks. The Computer Journal, 2020, bxaa115

[14] Shen C Y, Huang L H, Yang D N, Shuai H H, Lee W C, Chen M S. On finding socially tenuous groups for online social networks. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017, 415– 424

[15] Shen C Y, Shuai H H, Yang D N, Lee G S, Huang L H, Lee W C, Chen M S. On extracting socially tenuous groups for online social networks with k-triangles. IEEE Transactions on Knowledge and Data Engineering, 2020,

[16] Center for Substance Abuse Treatment. Substance abuse treatment: Group therapy. 2005

[17] Goldberg A V. Finding a Maximum Density Subgraph. Berkeley: University of California, 1984

[18] Tsourakakis C. The k-clique densest subgraph problem. In: Proceedings of the 24th International Conference on World Wide Web. 2015, 1122– 1132

[19] Mitzenmacher M, Pachocki J, Peng R, Tsourakakis C, Xu S C. Scalable large near-clique detection in large-scale networks via sampling. In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015, 815– 824

[20] Fang Y, Yu K, Cheng R, Lakshmanan L V S, Lin X . Efficient algorithms for densest subgraph discovery. Proceedings of the VLDB Endowment, 2019, 12( 11): 1719– 1732

[21] Charikar M. Greedy approximation algorithms for finding dense components in a graph. In: Proceedings of the 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization. 2000, 84– 95

[22] Bahmani B, Kumar R, Vassilvitskii S . Densest subgraph in streaming and MapReduce. Proceedings of the VLDB Endowment, 2012, 5( 5): 454– 465

[23] Bhaskara A, Charikar M, Chlamtac E, Feige U, Vijayaraghavan A. Detecting high log-densities: an O( n^1/4) approximation for densest k-subgraph . In: Proceedings of the 42nd ACM Symposium on Theory of Computing. 2010, 201– 210

[24] Qin L, Li R H, Chang L, Zhang C. Locally densest subgraph discovery. In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015, 965– 974

[25] Kannan R, Vinay V. Analyzing the Structure of Large Graphs. Forschungsinst. für Diskrete Mathematik, 1999

[26] Khuller S, Saha B. On finding dense subgraphs. In: Proceedings of the 36th International Colloquium on Automata, Languages, and Programming. 2009, 597– 608

RIGHTS & PERMISSIONS

Higher Education Press