Finding Maximal K-Edge-Connected Subgraphs From a Large Graph

Date Added: Mar 2012
Format: PDF

In this paper, the authors study how to find maximal k-edge-connected sub-graphs from a large graph. k-edge-connected sub-graphs 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 sub-graph further requires high connectivity within a sub-graph (a stronger requirement), and hence defines a more closely related vertex cluster. To find maximal k-edge-connected sub-graphs 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.