Bezškálová síť - Scale-free network

Síťová věda
Teorie
Graf Komplexní síť Nákaza Malý svět Bez vodního kamene Struktura Společenství Perkolace Vývoj Ovladatelnost Kreslení grafu Sociální kapital Analýza odkazů Optimalizace Vzájemnost Uzavření Homofilie Přechodnost Preferenční příloha Teorie rovnováhy Síťový efekt Sociální vliv
Typy sítí
Informační (výpočetní) Telekomunikace Doprava Sociální Vědecká spolupráce Biologický Umělý neurální Vzájemně závislé Sémantický Prostorový Závislost Tok na čipu
Grafy
Funkce Klika Součástka Střih Cyklus Datová struktura Okraj Smyčka Sousedství Cesta Vrchol Seznam sousedů  / matice Seznam případů  / matice Typy Bipartitní Kompletní Režie Hyper Multi Náhodný Vážený
Metriky Algoritmy
Centrálnost Stupeň Mezi Blízkost PageRank Motiv Shlukování Rozdělení stupňů Assortativity Vzdálenost Modularita Účinnost
Modely
Topologie Náhodný graf Erdős – Rényi Barabási – Albert Fitness model Watts – Strogatz Exponenciální náhodné (ERGM) Náhodné geometrické (RGG) Hyperbolický (HGN) Hierarchický Stochastický blok Maximální entropie Měkká konfigurace Referenční hodnota LFR Dynamika Booleovská síť agent Epidemický /VÁŽENÝ PANE
Seznamy Kategorie
Témata Software Síťoví vědci Kategorie: Teorie sítí Kategorie: Teorie grafů

A bezškálová síť je síť jehož rozdělení stupňů následuje a mocenský zákon, alespoň asymptoticky. To je zlomek P(k) uzlů v síti s k připojení k jiným uzlům platí pro velké hodnoty k tak jako

${ displaystyle P (k) sim k ^ { boldsymbol {- gamma}}}$

kde ${ displaystyle gamma}$ je parametr, jehož hodnota je typicky v rozsahu 2 < ${ displaystyle gamma}$ <3 (přičemž druhý moment (parametr měřítka ) ${ displaystyle k ^ { boldsymbol {- gamma}}}$ je nekonečný, ale první okamžik je konečný), i když občas může ležet mimo tyto hranice.^[1][2]

Uvádí se, že mnoho sítí je bez měřítka, ačkoli statistická analýza mnoho z těchto tvrzení vyvrátila a vážně zpochybnila ostatní.^[3][4] Preferenční příloha a fitness model byly navrženy jako mechanismy k vysvětlení domnělých distribucí stupňů výkonu podle zákona v reálných sítích.

Dějiny

Ve studiích sítí citací mezi vědeckými pracemi Derek de Solla Price v roce 1965 ukázal, že počet odkazů na články - tj. počet citací, které dostanou - měl a těžký-sledoval distribuci následující a Paretova distribuce nebo mocenský zákon, a tedy, že citační síť je bez měřítka. Nepoužíval však pojem „bezškálová síť“, který byl vytvořen až o několik desetiletí později. V pozdějším článku v roce 1976 Price také navrhl mechanismus vysvětlující výskyt mocenských zákonů v citačních sítích, který nazval „kumulativní výhodou“, ale který je dnes běžněji známý pod názvem preferenční přílohu.

Nedávný zájem o bezškálové sítě začal v roce 1999 prací od Albert-László Barabási a kolegové v University of Notre Dame kdo zmapoval topologii části webu,^[5] zjištění, že některé uzly, které nazývají „rozbočovače“, mají mnohem více spojení než jiné a že síť jako celek má mocninové rozdělení počtu odkazů připojujících se k uzlu. Poté, co Barabási a spolupracovníci zjistili, že několik dalších sítí, včetně některých sociálních a biologických sítí, také mělo distribuci titulů se silným ocasem, vytvořilo termín „síť bez měřítka“ k popisu třídy sítí, které vykazují distribuci titulů podle zákona. Při studiu sedmi příkladů sítí v sociálních, ekonomických, technologických, biologických a fyzických systémech však Amaral et al. nebyli mezi těmito sedmi příklady schopni najít síť bez měřítka. Pouze jeden z těchto příkladů, síť filmových herců, měl distribuci titulů P(k) podle mocenského režimu pro mírné k, ačkoli nakonec po tomto režimu mocenského zákona následoval ostrý cut-off ukazující exponenciální úpadek pro velké k.^[6]

Barabási a Réka Albert navrhli generativní mechanismus k vysvětlení vzhledu distribuce mocenského práva, kterému říkali „preferenční přílohu „a která je v zásadě stejná jako ta, kterou navrhla Price. Analytická řešení tohoto mechanismu (rovněž podobná řešení Price) představila v roce 2000 Dorogovtsev, Mendes a Samukhin ^[7] a nezávisle Krapivsky, Redner, a Leyvraz, a později důsledně prokázáno matematikem Béla Bollobás.^[8] Pozoruhodně však tento mechanismus vytváří pouze specifickou podmnožinu sítí ve třídě bez měřítka a od té doby bylo objeveno mnoho alternativních mechanismů.^[9]

Historie bezškálových sítí zahrnuje také určité neshody. Na empirické úrovni byla zpochybněna škálovatelnost několika sítí. Například tři bratři Faloutsos věřili, že Internet měl rozložení stupně mocenského práva na základě traceroute data; nicméně, to bylo navrhl, že toto je a vrstva 3 iluze vytvořená směrovači, které vypadají jako uzly vysokého stupně, zatímco skrývají vnitřní vrstva 2 struktura ASes vzájemně se propojují.^[10]

V teoretické rovině byla navržena upřesnění abstraktní definice škálovatelnosti. Například Li et al. (2005) nedávno nabídli potenciálně přesnější „měřítko bez měřítka“. Krátce, pojďme G být graf s množinou hran Ea označují stupeň vrcholu ${ displaystyle v}$ (tj. počet hran dopadajících na ${ displaystyle v}$) od ${ displaystyle deg (v)}$. Definovat

${ displaystyle s (G) = součet _ {(u, v) v E} deg (u) cdot deg (v).}$

To se maximalizuje, když jsou uzly vysokého stupně připojeny k jiným uzlům vysokého stupně. Nyní definujte

${ displaystyle S (G) = { frac {s (G)} {s _ { max}}},}$

kde s_max je maximální hodnota s(H) pro H v sadě všech grafů se stejným rozložením stupňů jako uG. To dává metriku mezi 0 a 1, kde je graf G s malými S(G) je „scale-rich“ a graf G s S(G) blízko 1 je „bez měřítka“. Tato definice vystihuje pojem sebepodobnost vyplývá z názvu „scale-free“.

Přehled

Existují dvě hlavní složky, které vysvětlují vznik bezrozměrné vlastnosti v komplexních sítích: růst a preferenční připojení.^[11] „Růstem“ se nazývá proces růstu, kdy se po delší dobu nové uzly připojí k již existujícímu systému, síti (jako je World Wide Web, který se za 10 let rozrostl o miliardy webových stránek). „preferenční příloha“ se nazývá nový nadcházející uzel, který upřednostňuje připojení k jinému uzlu, který již má určitý počet odkazů s ostatními. Existuje tedy vyšší pravděpodobnost, že se více a více uzlů propojí s tím, který má již mnoho odkazů, což povede tento uzel k rozbočovači ve zkratce.^[5]V závislosti na síti mohou být rozbočovače buď rozdělovací, nebo rozřazovací. Assortativity by se našlo na sociálních sítích, ve kterých by dobře spojení / slavní lidé měli tendenci se navzájem lépe poznat. Dezassortativitu lze nalézt v technologických (internet, celosvětová síť) a biologických (interakce bílkovin, metabolismus) sítích.^[11]

Vlastnosti

Náhodná síť (a) a síť bez měřítka (b). V síti bez měřítka jsou zvýrazněny větší rozbočovače.

Komplexní distribuce síťových stupňů náhodně a bez měřítka

Nejpozoruhodnější charakteristikou v síti bez měřítka je relativní běžnost vrcholů s mírou, která výrazně převyšuje průměr. Uzly nejvyššího stupně se často nazývají „rozbočovače“ a předpokládá se, že slouží konkrétním účelům v jejich sítích, i když to do značné míry závisí na doméně.

Perkolace

Vlastnost bez měřítka silně koreluje s robustností sítě až do selhání. Ukazuje se, že hlavní rozbočovače jsou těsně následovány menšími. Tyto menší rozbočovače zase následují další uzly s ještě menším stupněm atd. Tato hierarchie umožňuje a tolerantní k chybám chování. Pokud dojde k náhodnému selhání a naprostá většina uzlů je těch s malým stupněm, je pravděpodobnost, že by to ovlivnilo rozbočovač, téměř zanedbatelná. I když dojde k selhání rozbočovače, síť obecně neztratí svoji propojenost, kvůli zbývajícím nábojům. Na druhou stranu, pokud vybereme několik hlavních rozbočovačů a vyjmeme je ze sítě, síť se promění v soubor poměrně izolovaných grafů. Rozbočovače jsou tedy silnou i slabou stránkou sítí bez měřítka. Tyto vlastnosti byly studovány analyticky pomocí teorie perkolace Cohen et al^[12][13] a Callaway et al.^[14] Bylo prokázáno Cohenem a kol ^[15] že pro širokou škálu bezplatných sítí, pro ${ displaystyle 2 < gamma <3}$ kritický práh perkolace, ${ displaystyle p_ {c} = 0}$. To znamená, že náhodným odebráním libovolného zlomku uzlů ze sítě síť nezničíte. To je na rozdíl od grafu Erdős – Rényi, kde ${ displaystyle p_ {c} = 1 / { bar {k}}}$, kde ${ displaystyle { bar {k}}}$ je průměrný stupeň. Výše popsané poruchy jsou náhodné, jak se obvykle předpokládá v teorii perkolace. Při zobecňování perkolace však také na nenáhodné, ale cílené útoky, např. Na uzly nejvyššího stupně, výsledky, jako je ${ displaystyle p_ {c}}$, významně změnit.^[13][14]Nedávno byl vyvinut nový typ poruch v sítích, nazývaný lokalizované útoky.^[16] V tomto případě jeden náhodně vybere uzel a odstraní jeho sousedy a další nejbližší sousedy, dokud nebude odstraněn zlomek 1-p uzlů. Díky lokalizovaným útokům je škálovatelná bezplatnější síť zranitelnější ve srovnání s výkupnými a pc> 0. Kritičtí exponenti perkolace v sítích bez měřítka se liší od náhodných sítí Erdős – Rényi. ^ [16a] Sítě bez měřítka jsou tedy v jiné třídě univerzality než sítě Erdős – Rényi.^[17]

Shlukování

Další důležitou charakteristikou sítí bez měřítka je shlukovací koeficient distribuce, která klesá s rostoucím stupněm uzlu. Toto rozdělení se rovněž řídí mocenským zákonem. To znamená, že uzly nízkého stupně patří do velmi hustých dílčích grafů a tyto dílčí grafy jsou navzájem propojeny prostřednictvím rozbočovačů. Zvažte sociální síť, ve které jsou uzly lidé a odkazy jsou vztahy známosti mezi lidmi. Je snadné vidět, že lidé mají tendenci utvářet komunity, tj. Malé skupiny, ve kterých každý každého zná (o této komunitě lze uvažovat jako o kompletní graf ). Kromě toho mají členové komunity také několik známých vztahů k lidem mimo tuto komunitu. Někteří lidé jsou však spojeni s velkým počtem komunit (např. Celebrity, politici). Tito lidé mohou být považováni za centra odpovědná za fenomén malého světa.

V současné době se specifičtější charakteristiky sítí bez měřítka liší podle generativního mechanismu použitého k jejich vytvoření. Například sítě generované preferenčním připojením obvykle umisťují vrcholy vysokého stupně do středu sítě a spojují je dohromady, aby vytvořily jádro, s postupně uzly nižšího stupně tvořícími regiony mezi jádrem a periferií. Náhodné odstranění i velkého zlomku vrcholů má velmi malý dopad na celkovou propojenost sítě, což naznačuje, že takové topologie by mohly být užitečné pro bezpečnostní, zatímco cílené útoky velmi rychle ničí propojenost. Jiné sítě bez měřítka, které umisťují vrcholy vysokých stupňů na periferii, tyto vlastnosti nevykazují. Podobně se může klastrový koeficient bezškálových sítí významně lišit v závislosti na dalších topologických detailech.

Vzdálenost v měřítku bez sítí

Další charakteristika se týká průměrné vzdálenosti mezi dvěma vrcholy v síti. Stejně jako u většiny neuspořádaných sítí, jako je malá světová síť model, tato vzdálenost je velmi malá ve srovnání s vysoce uspořádanou sítí, jako je a mřížkový graf. Je pozoruhodné, že nekorelovaný graf výkonu a síly, který má 2 d ~ ln lnN kde N je počet uzlů v síti, jak dokazují Cohen a Havlin.^[18] Průměr rostoucí sítě bez měřítka by tedy mohl být v praxi považován za téměř konstantní.

Fraktální sítě zdarma

Rozenfeld a kol ^[19] navrhl metodu generování deterministických sítí ve fraktálním měřítku

Imunizace

Podrobně byla studována otázka, jak efektivně imunizovat volné sítě, které představují realistické sítě, jako je internet a sociální sítě. Jednou z takových strategií je imunizace uzlů nejvyššího stupně, tj. Cílené (úmyslné) útoky^[12][13] protože pro tento případ str${ displaystyle c}$ je relativně vysoká a k imunizaci je potřeba méně uzlů. V mnoha realistických případech však globální struktura není k dispozici a uzly nejvyššího stupně nejsou známy. Pro takové případy byla vyvinuta metoda známé imunizace.^[20] V tomto případě, který je docela efektivní, se vybírá náhodně uzly, ale imunizuje se jejich sousedy. Další a ještě efektivnější metoda je založena na metodě grafického rozdělení^[21]  .

Vlastnosti náhodného grafu se mohou při transformaci grafu změnit nebo zůstat neměnné. Mashaghi A. et al. například prokázali, že transformace, která převádí náhodné grafy na jejich okrajové duální grafy (nebo liniové grafy), vytváří soubor grafů s téměř stejným rozdělením stupňů, ale s korelacemi stupňů a výrazně vyšším koeficientem shlukování. Scale free graphs, as such, remain scale free under such transformations.^[22]

Příklady

Přestože se o mnoha sítích v reálném světě říká, že jsou bez měřítka, důkazy často zůstávají neprůkazné, a to především kvůli rostoucímu povědomí o přísnějších technikách analýzy dat.^[3] Vědecká komunita jako taková bezrozměrná povaha mnoha sítí stále diskutuje. Několik příkladů sítí prohlášených za bezškálové:

• Nějaký Sociální sítě, včetně sítí pro spolupráci. Dva příklady, které byly rozsáhle studovány, jsou spolupráce filmových herců ve filmech a spoluautorství matematiků z článků.
• Mnoho druhů počítačové sítě, včetně Internet a webgraf z Celosvětová Síť.
• Grafy závislosti na softwaru,^[23] některé z nich byly popsány pomocí generativního modelu.^[24]
• Některé finanční sítě, například mezibankovní platební sítě ^[25][26]
• Interakce protein-protein sítí.
• Sémantické sítě.^[27]
• Sítě leteckých společností.

Snímek vážené planární stochastické mřížky (WPSL).

Topologie bez šupin byla také nalezena ve vysokoteplotních supravodičích.^[28] Vlastnosti vysokoteplotního supravodiče - sloučeniny, ve které elektrony dodržují zákony kvantové fyziky a proudí v dokonalé synchronizaci bez tření - se zdají být spojeny s fraktálním uspořádáním zdánlivě náhodných atomů kyslíku a mřížkovým zkreslením.^[29]

Prostorová buněčná struktura, vážená planární stochastická mříž (WPSL) nedávno bylo navrženo, jehož rozdělení koordinačních čísel se řídí zákonem o moci. Znamená to, že mřížka má několik bloků, které mají neuvěřitelně velký počet sousedů, se kterými sdílejí společné hranice. Jeho konstrukce začíná iniciátorem, řekněme čtvercem jednotkové plochy, a generátorem, který jej náhodně rozdělí do čtyř bloků. Generátor je poté postupně aplikován znovu a znovu pouze na jeden z dostupných bloků, které byly přednostně vybrány s ohledem na jejich oblasti. Výsledkem je rozdělení čtverce na stále menší vzájemně se vylučující obdélníkové bloky. Duál WPSL (DWPSL) se získá nahrazením každého bloku uzlem v jeho středu a společná hranice mezi bloky s hranou spojující dva odpovídající vrcholy se jeví jako síť, jejíž rozdělení stupňů se řídí zákonem moci.^[30][31] Důvodem je to, že roste zprostředkování řízený model přílohy pravidlo, které také ztělesňuje preferenční pravidlo připoutání, ale v přestrojení.

Generativní modely

Bezškálové sítě nevznikají náhodou. Erdős a Rényi (1960) studovali model růstu grafů, ve kterém jsou v každém kroku náhodně vybrány dva uzly a je mezi ně vložen odkaz. Jejich vlastnosti náhodné grafy se liší od vlastností nalezených v sítích bez měřítka, a proto je pro tento růstový proces potřeba model.

Nejznámějším generativním modelem pro podmnožinu sítí bez měřítka je Barabási and Albert's (1999) bohatí zbohatnou generativní model, ve kterém každá nová webová stránka vytváří odkazy na existující webové stránky s pravděpodobným rozložením, které není jednotné, ale přiměřené aktuálnímu stupni webových stránek. Tento model původně vynalezl Derek J. de Solla Price v roce 1965 pod tímto termínem kumulativní výhoda, ale nedosáhla popularity, dokud Barabási znovu neobjevil výsledky pod svým současným názvem (BA Model ). Podle tohoto procesu bude stránka s mnoha odkazy obsahovat více odkazů než běžná stránka. Tím se vygeneruje zákon o moci, ale výsledný graf se liší od skutečného webového grafu v jiných vlastnostech, jako je přítomnost malých těsně propojených komunit. Byly navrženy a studovány obecnější modely a charakteristiky sítě. Například Pachon et al. (2018) navrhli variantu bohatí zbohatnou generativní model, který bere v úvahu dvě různá pravidla připojení: preferenční mechanismus připojení a jednotný výběr pouze pro nejnovější uzly.^[32] Recenze naleznete v knize Dorogovtsev a Mendes.

Poněkud odlišný generativní model pro webové odkazy navrhli Pennock a kol. (2002). Zkoumali komunity se zájmy v konkrétním tématu, jako jsou domovské stránky univerzit, veřejných společností, novin nebo vědců, a vyřadili hlavní uzly webu. V tomto případě již distribuce odkazů nebyla mocenským zákonem, ale připomínala a normální distribuce. Na základě těchto pozorování autoři navrhli generativní model, který kombinuje preferenční připoutání se základní pravděpodobností získání odkazu.

Dalším generativním modelem je kopírovat model studovaný Kumarem a kol.^[33] (2000), ve kterém nové uzly náhodně vybírají existující uzel a kopírují zlomek odkazů existujícího uzlu. Tím se také vytváří mocenský zákon.

The růst sítí (přidání nových uzlů) není nutnou podmínkou pro vytvoření bezškálové sítě. Dangalchev^[34] (2004) uvádí příklady generování statických sítí bez měřítka. Další možností (Caldarelli et al. 2002) je považovat strukturu za statickou a nakreslit vazbu mezi vrcholy podle konkrétní vlastnosti obou zúčastněných vrcholů. Jakmile zadáte statistickou distribuci pro tyto vlastnosti vrcholů (zdatnosti), ukáže se, že za určitých okolností také statické sítě vyvíjejí vlastnosti bez měřítka.

Zobecněný model bez měřítka

tento článek potřebuje pozornost odborníka na matematiku. Přidejte prosím důvod nebo a mluvit parametr k této šabloně pro vysvětlení problému s článkem. Matematika WikiProject může pomoci s náborem odborníka. (Červen 2009)

Došlo k výbuchu aktivity v modelování škálovatelné komplexní sítě. Recept Barabásiho a Alberta^[35] následovalo několik variací a zevšeobecnění^{[36][37][38][39][32]} a vylepšení předchozích matematických prací.^[40] Dokud existuje mocenský zákon distribuce v modelu, je to síť bez měřítka a model této sítě je model bez měřítka.

Funkce

Mnoho skutečných sítí je (přibližně) bez měřítka, a proto k jejich popisu vyžadují modely bez měřítka. V Priceově schématu jsou k vytvoření modelu bez měřítka potřeba dvě ingredience:

1. Přidání nebo odebrání uzly. Obvykle se soustředíme na rozšiřování sítě, tj. Na přidávání uzlů.

2. Preferenční příloha: Pravděpodobnost ${ displaystyle Pi}$ že nové uzly budou připojeny k „starému“ uzlu.

Upozorňujeme, že modely Fitness (viz níže) mohou fungovat také staticky, aniž by se změnil počet uzlů. Mělo by se také pamatovat na to, že skutečnost, že modely „preferenčního připoutání“ vedou k sítím bez měřítka, neprokazuje, že se jedná o mechanismus, který je základem vývoje sítí bez měřítka v reálném světě, protože na pracovat v systémech reálného světa, které nicméně vedou k škálování.

Příklady

Bylo několik pokusů o generování síťových vlastností bez měřítka. Zde jsou nějaké příklady:

Barabási – Albertův model

Například první model bez měřítka, Barabási – Albertův model, má lineární preferenční přílohu ${ displaystyle Pi (k_ {i}) = { frac {k_ {i}} { součet _ {j} k_ {j}}}}$ a v každém časovém kroku přidá jeden nový uzel.

(Poznámka, další obecná vlastnost ${ displaystyle Pi (k)}$ ve skutečných sítích je to ${ displaystyle Pi (0) neq 0}$, tj. existuje nenulová pravděpodobnost, že se nový uzel připojí k izolovanému uzlu. Tedy obecně ${ displaystyle Pi (k)}$ má formu ${ displaystyle Pi (k) = A + k ^ { alpha}}$, kde ${ displaystyle A}$ je počáteční přitažlivost uzlu.)

Dvouúrovňový síťový model

Dangalchev^[34] staví 2-L model přidáním a druhá objednávka preferenční přílohu. Atraktivita uzlu v modelu 2-L závisí nejen na počtu uzlů s ním spojených, ale také na počtu odkazů v každém z těchto uzlů.

${ displaystyle Pi (k_ {i}) = { frac {k_ {i} + C sum _ {(i, j)} k_ {j}} { sum _ {j} k_ {j} + C sum _ {j} k_ {j} ^ {2}}},}$

kde C je koeficient mezi 0 a 1.

Model přílohy zprostředkovaný zprostředkováním (MDA)

V model připojení zprostředkovaný pohonem (MDA), přichází nový uzel ${ displaystyle m}$ edge náhodně vybere existující připojený uzel a poté se spojí, ne s tímto, ale s ${ displaystyle m}$ jejích sousedů, také náhodně vybraných. Pravděpodobnost ${ displaystyle Pi (i)}$ že uzel ${ displaystyle i}$ existujícího vybraného uzlu je

${ displaystyle Pi (i) = { frac {k_ {i}} {N}} { frac { součet _ {j = 1} ^ {k_ {i}} { frac {1} {k_ { j}}}} {k_ {i}}}.}$

Faktor ${ displaystyle { frac { sum _ {j = 1} ^ {k_ {i}} { frac {1} {k_ {j}}}} {k_ {i}}}}$ je inverzní hodnota harmonického průměru (IHM) stupňů ${ displaystyle k_ {i}}$ sousedé uzlu ${ displaystyle i}$. Rozsáhlé numerické šetření naznačuje, že přibližně ${ displaystyle m> 14}$ střední hodnota IHM ve velkém ${ displaystyle N}$ limit se stává konstantou, což znamená ${ displaystyle Pi (i) propto k_ {i}}$. Znamená to, že čím vyšší jsou odkazy (stupně), tím vyšší je šance na získání více odkazů, protože mohou být vyléčeny větším počtem způsobů prostřednictvím mediátorů, které v podstatě ztělesňují intuitivní mechanismus bohatého bohatnutí (nebo preferenční pravidlo připevnění model Barabasi – Albert). Síť MDA lze tedy vidět, že se řídí pravidly PA, ale v přestrojení.^[41]

Nicméně pro ${ displaystyle m = 1}$ to popisuje vítěz bere vše mechanismus, jak jsme zjistili, že téměř ${ displaystyle 99 \%}$ z celkového počtu uzlů má stupeň jedna a jeden je velmi bohatý na stupeň. Tak jako ${ displaystyle m}$ hodnota zvyšuje rozdíl mezi super bohatými a chudými klesá a jako ${ displaystyle m> 14}$ najdeme přechod z mechanismu bohatého bohatství na bohatší bohatství na bohatší bohatství.

Nelineární preferenční připojení

Barabási – Albertův model předpokládá pravděpodobnost ${ displaystyle Pi (k)}$ uzel se připojí k uzlu ${ displaystyle i}$ je úměrná stupeň ${ displaystyle k}$ uzlu ${ displaystyle i}$. Tento předpoklad zahrnuje dvě hypotézy: zaprvé, že ${ displaystyle Pi (k)}$ záleží na ${ displaystyle k}$, na rozdíl od náhodných grafů, ve kterých ${ displaystyle Pi (k) = p}$, a za druhé, že funkční forma ${ displaystyle Pi (k)}$ je lineární v ${ displaystyle k}$. Přesná forma ${ displaystyle Pi (k)}$ není nutně lineární a nedávné studie prokázaly, že rozdělení stupňů silně závisí na ${ displaystyle Pi (k)}$

Krapivskij, Redner a Leyvraz^[38] prokázat, že bezškálová povaha sítě je zničena pro nelineární preferenční připojení. Jediným případem, kdy je topologie sítě bez měřítka, je ten, ve kterém je preferenční připojení asymptoticky lineární, tj. ${ displaystyle Pi (k_ {i}) sim a _ { infty} k_ {i}}$ tak jako ${ displaystyle k_ {i} do infty}$. V tomto případě vede rovnice rychlosti k

${ displaystyle P (k) sim k ^ {- gamma} { text {with}} gamma = 1 + { frac { mu} {a _ { infty}}}.}$

Tímto způsobem lze exponent rozložení stupňů naladit na libovolnou hodnotu mezi 2 a ${ displaystyle infty}$.

Hierarchický model sítě

Existuje další druh modelu bez měřítka, který roste podle některých vzorů, například hierarchický model sítě.^[42]

The iterativní konstrukce vedoucí k hierarchické síti. Počínaje plně připojeným klastrem pěti uzlů vytvoříme čtyři identické repliky spojující periferní uzly každého klastru s centrálním uzlem původního klastru. Z toho získáme síť 25 uzlů (N = 25). Opakováním stejného procesu můžeme vytvořit další čtyři repliky původního klastru - čtyři periferní uzly každého z nich se připojují k centrálnímu uzlu uzlů vytvořených v prvním kroku. To dává N = 125 a proces může pokračovat neomezeně dlouho.

Fitness model

Myšlenka je, že spojení mezi dvěma vrcholy je přiřazeno ne náhodně s pravděpodobností p stejné pro všechny dva vrcholy. Spíše pro každý vrchol j tam je vnitřní zdatnost X_j a spojení mezi vrcholem i a j je vytvořen s pravděpodobností ${ displaystyle p (x_ {i}, x_ {j})}$.^[43] V případě webu World Trade Web je možné rekonstruovat všechny nemovitosti s využitím jejich HDP jako fitness v zemi a

${ displaystyle p (x_ {i}, x_ {j}) = { frac { delta x_ {i} x_ {j}} {1+ delta x_ {i} x_ {j}}}.}$^[44]

Hyperbolické geometrické grafy

Za předpokladu, že síť má základní hyperbolickou geometrii, lze použít rámec prostorové sítě generovat distribuce stupňů bez měřítka. Toto heterogenní rozdělení stupňů pak jednoduše odráží negativní zakřivení a metrické vlastnosti podkladové hyperbolické geometrie.^[45]

Okrajová duální transformace pro generování grafů bez měřítka s požadovanými vlastnostmi

Počínaje grafy bez měřítka s nízkou mírou korelace a klastrovým koeficientem lze pomocí aplikace edge-dual transformace generovat nové grafy s mnohem vyššími korelačními koeficienty a shlukovacími koeficienty.^[22]

Uniform-Preference-Attachment model (model UPA)

Model UPA je varianta preferenčního modelu připevnění (navržená Pachonem a kol.), která bere v úvahu dvě různá pravidla připevnění: preferenční mechanismus připevnění (s pravděpodobností 1 − p), který zdůrazňuje bohatý bohatý systém, a jednotný výběr (s pravděpodobnost p) pro nejnovější uzly. Tato modifikace je zajímavá pro studium robustnosti bezrozměrného chování rozložení stupňů. Analyticky je prokázáno, že je zachováno asymptoticky rozdělení stupně práva.^[32]

Ideální sítě bez měřítka

V kontextu teorie sítí A ideální síť bez měřítka je náhodná síť s rozdělení stupňů v návaznosti na ideální plyn bez vodního kamene distribuce hustoty. Tyto sítě jsou schopny reprodukovat distribuce velikosti města a volební výsledky rozložením distribuce velikosti sociálních skupin pomocí teorie informací v komplexních sítích, když je na síť aplikován konkurenční proces růstu klastrů.^[46][47] Na modelech ideálních sítí bez měřítka je možné to prokázat Dunbarovo číslo je příčinou jevu známého jako „šest stupňů oddělení ' .

Nové charakteristiky

Pro síť bez měřítka s ${ displaystyle n}$ uzly a exponent mocninového zákona ${ displaystyle beta> 3}$, indukovaný podgraf vytvořený vrcholy se stupni většími než ${ displaystyle log {n} krát log ^ {*} {n}}$ je bezškálová síť s ${ displaystyle beta '= 2}$, téměř jistě (a.s.).^[48]

Viz také

• Náhodný graf - Graf generovaný náhodným procesem
• Erdős – Rényiho model - Dva úzce související modely pro generování náhodných grafů
• Nelineární preferenční připojení
• Bose – Einsteinova kondenzace (teorie sítě) - Výskyt v teorii sítí
• Měřítko invariance
• Komplexní síť - Síť s netriviálními topologickými rysy
• Webgraf
• Barabási – Albertův model
• Bianconi – Barabásiho model

Reference

Další čtení

• Albert R .; Barabási A.-L. (2002). "Statistická mechanika komplexních sítí". Rev. Mod. Phys. 74 (1): 47–97. arXiv:cond-mat / 0106096. Bibcode:2002RvMP ... 74 ... 47A. doi:10.1103 / RevModPhys.74.47. S2CID  60545.
• Amaral LAN, Scala A, Barthelemy M, Stanley HE (2000). „Třídy sítí malého světa“. PNAS. 97 (21): 11149–52. arXiv:cond-mat / 0001458. Bibcode:2000PNAS ... 9711149A. doi:10.1073 / pnas.200327197. PMC  17168. PMID  11005838.
• Barabási, Albert-László (2004). Propojeno: Jak je všechno spojeno se vším ostatním. ISBN  0-452-28439-2.
• Barabási, Albert-László; Bonabeau, Eric (květen 2003). „Bezškálové sítě“ (PDF). Scientific American. 288 (5): 50–9. Bibcode:2003SciAm.288e..60B. doi:10.1038 / scientificamerican0503-60. PMID  12701331.
• Dan Braha; Yaneer Bar-Yam (2004). „Topologie rozsáhlých inženýrských sítí pro řešení problémů“ (PDF). Phys. Rev.. 69 (1): 016113. Bibcode:2004PhRvE..69a6113B. doi:10.1103 / PhysRevE.69.016113. PMID  14995673. S2CID  1001176.
• Caldarelli G. "Bezškálové sítě “ Oxford University Press, Oxford (2007).
• Caldarelli G .; Capocci A .; De Los Rios P ​​.; Muñoz M.A. (2002). "Bezškálové sítě s různou vrcholovou vnitřní kondicí". Dopisy o fyzické kontrole. 89 (25): 258702. arXiv:cond-mat / 0207366. Bibcode:2002PhRvL..89y8702C. doi:10.1103 / PhysRevLett.89.258702. PMID  12484927.
• R. Cohen; K. Erez; D. ben-Avraham; S. Havlin (2000). "Odolnost internetu proti náhodným poruchám". Phys. Rev. Lett. 85 (21): 4626–8. arXiv:cond-mat / 0007048. Bibcode:2000PhRvL..85,4626C. doi:10.1103 / PhysRevLett.85.4626. PMID  11082612. S2CID  15372152.
• R. Cohen; K. Erez; D. ben-Avraham; S. Havlin (2001). „Rozpad internetu pod úmyslným útokem“. Phys. Rev. Lett. 86 (16): 3682–5. arXiv:cond-mat / 0010251. Bibcode:2001PhRvL..86.3682C. doi:10.1103 / PhysRevLett.86.3682. PMID  11328053. S2CID  3852896.
• R. Cohen; K. Erez; D. ben-Avraham; S. Havlin (2002). „Bezškálové sítě v mřížích“. Phys. Rev. Lett. 89 (21): 218701. arXiv:cond-mat / 0205613. Bibcode:2002PhRvL..89u8701R. doi:10.1103 / fyzrevlett.89.218701. PMID  12443452. S2CID  13379794.
• Dangalchev, Ch. (2004). „Generační modely pro sítě bez měřítka“. Physica A. 338 (3–4): 659–671. Bibcode:2004PhyA..338..659D. doi:10.1016 / j.physa.2004.01.056.
• Dorogovtsev, S.N .; Mendes, J.F.F .; Samukhin, A.N. (2000). „Struktura rostoucích sítí: přesné řešení Barabási - Albertův model“. Phys. Rev. Lett. 85 (21): 4633–6. arXiv:cond-mat / 0004434. Bibcode:2000PhRvL..85,4633D. doi:10.1103 / PhysRevLett.85.4633. PMID  11082614.
• Dorogovtsev, S.N .; Mendes, J.F.F. (2003). Evoluce sítí: od biologických sítí po internet a WWW. Oxford University Press. ISBN  0-19-851590-1.
• Dorogovtsev, S.N .; Goltsev A.V .; Mendes, J.F.F. (2008). "Kritické jevy ve složitých sítích". Rev. Mod. Phys. 80 (4): 1275–1335. arXiv:0705.0010. Bibcode:2008RvMP ... 80.1275D. doi:10.1103 / RevModPhys.80.1275. S2CID  3174463.
• Dorogovtsev, S.N .; Mendes, J.F.F. (2002). "Evolution of networks". Pokroky ve fyzice. 51 (4): 1079–1187. arXiv:cond-mat / 0106144. Bibcode:2002AdPhy..51.1079D. doi:10.1080/00018730110112519. S2CID  429546.
• Erdős, P.; Rényi, A. (1960). On the Evolution of Random Graphs (PDF). 5. Publication of the Mathematical Institute of the Hungarian Academy of Science. pp. 17–61.
• Faloutsos, M.; Faloutsos, P.; Faloutsos, C. (1999). "On power-law relationships of the internet topology". Comp. Comm. Rev. 29 (4): 251–262. doi:10.1145/316194.316229.
• Li, L .; Alderson, D.; Tanaka, R.; Doyle, J.C.; Willinger, W. (2005). "Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)". arXiv:cond-mat/0501169.
• Kumar, R .; Raghavan, P .; Rajagopalan, S .; Sivakumar, D.; Tomkins, A.; Upfal, E. (2000). "Stochastic models for the web graph" (PDF). Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). Redondo Beach, CA: IEEE CS Press. str. 57–65.
• Matlis, Jan (November 4, 2002). "Scale-Free Networks".
• Newman, Mark E.J. (2003). "Struktura a funkce složitých sítí". Recenze SIAM. 45 (2): 167–256. arXiv:cond-mat / 0303516. Bibcode:2003SIAMR..45..167N. doi:10.1137 / S003614450342480. S2CID  221278130.
• Pastor-Satorras, R.; Vespignani, A. (2004). Evolution and Structure of the Internet: A Statistical Physics Approach. Cambridge University Press. ISBN  0-521-82698-5.
• Pennock, D.M.; Flake, G.W.; Lawrence, S .; Glover, E.J.; Giles, C.L. (2002). "Winners don't take all: Characterizing the competition for links on the web". PNAS. 99 (8): 5207–11. Bibcode:2002PNAS...99.5207P. doi:10.1073/pnas.032085699. PMC  122747. PMID  16578867.
• Robb, John. Scale-Free Networks and Terrorism, 2004.
• Keller, E.F. (2005). "Revisiting "scale-free" networks". BioEssays. 27 (10): 1060–8. doi:10.1002/bies.20294. PMID  16163729. Archivovány od originál dne 13. 8. 2011.
• Onody, R.N.; de Castro, P.A. (2004). "Complex Network Study of Brazilian Soccer Player". Phys. Rev.. 70 (3): 037103. arXiv:cond-mat/0409609. Bibcode:2004PhRvE..70c7103O. doi:10.1103/PhysRevE.70.037103. PMID  15524675. S2CID  31653489.
• Reuven Cohen; Shlomo Havlin (2003). "Scale-Free Networks are Ultrasmall". Phys. Rev. Lett. 90 (5): 058701. arXiv:cond-mat / 0205476. Bibcode:2003PhRvL..90e8701C. doi:10.1103 / PhysRevLett.90.058701. PMID  12633404. S2CID  10508339.
• Kasthurirathna, D.; Piraveenan, M. (2015). "Complex Network Study of Brazilian Soccer Player". Sci. Rep. V tisku.