We define a statistical ensemble of nondegenerate graphs, i.e., graphs without multiple-connections and self-connections between nodes. The node degree distribution is arbitrary, but the nodes are assumed to be uncorrelated. This completes our earlier publication [Phys. Rev. 64, 046118 (2001)] where trees and degenerate graphs were considered. An efficient algorithm generating nondegenerate graphs is constructed. The corresponding computer code is available on request. Finite-size effects in scale-free graphs, i.e., those where the tail of the degree distribution falls like $n^{-\beta },$ are carefully studied. We find that in the absence of dynamical internode correlations the degree distribution is cut at a degree value scaling like $N^{\gamma },$ with $\gamma =\min [1/2,1/(\beta -1\left)\right],$ where N is the total number of nodes. The consequence is that, independently of any specific model, the internode correlations seem to be a necessary ingredient of the physics of scale-free networks observed in nature.

• Received 2 July 2002

DOI:https://doi.org/10.1103/PhysRevE.67.046118