Please use this identifier to cite or link to this item:
Scopus Web of ScienceĀ® Altmetric
Type: Conference paper
Title: Finding maximal k-edge-connected subgraphs from a large graph
Author: Zhou, R.
Liu, C.
Yu, J.
Liang, W.
Chen, B.
Li, J.
Citation: Proceedings of the 15th International Conference on Extending Database Technology, 2012 / pp.480-491
Publisher: ACM
Issue Date: 2012
ISBN: 9781450307901
Conference Name: 15th International Conference on Extending Database Technology (EDBT) (27 Mar 2012 - 30 Mar 2012 : Berlin, Germany)
Statement of
Rui Zhou, Chengfei Liu, Jeffrey Xu Yu, Weifa Liang, Baichen Chen, Jianxin Li
Abstract: In this paper, we study how to find maximal k-edge-connected subgraphs from a large graph. k-edge-connected subgraphs can be used to capture closely related vertices, and finding such vertex clusters is interesting in many applications, e.g., social network analysis, bioinformatics, web link research. Compared with other explicit structures for modeling vertex clusters, such as quasi-clique, k-core, which only set the requirement on vertex degrees, k-edge-connected subgraph further requires high connectivity within a subgraph (a stronger requirement), and hence defines a more closely related vertex cluster. To find maximal k-edge-connected subgraphs from a graph, a basic approach is to repeatedly apply minimum cut algorithm to the connected components of the input graph until all connected components are k-connected. However, the basic approach is very expensive if the input graph is large. To tackle the problem, we propose three major techniques: vertex reduction, edge reduction and cut pruning. These speed-up techniques are applied on top of the basic approach. We conduct extensive experiments and show that the speed-up techniques are very effective.
Rights: Copyright 2012 ACM
RMID: 0030060983
DOI: 10.1145/2247596.2247652
Grant ID:
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_109517.pdfRestricted Access250.5 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.