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

Na Li is a master candidate at Sun Yat-Sun University, China. Her research interests include spatial database and social network

Huaijie Zhu received the BSc degree from the Information Science Department, Kunming University of Science and Technology, China and the MSc degree from the Computer Science Department, Northeastern University, China. He received the PhD degree in computer science from Northeastern University, China in 2018. He is currently an associate professor with Sun Yat-Sen University, China. His research interests include spatial database, and data privacy. He is a member of the ACM and a senior member of the CCF

Wenhao Lu is a M candidate at Sun Yat-Sun University, China. His research interests include spatial database, social network

Ningning Cui is a senior lecture in the School of computer science, Anhui University, China. He graduated with a PhD degree in the Computer Science from Northeastern University, China in 2020. During his PhD degree, Dr. Cui worked as a visiting scholar in University of Western Australia (UWA), Australia from 2018 to 2019. His research interests include data security, privacy preserving, query processing and optimization, and big data analytics. He has published a series of high quality research papers in the international conferences and journals, including IEEE ICDE, IEEE TII, WWW Journal, DASFAA, etc. He has served as different roles in academic committees, e.g., the conference PC members in CIKM2021, ADMA 2019 and 2020, and the reviewer of journals such as WWWJ, FCS, Neurocomputing, etc

Wei Liu received the BS degree from Shanghai University, MS degree from South China University of Technology, Ph.D. degree from Sun Yat-Sen University, China in 2010, 2013, 2018, respectively, all in computer science. He is doing a post-doctoral fellow in Sun Yat-sen University from 2018. His current research interests are in the areas of recommendation system, user behavior learning in location-based social network, spatio-temporal data mining and deep learning

Jian Yin received the BS, MS, and PhD degrees from Wuhan University, China in 1989, 1991, and 1994, respectively, all in computer science. He joined Sun Yat-Sen University, China in July 1994 and now he is a professor of Data and Computer Science School. He has published more than 100 refereed journal and conference papers. His current research interests are in the areas of Data Mining, Artificial Intelligence, and Machine Learning. He is a senior member of China Computer Federation

Jianliang Xu received the BEng degree in computer science and engineering from Zhejiang University, China and the PhD degree in computer science from the Hong Kong University of Science and Technology, China. He is a professor with the Department of Computer Science, Hong Kong Baptist University, China. He held visiting positions with Pennsylvania State University, USA and Fudan University, China. His research interests include big data management, mobile computing, and data security and privacy. He has published more than 150 technical papers in these areas. He has served as a program cochair/vice chair for a number of major international conferences including IEEE ICDCS 2012, IEEE CPSNA 2015, and APWeb-WAIM 2018. He is an associate editor of the IEEE Transactions on Knowledge and Data Engineering and the Proceedings of the VLDB Endowment 2018

Wang-Chien Lee received the PhD degree in computer and information science from the Ohio State University, USA. Currently, he is an associate professor with the Department of Computer Science and Engineering, the Pennsylvania State University, USA, leading the Intelligent Pervasive Data Access (iPDA) research group to pursue cross-area research in data management, pervasive/mobile computing, and networking. He has published more than 280 research papers in these areas. He serves as an associate editor on the editorial boards of the IEEE Transactions on Service Computing (TSC) and the ACM Transactions on Intelligent Systems and Technology (TIST). He is a member of the IEEE

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, doi: 10.1109/TKDE.2020.3025911

[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

Acknowledgements

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).

RIGHTS & PERMISSIONS

2023 Higher Education Press