Rank-based attachment leads to power law graphs

DOI10.1137/080716967zbMATH Open1213.05237arXiv0908.3436OpenAlexW2052630574MaRDI QIDQ5392902FDOQ5392902

Authors: Paweł Prałat, Jeannette Janssen 

Publication date: 15 April 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We investigate the degree distribution resulting from graph generation models based on rank-based attachment. In rank-based attachment, all vertices are ranked according to a ranking scheme. The link probability of a given vertex is proportional to its rank raised to the power -a, for some a in (0,1). Through a rigorous analysis, we show that rank-based attachment models lead to graphs with a power law degree distribution with exponent 1+1/a whenever vertices are ranked according to their degree, their age, or a randomly chosen fitness value. We also investigate the case where the ranking is based on the initial rank of each vertex; the rank of existing vertices only changes to accommodate the new vertex. Here, we obtain a sharp threshold for power law behaviour. Only if initial ranks are biased towards lower ranks, or chosen uniformly at random, we obtain a power law degree distribution with exponent 1+1/a. This indicates that the power law degree distribution often observed in nature can be explained by a rank-based attachment scheme, based on a ranking scheme that can be derived from a number of different factors; the exponent of the power law can be seen as a measure of the strength of the attachment.

Full work available at URL: https://arxiv.org/abs/0908.3436

Recommendations

• Protean graphs with a variety of ranking schemes
• scientific article; zbMATH DE number 5732563
• Popularity based random graph models leading to a scale-free degree sequence
• Protean Graphs with a Variety of Ranking Schemes
• A preferential attachment model with random initial degrees

zbMATH Keywords

random graphsdegree distributionscale-free networksweb graphspower law graphsprotean graphsdifferential equations method

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07)

Cited In (7)

• Protean Graphs with a Variety of Ranking Schemes
• Connectivity threshold and recovery time in rank-based models for complex networks
• The diameter of protean graphs
• Protean graphs with a variety of ranking schemes
• Degree evolution in a general growing network
• Putting down roots: a graphical exploration of community attachment
• Large deviations for the degree structure in preferential attachment schemes

This page was built for publication: Rank-based attachment leads to power law graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5392902)