Efficient Sink-Reachability Analysis via Graph Reduction

Jens Dietrich

doi:10.1109/TKDE.2021.3052710

Efficient Sink-Reachability Analysis via Graph Reduction

2022-11-01

0

PRE

AI

DOI：10.1109/TKDE.2021.3052710

Original

Original request for help

Save

Abstract

En 中文

The reachability problem on directed graphs, asking whether two vertices are connected via a directed path, is an elementary problem that has been well-studied. In this paper, we study a variation of the elementary reachability problem, called the sink-reachability problem, which can be found in many applications such as static program analysis, social network analysis, large scale web graph analysis, XML document link path analysis, and the study of gene regulation relationships. To scale sink-reachablity analysis to large graphs, we develop a highly scalable sink-reachability preserving graph reduction strategy for input sink graphs, by using a composition framework. That is, individual sink-reachability preserving condensation operators, each running in linear time, are pipelined together to produce graph reduction algorithms that result in close to maximum reduction, while keeping the computation efficient. Experiments on large real-world sink graphs demonstrate the efficiency and effectiveness of our compositional approach to sink-reachability preserving graph reduction with a reduction rate of up to 99.74 percent for vertices and a rate of up to 99.46 percent for edges.

Keywords:

Social networking (online)

Indexing

XML

Directed graphs

Scalability

Time complexity

Query processing

Sink reachability

graph reduction

modular decomposition

dominator

Efficient Sink-Reachability Analysis via Graph Reduction

Abstract

AI Summary

Journal

Organization