Scale-Free Property for Degrees and Weights in an N-Interactions Random Graph Model*

Abstract

A general random graph evolution mechanism is defined. The evolution is based on the interactions of N vertices. Besides the interactions of the new vertex and the old ones, interactions among old vertices are also allowed. Moreover, both preferential attachment and uniform choice are possible. A vertex in the graph is characterized by its degree and its weight. The weight of a given vertex is the number of interactions of the vertex. The asymptotic behavior of the graph is studied. Scale-free properties both for the degrees and the weights are proved. It turns out that any exponent in (2,∞) can be achieved. The proofs are based on discrete time martingale theory.