Bezškálová síť
Kategorie: Nezařazeno (celkem: 23181 referátů a seminárek)
Informace o referátu:
- Přidal/a: anonymous
- Datum přidání: 12. srpna 2008
- Zobrazeno: 2075×
- Licence: GNU Free Documentation License
- Seznam autorů a změn
- Vyloučení odpovědnosti
Příbuzná témata
Bezškálová síť
Bezškálová síť je souvislý graf, jehož vrcholy mají Yuleovu-Simonovu distribuci stupňů vrcholů
kde P(k) je pravděpodobnost, že vrchol uzlu sousedí s k jinými vrcholy a ? je reálný koeficient distribuce, větší než 1.[1]
Obsah |
Vlastnosti bezškálových sítí
Předepsaná distribuce stupňů vrcholů velmi ovlivňuje celkovou topologii grafu. Nejzajímavější vlastností bezškálových sítí je relativní běžnost vrcholů, jejichž stupeň vysoce převyšuje průměr. Vrcholy s nejvyššími stupni se často nazývají „huby“ ([h?b] IPA). Tyto huby jsou obklopeny vrcholy s nižšími stupni a ty vrcholy s ještě nižšími atd…
Topologie bezškálových sítí je velmi odolná vůči náhodnému (při rovnoměrném rozdělení pravděpodobnosti) odstranění některých vrcholů. Pravděpodobnost, že hub bude odstraněn je téměř zanedbatelná, protože hubů je málo. Pokud přesto je některý odstraněn, s velkou pravděpodobností graf zůstane souvislý. Na druhou stranu, pokud cíleně odstraníme několik hlavních hubů, graf se rozpadne na několik izolovaných grafů. Huby jsou tedy jak silnou stránkou, tak Achillovou patou bezškálových sítí.
Další důležitou vlastností bezškálových sítí je vytváření shluků, klastrů. Vrcholy s nízkými stupni bývají připojeny k velmi hustým podgrafům a ty bývají s jinými takovými podgrafy spojeny přes huby s ještě vyšším stupněm.
Významnou vlastností bezškálových sítí s 2 < ? < 3 je jejich velmi malý průměr grafu d, který s počtem vrcholů n roste jen jako d~lnlnn. Díky tomu se dá průměr rostoucích bezškálových sítí považovat za téměř neměnný.[2]
Bezškálové sítě v reálném světě
Bezškálová síť odpovídá mnoha sítím v reálném světě, v biologii, epidemiologii, sociologii nebo informatice.[1] Jejich koeficient ? se většinou pohybuje mezi 2 a 3, ale může být i menší než 2.[3]
Příklady bezškálových sítí
- sociální sítě, včetně sítí spolupracovníků
- sítě interakcí proteinů
- sítě sexuálních partnerů lidí[4]
- počítačové sítě, včetně World Wide Webu
Odkazy
- ? a b SMALL, Michael. MathWorld — A Wolfram Web Resource: Scale-Free Network [online]. Eric W. Weisstein, 2004-10-15, [cit. 2008-01-08]. Dostupné online. (anglicky)
- ? COHEN, Reuven; HAVLIN, Shlomo. Scale-Free Networks are Ultrasmall. Phys. Rev. Lett. 90, 02 2003, roč. 05, čís. 90, s. 058701. Dostupné online.
- ? SEYED-ALLAEI, Hamed; BIANCONI, Ginestra; MARSILI, Matteo. Scale-free networks with an exponent less than two. Physical Review E, 2006, čís. 73, s. 046113. Dostupné online. DOI:10.1103/PhysRevE.73.046113.
- ? LILJEROS, Fredrik; EDLING, Christofer R.; AMARAL, Luís A. Nunes, et al. The web of human sexual contacts. Nature, 2001, čís. 411, s. 907-908. Dostupné online. DOI:10.1038/35082140.
Tento článek je zčásti nebo zcela založen na překladu článku Scale-free network na anglické Wikipedii.