Correlations in connected random graphs

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...

Full description

Saved in:
Bibliographic Details
Published in:Physical review. E, Statistical, nonlinear, and soft matter physics Statistical, nonlinear, and soft matter physics, 2008-03, Vol.77 (3 Pt 2), p.036124-036124, Article 036124
Main Authors: Bialas, Piotr, Oleś, Andrzej K
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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.
ISSN:1539-3755
1550-2376
DOI:10.1103/PhysRevE.77.036124