%0 Journal Article
%T Scale-Free Property for Degrees and Weights in a Preferential Attachment Random Graph Model
%A Istv¨˘n Fazekas
%A Bettina Porv¨˘zsnyik
%J Journal of Probability and Statistics
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/707960
%X A random graph evolution mechanism is defined. The evolution studied is a combination of the preferential attachment model and the interaction of four vertices. The asymptotic behaviour of the graph is described. It is proved that the graph exhibits a power law degree distribution; in other words, it is scale-free. It turns out that any exponent in can be achieved. The proofs are based on martingale methods. 1. Introduction During the last years the behaviour of many types of real-world networks was investigated. Such networks are the WWW, the Internet, and social and biological networks (see [1] for an overview). The main common characteristic of such networks is their scale-free nature, in other words the power law degree distribution, that is, , as . Using real-life data, the exponents were determined for several cases. For the WWW the in-degree and the out-degree of web pages follow power law with and , for the Internet , for the movie actor network , and for the collaboration graph of mathematicians (see [1] for details). To describe the phenomenon, in [2] the preferential attachment model was introduced. In that model the growing procedure of the random graph is the following. At every time a new vertex with edges is added so that the edges link the new vertex to existing vertices. The probability that the new vertex will be connected to the old vertex depends on the degree of vertex , so that . Then several papers were devoted to the proof of the power law in the preferential attachment model (see, e.g., [3]). There are versions of the preferential attachment model (see [4, 5]). It turned out that besides the degrees of the vertices other characteristics of the graph can be important (see [5]). In [6] a model based on the interaction of three vertices was introduced. Then the power law degree distribution in that model was obtained in [7]. In this paper, we extend the model and the results of [6, 7] to interactions of four vertices. Our model is the following. For short, a complete graph with four vertices we will call tetragon. The starting point at time is one tetragon. The initial weight of this graph is one. This graph contains vertices, edges, and triangles. Each of these objects has initial weight . After the initial step we start to increase the size of the graph. The main feature of the procedure is that at each step we consider four vertices and draw all nonexisting edges between these vertices. So we obtain a tetragon. The weight of this tetragon and the weights of all the objects in the tetragon are increased by . (That is, we increase
%U http://www.hindawi.com/journals/jps/2013/707960/