Name
Abstract | ||
|---|---|---|
We introduce a new class of random graph models for complex real-world networks, based on the protean graph model by Łuczak and Prałat. 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.tcs.2009.05.009 | Theoretical Computer Science |
Keywords | Field | DocType |
Random graphs,Web graphs,Protean graphs,Degree distribution,Differential equations method,Power law graphs,Scale-free networks | Random regular graph,Strength of a graph,Discrete mathematics,Modular decomposition,Combinatorics,Random graph,Line graph,Computer science,Theoretical computer science,Graph product,Pathwidth,Universal graph | Journal |
Volume | Issue | ISSN |
410 | 52 | 0304-3975 |
Citations | PageRank | References |
5 | 0.54 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeannette Janssen | 1 | 295 | 32.23 |
| Paweł Prałat | 2 | 162 | 16.57 |