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 graphs
Authors: Zoran Nikoloski 1; Narsingh Deo 1; Ludek Kucera 2
NULL##NULL##NULL
Zoran Nikoloski;Narsingh Deo;Ludek Kucera
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.
Akama, Hiroyuki, 0000-0003-1777-497; Miyake, Maki; Jung, Jaeyoung; Murphy, Brian, 2015, Using Graph Components Derived From An Associative Concept Dictionary To Predict fMRI Neural Activation Patterns That Represent The Meaning Of Nouns, Plos One, 10, 4, pp. e0125725, 10.1371/journal.pone.0125725.
Gustedt, Jens, 2009, Generalized Attachment Models For The Genesis Of Graphs With High Clustering Coefficient, Complex Networks, pp. 99-113, 10.1007/978-3-642-01206-8_9.
Lee, Duan-Shin; Chang, Cheng-Shang; Zhu, Miao; Li, Hung-Chih, 2019, A Generalized Configuration Model With Degree Correlations And Its Percolation Analysis, Applied Network Science, 4, 1, 10.1007/s41109-019-0240-2.
Lee, Duan-Shin; Chang, Cheng-Shang; Li, Hung-Chih, 2019, A Generalized Configuration Model With Degree Correlations, Complex Networks X, pp. 49-61, 10.1007/978-3-030-14459-3_4.