Name
Abstract | ||
|---|---|---|
We study a scale-free random graph process in which the number of edges added at each step increases. This differs from the standard model in which a fixed number, m, of edges are added at each step. Let f(t) be the number of edges added at step t. In the standard scale-free model, f(t) = m constant, whereas in this paper we consider f(t) = [tc],c 0. Such a graph process, in which the number of edges grows non-linearly with the number of vertices is said to have accelerating growth. We analyze both an undirected and a directed process. The power law of the degree sequence of these processes exhibits widely differing behavior. For the undirected process, the terminal vertex of each edge is chosen by preferential attachment based on vertex degree. When f(t) = m constant, this is the standard scale-free model, and the power law of the degree sequence is 3. When f(t) = [tc],c x = (3 − c)/(1 − c). As c → 0, x → 3, which gives a value of x = 3, as in standard scale-free model. Thus no more slowly growing monotone function f(t) alters the power law of this model away from x = 3. When c = 1, so that f(t) = t, the expected degree of all vertices is t, the vertex degree is concentrated, and the degree sequence does not have a power law. For the directed process, the terminal vertex is chosen proportional to in-degree plus an additive constant, to allow the selection of vertices of in-degree zero. For this process when f(t) = m is constant, the power law of the degree sequence is x = 2 + 1/m. When f(t) = [tc], c 0, the power law becomes x = 1 + 1/(1 + c), which naturally extends the power law to [1,2]. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 396–421, 2011 © 2011 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1002/rsa.20318 | Random Struct. Algorithms |
Keywords | Field | DocType |
degree sequence,wiley periodicals,terminal vertex,vertex degree,power law,scale-free graph,standard scale-free model,undirected process,scale-free random graph process,graph process,expected degree,scale free | Discrete mathematics,Combinatorics,Random graph,Vertex (geometry),Neighbourhood (graph theory),Cycle graph,Frequency partition of a graph,Degree (graph theory),Power law,Mathematics,Preferential attachment | Journal |
Volume | Issue | ISSN |
38 | 4 | 1042-9832 |
Citations | PageRank | References |
5 | 0.55 | 17 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 857 | 91.88 |
| Paweł Prałat | 2 | 162 | 16.57 |