Efficient Bitruss Decomposition for Large-scale Bipartite Graphs
Efficient Bitruss Decomposition for Large-scale Bipartite Graphs
复制标题
DOI：
10.1109/icde48307.2020.00063
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Kai Wang;Xuemin Lin;Lu Qin;Wenjie Zhang;Ying Zhang
中科院分区：
文献类型：
--
作者：
Kai Wang;Xuemin Lin;Lu Qin;Wenjie Zhang;Ying Zhang
二部图的内聚子图挖掘是近年来研究的热点。一个重要的结构k-bitruss是最大内聚子图，其中每条边至少包含在k个蝴蝶（即(2,2)-bicliques）中。本文研究了以求k≥0的所有k-比特线为目标的比特线分解问题。现有的自底向上技术需要迭代地剥离最低蝴蝶支撑的边缘。在这种剥皮过程中，这些技术需要花费大量时间来枚举每条边的所有支撑蝴蝶。为了解决这个问题，我们首先提出了一种新的在线索引- BE-Index，它将蝴蝶压缩成k-bloom（即(2,k)-bicliques）。在BE-Index的基础上，提出了一种新的bitrus分解算法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 results demonstrate that our new techniques can speed up the state-of-the-art techniques by up to two orders of magnitude.