Random walk attachment graphs

被引：7

作者：

Cannings, Chris ^{[1
]}

Jordan, Jonathan ^{[1
]}

机构：

[1] Univ Sheffield, Sheffield S10 2TN, S Yorkshire, England

来源：

ELECTRONIC COMMUNICATIONS IN PROBABILITY | 2013年 / 18卷

关键词：

random graphs; preferential attachment; random walk; RANDOM NETWORKS;

D O I：

10.1214/ECP.v18-2518

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We consider the random walk attachment graph introduced by Saramaki and Kaski and proposed as a mechanism to explain how behaviour similar to preferential attachment may appear requiring only local knowledge. We show that if the length of the random walk is fixed then the resulting graphs can have properties significantly different from those of preferential attachment graphs, and in particular that in the case where the random walks are of length 1 and each new vertex attaches to a single existing vertex the proportion of vertices which have degree 1 tends to 1, in contrast to preferential attachment models.

引用

页码：1 / 5

页数：5

共 11 条

[1]

[Anonymous], 2011, JAHRESBER DTSCH MATH, DOI [DOI 10.1365/S13291-010-0011-6, DOI 10.1365/S13291-010-0011-6)]

[2] Mean-field theory for scale-free random networks [J].

Barabási, AL ;

Albert, R ;

Jeong, H .

PHYSICA A, 1999, 272 (1-2) :173-187

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

Barabási, AL ;

Albert, R .

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

[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] Random networks with sublinear preferential attachment: Degree evolutions [J].

Dereich, Steffen ;

Moerters, Peter .

ELECTRONIC JOURNAL OF PROBABILITY, 2009, 14 :1222-1267

[6] Scale-free networks from self-organization -: art. no. 026138 [J].

Evans, TS ;

Saramäki, JP .

PHYSICAL REVIEW E, 2005, 72 (02)

[7] FRIEDMAN,BERNARD URN [J].

FREEDMAN, DA .

ANNALS OF MATHEMATICAL STATISTICS, 1965, 36 (03) :956-970

[8] A survey of random processes with reinforcement [J].

Pemantle, Robin .

PROBABILITY SURVEYS, 2007, 4 :1-79

[9] Scale-free networks generated by random walkers [J].

Saramäki, J ;

Kaski, K .

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2004, 341 (1-4) :80-86

[10]

SIMON HA, 1955, BIOMETRIKA, V42, P425

← 1 2 →