Protean graphs with a variety of ranking schemes

Abstract. We introduce a new class of random graph models for complex real-world networks, based on the protean graph model by ÃLuczak and PraÃlat. Our generalized protean graph models have two distinguishing features. First, they are not growth models, but instead are based on the assumption that a “steady state ” of large but finite size has been reached. Second, the models assume that the vertices are ranked according to a given ranking scheme, and the rank of a vertex determines the probability that that vertex receives a link in a given time step. Precisely, the link probability is proportional to the rank raised to the power −α, where the attachment strength α is a tunable parameter. We show that the model leads to a power law degree distribution with exponent 1 + 1/α for ranking schemes based on a given prestige label, or on the degree of a vertex. We also study a scheme where each vertex receives an initial rank chosen randomly according to a biased distribution. In this case, the degree distribution depends on the distribution of the initial rank. For one particular choice of parameters we obtain a power law with an exponent that depends both on α and on a parameter determining the initial rank distribution. 1