Efficient Computation of K-Edge Connected Components: An Empirical Analysis

Graphs play a pivotal role in representing complex relationships across various domains, such as social networks and bioinformatics. Key to many applications is the identification of communities or clusters within these graphs, with k-edge connected components emerging as an important method for finding well-connected communities. Although there exist other techniques such as k-plexes, k-cores, and k-trusses, they are known to have some limitations. This study delves into four existing algorithms designed for computing maximal k-edge connected subgraphs. We conduct a thorough study of these algorithms to understand the strengths and weaknesses of each algorithm in detail and propose algorithmic refinements to optimize their performance. We provide a careful implementation of each of these algorithms, using which we analyze and compare their performance on graphs of varying sizes. Our work is the first to provide such a direct experimental comparison of these four methods. Finally, we also address an incorrect claim made in the literature about one of these algorithms.