论文标题
有效的Bitruss分解用于大规模两部分图
Efficient Bitruss Decomposition for Large-scale Bipartite Graphs
论文作者
论文摘要
两分图中的凝聚力子图挖掘最近成为一个流行的研究主题。一个重要的结构k-bitruss是最大的内聚子图，其中每个边缘至少包含在k蝴蝶中（即（2，2）-Bicliques）。在本文中，我们研究了Bitruss的分解问题，该问题旨在找到k> = 0的所有k-竞争。在这个剥离过程中，这些技术很耗时，以列举每个边缘的所有支撑蝴蝶。为了放松这个问题，我们首先提出了一个新颖的在线索引 - 将蝴蝶压缩成k型束缚的Be-Index（即（2，k） - 贝克利斯）。基于BE-INDEX，提出了新的Bitruss分解算法BIT-BU，以及两个基于批次的优化，以有效地完成剥离过程的蝴蝶枚举。此外，设计了BIT-PC算法，该算法更有效地防止用高蝴蝶支撑处理边缘。从理论上讲，我们表明我们的新算法大大降低了现有算法的时间复杂性。此外，我们在实际数据集上进行了广泛的实验，结果表明，我们的新技术可以将最新技术加快提高两个数量级。
Cohesive subgraph mining in bipartite graphs becomes a popular research topic recently. An important structure k-bitruss is the maximal cohesive subgraph where each edge is contained in at least k butterflies (i.e., (2, 2)-bicliques). In this paper, we study the bitruss decomposition problem which aims to find all the k-bitrusses for k >= 0. The existing bottom-up techniques need to iteratively peel the edges with the lowest butterfly support. In this peeling process, these techniques are time-consuming to enumerate all the supporting butterflies for each edge. To relax this issue, we first propose a novel online index -- the BE-Index which compresses butterflies into k-blooms (i.e., (2, k)-bicliques). Based on the BE-Index, the new bitruss decomposition algorithm BiT-BU is proposed, along with two batch-based optimizations, to accomplish the butterfly enumeration of the peeling process in an efficient way. Furthermore, the BiT-PC algorithm is devised which is more efficient against handling the edges with high butterfly supports. We theoretically show that our new algorithms significantly reduce the time complexities of the existing algorithms. Also, we conduct extensive experiments on real datasets and the result demonstrates that our new techniques can speed up the state-of-the-art techniques by up to two orders of magnitude.
