TY - GEN

T1 - Efficiently computing k-edge connected components via graph decomposition

AU - Chang, Lijun

AU - Yu, Jeffrey Xu

AU - Qin, Lu

AU - Lin, Xuemin

AU - Liu, Chengfei

AU - Liang, Weifa

PY - 2013

Y1 - 2013

N2 - Efficiently computing k-edge connected components in a large graph, G = (V, E), where V is the vertex set and E is the edge set, is a long standing research problem. It is not only fundamental in graph analysis but also crucial in graph search optimization algorithms. Consider existing techniques for computing k-edge connected components are quite time consuming and are unlikely to be scalable for large scale graphs, in this paper we firstly propose a novel graph decomposition paradigm to iteratively decompose a graph G for computing its k-edge connected components such that the number of drilling-down iterations h is bounded by the "depth" of the k-edge connected components nested together to form G, where h usually is a small integer in practice. Secondly, we devise a novel, efficient threshold-based graph decomposition algorithm, with time complexity O(l × |E|), to decompose a graph G at each iteration, where l usually is a small integer with l ≪ |V|. As a result, our algorithm for computing k-edge connected components significantly improves the time complexity of an existing state-of-the-art technique from O(|V|2|E| + |V|3log|V|) to O(h×l× |E|). Finally, we conduct extensive performance studies on large real and synthetic graphs. The performance studies demonstrate that our techniques significantly outperform the state-of-the-art solution by several orders of magnitude.

AB - Efficiently computing k-edge connected components in a large graph, G = (V, E), where V is the vertex set and E is the edge set, is a long standing research problem. It is not only fundamental in graph analysis but also crucial in graph search optimization algorithms. Consider existing techniques for computing k-edge connected components are quite time consuming and are unlikely to be scalable for large scale graphs, in this paper we firstly propose a novel graph decomposition paradigm to iteratively decompose a graph G for computing its k-edge connected components such that the number of drilling-down iterations h is bounded by the "depth" of the k-edge connected components nested together to form G, where h usually is a small integer in practice. Secondly, we devise a novel, efficient threshold-based graph decomposition algorithm, with time complexity O(l × |E|), to decompose a graph G at each iteration, where l usually is a small integer with l ≪ |V|. As a result, our algorithm for computing k-edge connected components significantly improves the time complexity of an existing state-of-the-art technique from O(|V|2|E| + |V|3log|V|) to O(h×l× |E|). Finally, we conduct extensive performance studies on large real and synthetic graphs. The performance studies demonstrate that our techniques significantly outperform the state-of-the-art solution by several orders of magnitude.

KW - Graph decomposition

KW - K-edge connected components

KW - Minimum cut

UR - http://www.scopus.com/inward/record.url?scp=84880534983&partnerID=8YFLogxK

U2 - 10.1145/2463676.2465323

DO - 10.1145/2463676.2465323

M3 - Conference contribution

SN - 9781450320375

T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data

SP - 205

EP - 216

BT - SIGMOD 2013 - International Conference on Management of Data

PB - Association for Computing Machinery

T2 - 2013 ACM SIGMOD Conference on Management of Data, SIGMOD 2013

Y2 - 22 June 2013 through 27 June 2013

ER -