Counting Induced 6-Cycles in Bipartite Graphs
Counting Induced 6-Cycles in Bipartite Graphs
复制标题
DOI：
10.1145/3545008.3545076
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Jason Niu;J. Zola;Ahmet Erdem Sarıyüce
中科院分区：
文献类型：
--
作者：
Jason Niu;J. Zola;Ahmet Erdem Sarıyüce
现实世界中的各种复杂网络最好用二分图表示，例如用户-产品，论文-作者，演员-电影关系。基于模体的分析对网络有很大的好处，二分图也不例外。二部图中最小的非平凡子图是（2，2）-biclique，也称为蝴蝶。虽然蝴蝶是简洁的，但它们在捕获来自同一节点集的两个以上节点之间的高阶关系方面受到限制。在这种情况下，一个有前途的结构是诱导6-循环，它由每个节点集上的三个节点组成，形成一个循环，每个节点正好有两个边缘。本文利用并行算法研究了诱导6-圈的计数问题。据我们所知，这是第一次研究诱导6周期计数。我们首先考虑两个改编的基础上，以前的作品在二分网络的周期计数。然后，我们介绍了一种新的方法的基础上的节点三元组，并提供了一个系统的方法来计算诱导的6-圈。我们的最终算法BatchTripletJoin在根节点之间是可并行的，并使用最小的全局存储来节省内存。我们在52核机器上的实验评估表明，BatchTripletJoin比其他算法快得多，同时可扩展到大图形大小和核数。在一个有112 M条边的网络上，BatchTripletJoin能够使用52个线程在78分钟内完成计算。
Various complex networks in real-world applications are best represented as a bipartite graph, such as user-product, paper-author, and actor-movie relations. Motif-based analysis has substantial benefits for networks and bipartite graphs are no exception. The smallest non-trivial subgraph in a bipartite graph is a (2,2)-biclique, also known as a butterfly. Although butterflies are succinct, they are limited in capturing the higher-order relations between more than two nodes from the same node set. One promising structure in this context is the induced 6-cycle which consists of three nodes on each node set forming a cycle where each node has exactly two edges. In this paper, we study the problem of counting induced 6-cycles through parallel algorithms. To the best of our knowledge, this is the first study on induced 6-cycle counting. We first consider two adaptations based on previous works for cycle counting in bipartite networks. Then, we introduce a new approach based on the node triplets and offer a systematic way to count the induced 6-cycles. Our final algorithm, BatchTripletJoin, is parallelizable across root nodes and uses minimal global storage to save memory. Our experimental evaluation on a 52 core machine shows that BatchTripletJoin is significantly faster than the other algorithms while being scalable to large graph sizes and number of cores. On a network with 112M edges, BatchTripletJoin is able to finish the computation in 78 mins by using 52 threads.