计算机科学
杠杆(统计)
效率低下
图形
桁架
群落结构
算法
理论计算机科学
人工智能
数学
组合数学
结构工程
工程类
经济
微观经济学
作者
Xuankun Liao,Qing Liu,Xin Huang,Jianliang Xu
出处
期刊:Proceedings of the VLDB Endowment
[VLDB Endowment]
日期:2024-04-01
卷期号:17 (8): 1816-1829
标识
DOI:10.14778/3659437.3659440
摘要
Community search aims to retrieve dense subgraphs that contain the query vertices. While many effective community models and algorithms have been proposed in the literature, none of them address the unique challenges posed by streaming graphs, where edges are continuously generated over time. In this paper, we investigate the problem of truss-based community search over streaming directed graphs. To address this problem, we first present a peeling-based algorithm that iteratively removes edges that do not meet the support constraints. To improve the efficiency of the peeling-based algorithm, we propose three optimizations that leverage the time information of the streaming graph and the structural information of trusses. As the peeling-based algorithm may suffer from inefficiency when the input peeling graph is large, we further propose a novel order-based algorithm that preserves the community by maintaining the deletion order of edges in the peeling algorithm. Extensive experimental results on real-world datasets show that our proposed algorithms outperform the baseline by up to two orders of magnitude in terms of throughput.
科研通智能强力驱动
Strongly Powered by AbleSci AI