Degree-correlation of Scale-free graphs

Abstract : 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.
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.239-244, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184363
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 11:37:31
Dernière modification le : jeudi 11 mai 2017 - 01:02:53
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:00:56

Fichier

dmAE0148.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184363, version 1

Collections

Citation

Zoran Nikoloski, Narsingh Deo, Ludek Kucera. Degree-correlation of Scale-free graphs. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.239-244, 2005, DMTCS Proceedings. 〈hal-01184363〉

Partager

Métriques

Consultations de la notice

276

Téléchargements de fichiers

144