Correlations in connected random graphs

作     者：Piotr Bialas Andrzej K. Oleś 

作者机构：Marian Smoluchowski Institute of Physics Jagellonian University Reymonta 4 30-059 Krakow Poland Mark Kac Complex Systems Research Centre Faculty of Physics Astronomy and Applied Computer Science Jagellonian University Reymonta 4 30-059 Krakow Poland 

出 版 物：《Physical Review E》 (物理学评论E辑：统计、非线性和软体物理学)

年 卷 期：2008年第77卷第3期

页      面：036124-036124页

核心收录：

学科分类：07[理学] 070203[理学-原子与分子物理] 0702[理学-物理学] 

主　　题：BRANCHED POLYMERS COMPLEX NETWORKS DEGREE SEQUENCE SIZE 

摘      要：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.