|
|
The most tenuous group query |
Na LI1,2, Huaijie ZHU2,3(), Wenhao LU1,2, Ningning CUI4, Wei LIU2,3, Jian YIN2,3, Jianliang XU5, Wang-Chien LEE6 |
1. School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510006, China 2. Laboratory of Big Data Analysis and Processing, Guangzhou 510006, China 3. School of Artificial Intelligence, Sun Yat-Sen University, Guangzhou 510006, China 4. Department of Computer Science, Anhui University, Hefei 230601, China 5. Department of Computer Science, Hong Kong Baptist University, Hong Kong 999077, China 6. Department of Computer Science, The Pennsylvania State University, State College 19019, USA |
|
|
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.
|
Keywords
tenuous group
pruning strategy
social network
group query
|
Corresponding Author(s):
Huaijie ZHU
|
Just Accepted Date: 28 January 2022
Issue Date: 04 August 2022
|
|
1 |
W, Cui Y, Xiao H, Wang W Wang. Local search of communities in large graphs. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. 2014, 991– 1002
|
2 |
R H, Li L, Qin J X, Yu R Mao . Influential community search in large networks. Proceedings of the VLDB Endowment, 2015, 8( 5): 509– 520
|
3 |
S B Seidman . Network structure and minimum degree. Social Networks, 1983, 5( 3): 269– 287
|
4 |
M, Sozio A Gionis. 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 |
D, Zheng J, Liu R H, Li C, Aslay Y C, Chen X Huang. Querying intimate-core groups in weighted graphs. In: Proceedings of the 11th IEEE International Conference on Semantic Computing (ICSC). 2017, 156– 163
|
6 |
S, Ebadian X Huang. 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 |
X, Huang H, Cheng L, Qin W, Tian J X Yu. 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 |
X, Huang L V S, Lakshmanan J X, Yu H Cheng . Approximate closest community search in networks. Proceedings of the VLDB Endowment, 2015, 9( 4): 276– 287
|
9 |
J, Hu R, Cheng K C C, Chang A, Sankar Y, Fang B Y H Lam. 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 |
C, Ma R, Cheng L V S, Lakshmanan T, Grubenmann Y, Fang X Li . LINC: a motif counting algorithm for uncertain graphs. Proceedings of the VLDB Endowment, 2019, 13( 2): 155– 168
|
11 |
B, Hou Z, Wang Q, Chen B, Suo C, Fang Z, Li Z G Ives . Efficient maximal clique enumeration over graph data. Data Science and Engineering, 2016, 1( 4): 219– 230
|
12 |
W Li. Finding tenuous groups in social networks. In: Proceedings of the 2018 IEEE International Conference on Data Mining Workshops (ICDMW). 2018, 284– 291
|
13 |
Y, Li H, Sun L, He J, Huang J, Chen H, He X Jia . Querying tenuous group in attributed networks. The Computer Journal, 2020, bxaa115
https://doi.org/10.1093/comjnl/bxaa115
|
14 |
C Y, Shen L H, Huang D N, Yang H H, Shuai W C, Lee M S Chen. 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 |
C Y, Shen H H, Shuai D N, Yang G S, Lee L H, Huang W C, Lee M S Chen. 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 |
A V Goldberg. Finding a Maximum Density Subgraph. Berkeley: University of California, 1984
|
18 |
C Tsourakakis. The k-clique densest subgraph problem. In: Proceedings of the 24th International Conference on World Wide Web. 2015, 1122– 1132
|
19 |
M, Mitzenmacher J, Pachocki R, Peng C, Tsourakakis S C Xu. 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 |
Y, Fang K, Yu R, Cheng L V S, Lakshmanan X Lin . Efficient algorithms for densest subgraph discovery. Proceedings of the VLDB Endowment, 2019, 12( 11): 1719– 1732
|
21 |
M Charikar. 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 |
B, Bahmani R, Kumar S Vassilvitskii . Densest subgraph in streaming and MapReduce. Proceedings of the VLDB Endowment, 2012, 5( 5): 454– 465
|
23 |
A, Bhaskara M, Charikar E, Chlamtac U, Feige A Vijayaraghavan. Detecting high log-densities: an O( n1/4) approximation for densest k-subgraph . In: Proceedings of the 42nd ACM Symposium on Theory of Computing. 2010, 201– 210
|
24 |
L, Qin R H, Li L, Chang C Zhang. Locally densest subgraph discovery. In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015, 965– 974
|
25 |
R, Kannan V Vinay. Analyzing the Structure of Large Graphs. Forschungsinst. für Diskrete Mathematik, 1999
|
26 |
S, Khuller B Saha. On finding dense subgraphs. In: Proceedings of the 36th International Colloquium on Automata, Languages, and Programming. 2009, 597– 608
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|