Efficient Community Search over Large Directed Graph: An Augmented Index-based Approach

Efficient Community Search over Large Directed Graph: An Augmented Index-based Approach

Yankai Chen, Jie Zhang, Yixiang Fang, Xin Cao, Irwin King

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 3544-3550. https://doi.org/10.24963/ijcai.2020/490

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 [Fang et al., 2019b]; 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.
Keywords:
Multidisciplinary Topics and Applications: Web Analysis of Communities
Data Mining: Big Data, Large-Scale Systems
Data Mining: Mining Graphs, Semi Structured Data, Complex Data