Exact Degree Distributions of a Simple Preferential Attachment Model
Tung-Lung Wu*
Department of Mathematics and Statistics, Mississippi State University, USA
Submission: June 07, 2018; Published: November 16, 2018
*Corresponding author: Tung-Lung Wu, Department of Mathematics and Statistics, Mississippi State University, USA.
How to cite this article: Tung-Lung W. Exact Degree Distributions of a Simple Preferential Attachment Model. Biostat Biometrics Open Acc J. 2018; 8(4): 555744. DOI: 10.19080/BBOAJ.2018.08.555744
Abstract
We study the exact degree distribution for a simple preferential attachment model. Suppose that there is only one initial node and each new node is allowed to connect to one existing node, the exact degree distributions are obtained using the finite Markov chain imbedding technique. Numerical results are given to demonstrate our result.
Keywords: Preferential attachment models; Degree distributions; Finite Markov chain imbedding
Introduction
Preferential attachment models have been successfully used to model human networks. Examples of this line of research include some empirical studies such as biological network and human behavior network. Many graph models including preferential attachment models are shown to have power laws. Approximations and bounds have also been developed for degree distributions [1-5]. In this paper, we will show how to compute the exact degree distribution for a simple preferential attachment model based on the finite Markov chain imbedding (FMCI) technique [3].
We consider the simple model where there is only l=1 initial node (label 0) and each new node (child) is only allowed to connect to m=1 existing node (parent) in the network. The k-th node joining the network is given a label .k For each node, the in-degree is the number of children and the outdegree is always 1 for new coming node. The only exception is the initial node whose out-degree is 0. The degree of a node is defined to be the sum of indegree and out-degree. The probability of a new node connecting to any node is proportional to its degree.
Let Dk(n) be the degree of label k at time .n It is not difficult to see that Dk(n) forms a discrete Markov chain. We can define a Markov chain with initial probability As the model grows over time with new nodes, the probability of a new node connecting to label i is also changing over time. Thus, is a non-homogeneous Markov chain. For a node labeled 1,k≥ the maximal degree at time t is t-k+1 At time t=1,
Also, . The transition probabilities of the imbedded Markov chain {Yt} are given as follows: at time ,t≥k
The transition matrices of are of the following form for ,t≥k
Hence, the degree distribution of label k is given by
Where with one corresponding to state .i The exact degree distributions of labels k=1,10.50.100 for n= 200,500,1000,2000 are given in Figure 1.
Conclusion
Preferential attachment models have recently gained popularity in modeling human networks. In this short paper, we illustrate how to obtain the exact degree distributions based on the FMCI technique for a simple model and hope that this will attract more interest in this line of work.
References
- Chung F, Lu L (2006) Complex graphs and networks. CBMS Regional Conference Series in Mathematics, Published for the Conference Board of the Mathematical Sciences, Washington. American Mathematical Society, Volume 107.
- Eisenberg E, Levanon EY (2003) Preferential attachment in the protein network evolution. Phys Rev Lett 91: 138.
- Fu JC, Lou WYW (2003) Distribution theory of runs and patterns and its applications. World Scientific Publishing Co., Inc., River Edge, UK.
- Jones JH, Handcock MS (2003) An assessment of preferential attachment as a mechanism for human sexual network formation. Proceedings of the Royal Society of London B: Biological Sciences 270(1520): 1123-1128.
- Pekoz EA, Rollin A, Ross N (2013) Degree asymptotics with rates for preferential attachment random graphs. Ann Appl Probab 23(3): 1188-1218.