A Fast Messages-Passing Algorithm for Counting Short Cycles in Bipartite Graphs

As short cycles have significant impact on the low-density parity-check (LDPC) decoding performance, counting short cycles for LDPC code graphs (more generally, for bipartite graphs) are important. In this paper, we first develop a new efficient implementation for the improved message-passing algorithm (IMPA) for counting short cycles of lengths between g and 2l<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</inf> in bipartite graphs for any given l<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</inf> ∈ [g/2, g − 1], where g is the girth. Building upon this, we further propose a fast message-passing algorithm (FMPA) by employing a level-wise activation strategy. The FMPA has storage complexity ${\mathcal{O}}(\delta |E|)$ and computational complexity ${\mathcal{O}}\left( {\left( {{l_{\max }} - g/2 + 1} \right)|E{|^2}} \right)$, where δ is the minimum of the maximum node degree of each partition and |E| is the number of edges. Extensive numerical results demonstrate that, the FMPA can always run significantly faster than the IMPA for any l<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</inf>, and generally run faster than the modified breadth-first search algorithm for l<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">max</inf> = g/2+1, g/2+2.