Fast Counting and Utilizing Induced 6-Cycles in Bipartite Networks
Jason Niu, Jarosław Żola, Ahmet Erdem Sarıyüce · IEEE Transactions on Knowledge and Data Engineering · 2025
Bipartite graphs are a powerful tool for modeling the interactions between two distinct groups. These bipartite relationships often feature small, recurring structural patterns called motifs which are building blocks for community structure. One promising structure 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 and utilizing induced 6-cycles in large bipartite networks. We first consider two adaptations inspired by previous works for cycle counting in bipartite networks. Then, we introduce a new approach for node triplets which offer a systematic way to count the induced 6-cycles, used inBatchTripletJoin. Our experimental evaluation shows thatBatchTripletJoinis significantly faster than the other algorithms while being scalable to large graph sizes and number of cores. On a network with$ 112M$edges,BatchTripletJoinis able to finish the computation in 78 mins by using 52 threads. In addition, we provide a new way to identify anomalous node triplets by comparing and contrasting the butterfly and induced 6-cycle counts of the nodes. We showcase several case studies on real-world networks from Amazon Kindle ratings, Steam game reviews, and Yelp ratings.