A Probabilistic Analysis of the Modified Barabasi-Albert Model for Scale-free Networks

概要

論文の詳細を見る
Many real networks have power-law vertex degree distribution such that the probability P(d) of vertex degree d is proportional to d^<-γ> for a constant real number γ. This property is called 'scale-free (SF)'. SF networks do not emerge in the traditional random graph model studied by Erdos and Renyi, and the famous 'BA model' proposed by Barabasi and Albert is the first random graph model which generates SF networks. The two characteristics of the model is the growth property and the preferential attachment property. In this article, we study random graph model which does not have the growth property but only have the preferential attachment property. We formulate the model as a (Z_+)^n-valued Markov chain of the numbers of balls in n bins, at each step an additional ball is placed in one of the bins, such that the probability the ball is placed in the bin is proportional to the number of balls in the bin. This is a generalization of the famous Polya's Urn model. We present an asymptotic formula, as n tends to infinity, of the probability law of the empirical distribution of the balls in n bins, corresponding to the degree distribution P(d).
関西学院大学の論文