TY - GEN
T1 - I/O Efficient Max-Truss Computation in Large Static and Dynamic Graphs
AU - Jiang, Jiaqi
AU - Zhang, Qi
AU - Li, Rong Hua
AU - Dai, Qiangqiang
AU - Wang, Guoren
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2024
Y1 - 2024
N2 - Cohesive sub graph mining has received much at-tention in the area of graph analysis. A k-truss, defined as a sub graph where each edge is associated with at least k-2 triangles, serves as a fundamental graph analysis tool. Among all k-trusses, the kmax-truss with the maximum k value holds significant importance in various practical applications such as community search and keyword retrieval. Furthermore, it is also closely related to many graph analysis problems, particularly those computational complexity problems parameterized by k. However, real-world graphs often exhibit large-scale characteris-tics, making it impractical to fully load them into main memory. In this paper, we investigate the problem of finding the kmax-truss in external memory settings. To address this problem, we propose an 110 efficient algorithm following a semi-external model, which only allows node information to be loaded into main memory. Our approach leverages greedy strategies and a binary search framework to efficiently find the kmax-truss. Subsequently, an elegant data structure is proposed to significantly reduce 110 costs. Furthermore, to address dynamic graph updates, we develop an 110 efficient kmax-truss maintenance algorithm based on the local-first update technique. To evaluate the performance of our algorithms, we conduct extensive experiments. The results demonstrate the high efficiency and scalability of our algorithms, which are at least two orders of magnitude faster in runtime and at least one order of magnitude lower in terms of 110 costs compared to the state-of-the-art solutions.
AB - Cohesive sub graph mining has received much at-tention in the area of graph analysis. A k-truss, defined as a sub graph where each edge is associated with at least k-2 triangles, serves as a fundamental graph analysis tool. Among all k-trusses, the kmax-truss with the maximum k value holds significant importance in various practical applications such as community search and keyword retrieval. Furthermore, it is also closely related to many graph analysis problems, particularly those computational complexity problems parameterized by k. However, real-world graphs often exhibit large-scale characteris-tics, making it impractical to fully load them into main memory. In this paper, we investigate the problem of finding the kmax-truss in external memory settings. To address this problem, we propose an 110 efficient algorithm following a semi-external model, which only allows node information to be loaded into main memory. Our approach leverages greedy strategies and a binary search framework to efficiently find the kmax-truss. Subsequently, an elegant data structure is proposed to significantly reduce 110 costs. Furthermore, to address dynamic graph updates, we develop an 110 efficient kmax-truss maintenance algorithm based on the local-first update technique. To evaluate the performance of our algorithms, we conduct extensive experiments. The results demonstrate the high efficiency and scalability of our algorithms, which are at least two orders of magnitude faster in runtime and at least one order of magnitude lower in terms of 110 costs compared to the state-of-the-art solutions.
UR - http://www.scopus.com/inward/record.url?scp=85200472878&partnerID=8YFLogxK
U2 - 10.1109/ICDE60146.2024.00249
DO - 10.1109/ICDE60146.2024.00249
M3 - Conference contribution
AN - SCOPUS:85200472878
T3 - Proceedings - International Conference on Data Engineering
SP - 3217
EP - 3229
BT - Proceedings - 2024 IEEE 40th International Conference on Data Engineering, ICDE 2024
PB - IEEE Computer Society
T2 - 40th IEEE International Conference on Data Engineering, ICDE 2024
Y2 - 13 May 2024 through 17 May 2024
ER -