Levels of a scale-free tree

被引：7

作者：

Katona, Zsolt ^{[1
]}

机构：

[1] Eotvos Lorand Univ, Dept Probabil Theory & Stat, H-1117 Budapest, Hungary

来源：

RANDOM STRUCTURES & ALGORITHMS | 2006年 / 29卷 / 02期

关键词：

random graphs; scale-free disribution; width of trees;

D O I：

10.1002/rsa.20106

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Consider the random graph model of Barabdsi and Albert, where we add a new vertex in every step and connect it to some old vertices with probabilities proportional to their degrees. If we connect it to only one of the old vertices the graph will be a tree. These graphs have been shown to have power law degree distributions, the same as observed in some large real-world networks. We show that the degree distribution is the same on every sufficiently high level of the tree. (c) 2005 Wiley Periodicals, Inc.

引用

页码：194 / 207

页数：14

共 12 条

[1]

[Anonymous], 1987, N HOLLAND MATH STUDI

[2] Emergence of scaling in random networks [J].

Barabási, AL ;

Albert, R .

SCIENCE, 1999, 286 (5439) :509-512

[3]

BENCZUR A, P WWW 2003

[4] The degree sequence of a scale-free random graph process [J].

Bollobás, B ;

Riordan, O ;

Spencer, J ;

Tusnády, G .

RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (03) :279-290

[5]

BOLLOBAS B, 2003, COMBINATORICA

[6]

Chauvin B, 2001, ANN APPL PROBAB, V11, P1042

[7] Width of a scale-free tree [J].

Katona, Z .

JOURNAL OF APPLIED PROBABILITY, 2005, 42 (03) :839-850

[8]

LU J, 1998, YOKOHAMA MATH J, V45, P61

[9] ON THE STRUCTURE OF RANDOM PLANE-ORIENTED RECURSIVE TREES AND THEIR BRANCHES [J].

MAHMOUD, HM ;

SMYTHE, RT ;

SZYMANSKI, J .

RANDOM STRUCTURES & ALGORITHMS, 1993, 4 (02) :151-176

[10]

MAHMOUD HM, 1996, THEORY PROBAB MATH S, V51, P1

← 1 2 →