Finding Maximal k-Edge-Connected Subgraphs from a Large Graph
Date
2012
Authors
Zhou, Rui
liu, Chengfei
Yu, Jeffrey
Liang, Weifa
Chen, Baichen
Li, Jianxin
Journal Title
Journal ISSN
Volume Title
Publisher
Conference Organising Committee
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.
Description
Keywords
Keywords: Connected component; High connectivity; Input graphs; K-connected; Large graphs; Minimum cut; Social Network Analysis; Subgraphs; Vertex degree; Web links; Bioinformatics; Cluster analysis; Social networking (online); Database systems
Citation
Collections
Source
ACM International Conference Proceeding Series
Type
Conference paper
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31
Downloads
File
Description