Name
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 $-\alpha$, for some $\alpha\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/\alpha$ 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 changes only to accommodate the new vertex. Here, we obtain a sharp threshold for power law behavior. Only if initial ranks are biased towards lower ranks, or chosen uniformly at random, do we obtain a power law degree distribution with exponent $1+1/\alpha$. 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1137/080716967 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
rank-based attachment,power law,degree distribution,initial rank,rank-based attachment scheme,protean graphs,. random graphs,lower rank,web graphs,power law behavior,power law graphs,dierential,power law degree distribution,ranking scheme,rank-based attachment model,scale free networks,random graph,random graphs | Discrete mathematics,Combinatorics,Random graph,Vertex (geometry),Exponent,Ranking,Scale-free network,Probability distribution,Degree distribution,Power law,Mathematics | Journal |
Volume | Issue | ISSN |
24 | 2 | SIAM Journal of Discrete Math 24, 2010, pp. 420--440 |
Citations | PageRank | References |
3 | 0.48 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeannette Janssen | 1 | 295 | 32.23 |
| Paweł Prałat | 2 | 162 | 16.57 |