Distributed Tip Decomposition on Large Bipartite Graphs |
| |
Authors: | Xu Zhou Tongfeng Weng Zhibang Yang Boren Li Ji Zhang Kenli Li |
| |
Affiliation: | College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China;Zhejiang Lab, Hangzhou 311100, China; College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China; National Supercomputing Center in Changsha, Changsha 410082, China |
| |
Abstract: | Tip decomposition has a pivotal role in mining cohesive subgraphs in bipartite graphs. It is a popular research topic with wide applications in document clustering, spam group detection, and analysis of affiliation networks. With the explosive growth of the bipartite graph data scale in these scenarios, it is necessary to use distributed methods to realize its effective storage. For this reason, this paper studies the problem of the tip decomposition on a bipartite graph in the distributed environment for the first time. Firstly, a new relay-based communication mode is proposed to realize effective message transmission when the given bipartite graph is decomposed in a distributed environment. Secondly, the Distributed Butterfly Counting (DBC) algorithm and the Distributed Tip Decomposition (DTD) algorithm are designed. In particular, a controllable parallel vertex activation strategy is proposed to solve the problem of memory overflow when DBC decomposes large-scale bipartite graphs. Finally, the message pruning strategy based on vertex priority and message validity pruning strategy are introduced to further improve the efficiency of the algorithm by reducing redundant communication and computing overhead. The experiment is deployed on the high-performance distributed computing platform of the National Supercomputing Center. The effectiveness and efficiency of the proposed algorithms are verified by experiments on several real datasets. |
| |
Keywords: | bipartite graph butterfly counting distributed systems tip decomposition |
|
| 点击此处可从《》浏览原始摘要信息 |
|
点击此处可从《》下载全文 |
|