Utilizing community centers to answer reachability queries for large graphs

As a fundamental problem, reach ability query has been always the research emphasis in many applications in the near 20 years. Especially with the coming of the big data era, its efficiency plays a critical role. Although there are many research results for this issue, they all reach a scalability bottleneck. In this paper, we propose an index structure utilizing community center, i.e. to select a group of vertices from the original graph and construct a sub graph. With this sub graph, we can answer reach ability queries rapidly. The experimental result shows that our approach is superior to the-state-of-the-art algorithms including construction time, index size and query time.