Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs

2021 
In recent years, cohesive subgraph mining in bipartite graphs becomes a popular research topic. An important cohesive subgraph model 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 \ge 0$$ . The existing algorithms follow a bottom-up strategy which peels the edges with the lowest butterfly support iteratively. In this peeling process, these algorithms are time-consuming to enumerate all the supporting butterflies for each edge. To solve this issue, we propose a novel online index, the $$\mathsf {BE}$$ - $$\mathsf {Index}$$ which compresses butterflies into k-blooms (i.e., (2, k)-bicliques). Based on the $$\mathsf {BE}$$ - $$\mathsf {Index}$$ , the new bitruss decomposition algorithm $$\mathsf {BiT}$$ - $$\mathsf {BU}$$ is proposed, along with two batch-based optimizations, to accomplish the butterfly enumeration of the peeling process efficiently. Furthermore, the $$\mathsf {BiT}$$ - $$\mathsf {PC}$$ algorithm is designed which is more efficient against handling the edges with high butterfly supports. Besides, we explore shared-memory parallel solutions to handle large graphs in a more efficient way. In the parallel algorithms, we propose effective techniques to reduce conflicts among threads. We theoretically show that our new algorithms significantly reduce the time complexities of the existing algorithms. In addition, extensive empirical evaluations are conducted on real-world datasets. The experimental results further validate the effectiveness of the bitruss model and demonstrate that our proposed solutions significantly outperform the state-of-the-art techniques by several orders of magnitude.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    69
    References
    4
    Citations
    NaN
    KQI
    []