Correlations in connected random graphs

Abstract

We study the properties of the giant connected component in random graphs with arbitrary degree distribution. We concentrate on the degree-degree correlations. We show that the adjoining nodes in the giant connected component are correlated and derive analytic formulas for the joint nearest-neighbor degree probability distribution. Using those results we describe the correlations in maximal entropy connected random graphs. We show that connected graphs are disassortative and that correlations are strongly related to the presence of one-degree nodes (leaves). We propose an efficient algorithm for generating connected random graphs. We illustrate our results with several examples.

Synchronized with the published version; 11 pages and 11 figures.

References in corpus (3)

• Generation of uncorrelated random scale-free networks
• Homogeneous complex networks
• A program generating homogeneous random graphs with given weights

Cited by in corpus (11)

• Zero Pearson Coefficient for Strongly Correlated Growing Trees
• Disassortativity of percolating clusters in random networks
• Limited path entanglement percolation in quantum complex networks
• Core organization of directed complex networks
• Structure of percolating clusters in random clustered networks
• Degree correlations in graphs with clique clustering
• Emergence of Long-Range Correlations in Random Networks
• Bifractality of fractal scale-free networks
• Disassortativity of random critical branching trees
• Long-range disassortative correlations in generic random trees
• Random walks on bifractal networks