Linear-time enumeration of maximal K-edge-connected subgraphs in large networks by random contraction
Linear-time enumeration of maximal K-edge-connected subgraphs in large networks by random contraction
复制标题
DOI：
10.1145/2505515.2505751
复制
发表时间：
2013-10
期刊：
影响因子：
--
通讯作者：
Takuya Akiba;Yoichi Iwata;Yuichi Yoshida
中科院分区：
文献类型：
--
作者：
Takuya Akiba;Yoichi Iwata;Yuichi Yoshida
从大型网络中捕获紧密相关的顶点集是许多应用中的一项重要任务，例如社会网络分析，生物信息学和Web链接研究。将图分解为k核组件是此任务的标准和有效方法，但获得的聚类可能不是良好连接的。最近提出了使用最大k-边连通子图的想法来解决这个问题。虽然我们可以用这个想法获得更好的聚类，但最先进的方法不足以处理具有数百万个顶点的大型网络。在本文中，我们提出了一个新的方法来分解一个图的最大k-边连通组件，基于随机收缩的边缘。我们的方法很容易实现，但大大提高了性能。我们的实验表明，我们的方法可以成功地分解大型网络，它比以前的方法快上千倍。此外，我们从理论上解释了为什么我们的方法在实践中是有效的。为了证明最大k边连通子图的重要性，我们还利用真实网络进行了实验，结果表明，许多k核组件具有较小的边连通性，它们可以被分解为大量的最大k边连通子图。
Capturing sets of closely related vertices from large networks is an essential task in many applications such as social network analysis, bioinformatics, and web link research. Decomposing a graph into k-core components is a standard and efficient method for this task, but obtained clusters might not be well-connected. The idea of using maximal k-edge-connected subgraphs was recently proposed to address this issue. Although we can obtain better clusters with this idea, the state-of-the-art method is not efficient enough to process large networks with millions of vertices. In this paper, we propose a new method to decompose a graph into maximal k-edge-connected components, based on random contraction of edges. Our method is simple to implement but improves performance drastically. We experimentally show that our method can successfully decompose large networks and it is thousands times faster than the previous method. Also, we theoretically explain why our method is efficient in practice. To see the importance of maximal k-edge-connected subgraphs, we also conduct experiments using real-world networks to show that many k-core components have small edge-connectivity and they can be decomposed into a lot of maximal k-edge-connected subgraphs.