DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Degree-correlation of Scale-free graphs

Zoran Nikoloski, Narsingh Deo, Ludek Kucera


Barabási and Albert [1] suggested modeling scale-free networks by the following random graph process: one node is added at a time and is connected to an earlier node chosen with probability proportional to its degree. A recent empirical study of Newman [5] demonstrates existence of degree-correlation between degrees of adjacent nodes in real-world networks. Here we define the degree correlation---correlation of the degrees in a pair of adjacent nodes---for a random graph process. We determine asymptotically the joint probability distribution for node-degrees, d and d', of adjacent nodes for every 0≤d≤ d'≤n1 / 5, and use this result to show that the model of Barabási and Albert does not generate degree-correlation. Our theorem confirms the result in [KR01], obtained by using the mean-field heuristic approach.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional