I/O efficient ECC graph decomposition via graph reduction
- Publication Type:
- Conference Proceeding
- Citation:
- Proceedings of the VLDB Endowment, 2016, 9 (7), pp. 516 - 527
- Issue Date:
- 2016-01-01
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
© 2016 VLDB Endowment 21508097/16/03. The problem of computing k-edge connected components (k-ECCs) of a graph G for a specific k is a fundamental graph problemand has been investigated recently. In this paper, we study the problemof ECC decomposition, which computes the k-ECCs of a graphG for all k values. ECC decomposition can be widely applied ina variety of applications such as graph-topology analysis, communitydetection, Steiner component search, and graph visualization.A straightforward solution for ECC decomposition is to apply theexisting k-ECC computation algorithm to compute the k-ECCs forall k values. However, this solution is not applicable to large graphsfor two challenging reasons. First, all existing k-ECC computationalgorithms are highly memory intensive due to the complex datastructures used in the algorithms. Second, the number of possiblek values can be very large, resulting in a high computational costwhen each k value is independently considered. In this paper, weaddress the above challenges, and study I/O efficient ECC decompositionvia graph reduction. We introduce two elegant graph reductionoperators which aim to reduce the size of the graph loadedin memory while preserving the connectivity information of a certainset of edges to be computed for a specific k. We also proposethree novel I/O efficient algorithms, Bottom-Up, Top-Down, andHybrid, that explore the k values in different orders to reduce the redundantcomputations between different k values. We analyze theI/O and memory costs for all proposed algorithms. In our experiments, we evaluate our algorithms using seven real large datasetswith various graph properties, one of which contains 1:95 billionedges. The experimental results show that our proposed algorithmsare scalable and efficient.
Please use this identifier to cite or link to this item: