Zoran Nikoloski ; Narsingh Deo ; Ludek Kucera - Degree-correlation of Scale-free graphs

dmtcs:3406 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3406
Degree-correlation of Scale-free graphsArticle

Authors: Zoran Nikoloski 1; Narsingh Deo 1; Ludek Kucera 2

  • 1 School of Electrical Engineering and Computer Science [Orlando]
  • 2 Department of Applied Mathematics (KAM)

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 \textitdegree 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'≤n^1 / 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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: degree-correlation,scale-free degree distribution,linearized chord diagrams,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

4 Documents citing this article

Consultation statistics

This page has been seen 196 times.
This article's PDF has been downloaded 203 times.