Statistics of cycles: how loopy is your network?
Journal of Physics A: Mathematical and General, 38 (21):
4589--4595 (2005)DOI: 10.1088/0305-4470/38/21/005
Abstract
We study the distribution of cycles of length h in large networks (of size N 1) and find it to be an excellent ergodic estimator, even in the extreme inhomogeneous case of scale-free networks. The distribution is sharply peaked around a characteristic cycle length, h \~ N α . Our results suggest that h and the exponent α might usefully characterize broad families of networks. In addition to an exact counting of cycles in hierarchical nets, we present a Monte Carlo sampling algorithm for approximately locating h and reliably determining α. Our empirical results indicate that for small random scale-free nets of degree exponent λ, α = 1/(λ − 1), and α grows as the nets become larger.
