Geometry of minimum spanning trees on scale-free networks

Gábor J. Szabó; Mikko Alava; János Kertész

doi:10.1016/j.physa.2003.08.031

Geometry of minimum spanning trees on scale-free networks

Gábor J. Szabó, Mikko Alava, János Kertész

Research output: Contribution to journal › Conference article › peer-review

Abstract (may include machine translation)

The minimum spanning trees on scale-free graphs are shown to be scale-free as well, in the presence of random edge weights. The probability distribution of the weights on the tree differs from regular lattices reflecting the typically short distances (small-world property). We consider also the trees in the absence of such randomness and the ensuing massive degeneracy, which is analyzed with graph theoretical arguments.

Original language	English
Pages (from-to)	31-36
Number of pages	6
Journal	Physica A: Statistical Mechanics and its Applications
Volume	330
Issue number	1-2
DOIs	https://doi.org/10.1016/j.physa.2003.08.031
State	Published - 1 Dec 2003
Externally published	Yes
Event	Randomes and Complexity - Eilat, Israel Duration: 5 Jan 2003 → 9 Jan 2003

Keywords

Global optimization
Minimum spanning trees
Random networks

Access to Document

10.1016/j.physa.2003.08.031

Cite this

@article{7f96d34016f94500a58f8c6c6efc6dd9,

title = "Geometry of minimum spanning trees on scale-free networks",

abstract = "The minimum spanning trees on scale-free graphs are shown to be scale-free as well, in the presence of random edge weights. The probability distribution of the weights on the tree differs from regular lattices reflecting the typically short distances (small-world property). We consider also the trees in the absence of such randomness and the ensuing massive degeneracy, which is analyzed with graph theoretical arguments.",

keywords = "Global optimization, Minimum spanning trees, Random networks",

author = "Szab{\'o}, {G{\'a}bor J.} and Mikko Alava and J{\'a}nos Kert{\'e}sz",

year = "2003",

month = dec,

day = "1",

doi = "10.1016/j.physa.2003.08.031",

language = "English",

volume = "330",

pages = "31--36",

journal = "Physica A: Statistical Mechanics and its Applications",

issn = "0378-4371",

number = "1-2",

note = "Randomes and Complexity ; Conference date: 05-01-2003 Through 09-01-2003",

}

TY - JOUR

T1 - Geometry of minimum spanning trees on scale-free networks

AU - Szabó, Gábor J.

AU - Alava, Mikko

AU - Kertész, János

PY - 2003/12/1

Y1 - 2003/12/1

N2 - The minimum spanning trees on scale-free graphs are shown to be scale-free as well, in the presence of random edge weights. The probability distribution of the weights on the tree differs from regular lattices reflecting the typically short distances (small-world property). We consider also the trees in the absence of such randomness and the ensuing massive degeneracy, which is analyzed with graph theoretical arguments.

AB - The minimum spanning trees on scale-free graphs are shown to be scale-free as well, in the presence of random edge weights. The probability distribution of the weights on the tree differs from regular lattices reflecting the typically short distances (small-world property). We consider also the trees in the absence of such randomness and the ensuing massive degeneracy, which is analyzed with graph theoretical arguments.

KW - Global optimization

KW - Minimum spanning trees

KW - Random networks

UR - http://www.scopus.com/inward/record.url?scp=0344550311&partnerID=8YFLogxK

U2 - 10.1016/j.physa.2003.08.031

DO - 10.1016/j.physa.2003.08.031

M3 - Conference article

AN - SCOPUS:0344550311

SN - 0378-4371

VL - 330

SP - 31

EP - 36

JO - Physica A: Statistical Mechanics and its Applications

JF - Physica A: Statistical Mechanics and its Applications

IS - 1-2

T2 - Randomes and Complexity

Y2 - 5 January 2003 through 9 January 2003

ER -

Geometry of minimum spanning trees on scale-free networks

Abstract (may include machine translation)

Keywords

Access to Document

Other files and links

Fingerprint

Cite this