Algorithm for counting large directed loops

Abstract

We derive a Belief-Propagation algorithm for counting large loops in a directed network. We evaluate the distribution of the number of small loops in a directed random network with given degree sequence. We apply the algorithm to a few characteristic directed networks of various network sizes and loop structures and compare the algorithm with exhaustive counting results when possible. The algorithm is adequate in estimating loop counts for large directed networks and can be used to compare the loop structure of directed networks and their randomized counterparts.

(9 pages, 3 figures)

References in corpus (11)

• Cut-offs and finite size effects in scale-free networks
• Topology of biological networks and reliability of information processing
• Maximum Performance at Minimum Cost in Network Synchronization
• Number of loops of size h in growing scale-free networks
• Loops of any size and Hamilton cycles in random scale-free networks
• Uncorrelated Random Networks
• Statistics of Cycles: How Loopy is your Network?
• Dynamics on Complex Networks and Applications
• Random replicators with asymmetric couplings
• On the number of circuits in random graphs
• An algorithm for counting circuits: application to real-world and random graphs

Cited by in corpus (4)

• Spin glass approach to the feedback vertex set problem
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Inherent directionality explains the lack of feedback loops in empirical networks
• Unevenness of Loop Location in Complex Networks