Loading...
Please wait, while we are loading the content...
Similar Documents
An Augmented Index-based Efficient Community Search for Large Directed Graphs
| Content Provider | arXiv |
|---|---|
| Author | Chen, Yankai Zhang, Jie Fang, Yixiang Cao, Xin King, Irwin |
| Date of Submission | 2023-11-16 |
| Abstract | Given a graph G and a query vertex q, the topic of community search (CS), aiming to retrieve a dense subgraph of G containing q, has gained much attention. Most existing works focus on undirected graphs which overlooks the rich information carried by the edge directions. Recently, the problem of community search over directed graphs (or CSD problem) has been studied; it finds a connected subgraph containing q, where the in-degree and out-degree of each vertex within the subgraph are at least k and l, respectively. However, existing solutions are inefficient, especially on large graphs. To tackle this issue, in this paper, we propose a novel index called D-Forest, which allows a CSD query to be completed within the optimal time cost. We further propose efficient index construction methods. Extensive experiments on six real large graphs show that our index-based query algorithm is up to two orders of magnitude faster than existing solutions. |
| Related Links | https://arxiv.org/pdf/2311.06487.pdf |
| arXiv | 2311.06487 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Computer Science - Databases Computer Science |
| Content Type | Text |
| Resource Type | Article |
| Subject | Computer Science |
