Model Barabashi-Albert

Model Barabashi-Albert (BA) je algoritmus pro generování náhodných sítí bez měřítka využívající princip preferenčního připojení. Sítě bez měřítka jsou rozšířeny v přirozených sítích (potravinové řetězce) a sítích vytvořených lidmi ( Internet , World Wide Web , citační sítě , některé sociální sítě ).

Koncepty

Mnoho studovaných sítí spadá do třídy sítí bez měřítka. To znamená, že mají mocninnou distribuci ve stupni uzlů, zatímco modely náhodných grafů ( Watts-Strogatza Erdős-Renyi ) takovou distribuci nemají. Barabasi-Albertův model je jedním z několika navrhovaných mocninných modelů, které generují sítě bez měřítka. Zahrnuje dva důležité obecné pojmy:

růst sítě
Princip preferovaného připojení (PP)

Oba koncepty jsou široce zastoupeny v sítích reálného světa. Růst znamená, že počet síťových uzlů se v průběhu času zvyšuje.

Princip preferenčního připojení spočívá v tom, že čím více spojení má uzel, tím je pro něj výhodnější vytvářet nová spojení. Uzly s nejvyšším stupněm mají více příležitostí převzít odkazy přidané do sítě. Intuitivně lze princip preferenčního připoutání pochopit, pokud uvažujeme v pojmech sociálních sítí, které lidi sbližují. Spojení z A do B zde znamená, že osoba A „zná“ nebo je „známá“ s osobou B. Silně propojené uzly představují známé osoby s velkým počtem spojení. Když do komunity vstoupí nováček, je pro něj výhodnější kontaktovat někoho ze známých lidí než relativně neznámého. Podobně na World Wide Web jsou stránky spojeny s centry, jako jsou známé weby jako Google nebo Wikipedia , spíše než se stránkami, které nejsou příliš známé. Pokud je náhodně vybrána nová stránka pro propojení, pak pravděpodobnost výběru konkrétní stránky bude úměrná jejímu stupni. To vysvětluje princip preferenčního připoutání.

Princip preferenčního připojení je příkladem pozitivní zpětné vazby, kdy jsou zpočátku náhodné variace (jeden uzel zpočátku má více odkazů nebo začíná sbírat odkazy dříve než ostatní) automaticky zesíleny, čímž se výrazně zvětšuje mezera. To se také někdy nazývá Matthewův efekt , „bohatí bohatnou“ nebo autokatalýza v chemii.

Algoritmus

Síť začíná počáteční sítí s uzly. a stupeň každého uzlu v počáteční síti musí být alespoň 1, jinak bude vždy oddělen od zbytku sítě. $m_{0}$ $m_{0}>=2$

V každém okamžiku je do sítě přidán nový uzel. Každý nový uzel se připojuje k existujícím uzlům s pravděpodobností úměrnou počtu spojení těchto uzlů. Formálně je pravděpodobnost , že se nový uzel připojí k uzlu i: [1] $p_{i}$

p_{i}={k_{i} \over \sum _{j}k_{j))

kde je stupeň i-tého uzlu a jmenovatel sečte stupně všech existujících uzlů. Nejvíce propojené uzly („rozbočovače“) mají tendenci hromadit ještě více připojení, zatímco uzly s malým počtem připojení pravděpodobně nebudou vybrány pro připojení k novým uzlům. Nové uzly mají „předvolbu“ pro připojení k nejvíce připojeným uzlům. $k_i$

Vlastnosti

Rozvod energie

Mocninné rozložení v BA modelu je bez měřítka, přesněji řečeno, podřizuje se mocninnému zákonu

{\displaystyle P\left(k\right)\sim k^{-3))

Průměrná délka cesty

Průměrná délka cesty v BA modelu se v průměru zvyšuje jako logaritmus velikosti sítě. Přesný tvar má dvojitou logaritmickou korekci [1] a vypadá takto

\ell \sim {\frac {\ln N}{\ln \ln N)).

BA model má systematicky kratší průměrnou cestu než náhodný graf.

Korelace stupně uzlu

Korelace stupňů připojených uzlů se v BA modelu vyvíjejí náhodně, kvůli zvláštnostem rozvoje sítě. Pravděpodobnost nalezení spojení mezi uzly se stupni a v BA modelu je prezentována jako

n_{k\ell }={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+ \ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right) \left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.

Samozřejmě, že výsledek bude jiný, pokud distribuce byla nekorelovaná, . ${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3))$

Shlukovací koeficient

Zatím neexistují žádné analytické hodnoty shlukovacího koeficientu BA modelu. Empiricky získané shlukovací koeficienty jsou obecně mnohem vyšší pro BA model než pro náhodné sítě. Shlukovací koeficient také závisí na velikosti sítě podle přibližného mocninného zákona:

C\sim N^{-0,75}.

[jeden]

Toto chování se stále liší od chování malých sítí, kde shlukování nezávisí na velikosti sítě. V případě hierarchických sítí se shlukování jako funkce stupně uzlů také řídí mocninným zákonem:

C(k)=k^{-1}.

Tyto výsledky analyticky získali Dorogovtsev, Goltsev a Mendes. [3]

Spektrální kvality

Tvar spektrální hustoty BA modelu se liší od půlkruhové spektrální hustoty náhodného grafu. Má trojúhelníkový tvar s vrcholem mnohem výše než půlkruh a hrany se zmenšují podle mocninného zákona.

Limitní případy

Model A

Model A si zachovává růst, ale nezahrnuje princip preferenčního připoutanosti. Pravděpodobnost připojení nového uzlu ke stávajícím je všude stejná. Distribuce konečných stupňů v tomto případě naznačuje, že samotný růst nestačí k dosažení struktury bez měřítka.

Model B

Model B zachovává princip preferenčního připojení, ale vylučuje růst. Model začíná s pevným počtem odpojených uzlů a přidává odkazy, přednostně volí uzly vysokého stupně jako cíle. Ačkoli se na začátku simulace zdá, že distribuce energie je bez měřítka, je nestabilní a nakonec se přiblíží gaussovu, jak se síť blíží saturaci. Princip PP tedy sám o sobě nestačí k vytvoření struktury bez vodního kamene. [jeden]

Neschopnost modelů A a B získat distribuci bez měřítka naznačuje, že růst a PP jsou stejně nezbytné pro reprodukci stacionárního rozložení mocnin, které lze vidět v sítích reálného světa.

Historie

Princip preferenčního připojení byl poprvé použit k vysvětlení Yuleova mocenského rozložení v roce 1925 [4] , ačkoli Yuleova matematická analýza je moderními standardy považována za nejasnou kvůli nedostatku vhodných nástrojů pro analýzu náhodných procesů. Moderní metodu základní kinetické rovnice, která dává přehlednější závěr, na problém aplikoval Herbert Simon v roce 1955 [5] v rámci studia velikosti měst a dalších jevů. Poprvé ji na růst sítě aplikoval Derek de Solla Price v roce 1976 [6] , který se zajímal o citační sítě mezi vědeckými publikacemi. Název „preferované propojení“ a současná obliba bezškálových modelů sítí je dílem Alberta-Laszla Barabasiho a Rekiho Alberta, který tento proces nezávisle objevil v roce 1999 a aplikoval jej na mocenskou distribuci na World Wide Web. [2]

Poznámky

↑ 1 2 3 4 Albert, Řeka; R. Albert; A.L. Barabasi. Statistická mechanika komplexních sítí (anglicky) // Reviews of Modern Physics : journal. - 2002. - Sv. 74 . - str. 47-97 . - doi : 10.1103/RevModPhys.74.47 . - . Archivováno z originálu 24. srpna 2015.
↑ 1 2 Albert-László Barabási & Reka Albert Vznik škálování v náhodných sítích (anglicky) // Science : journal. - 1999. - říjen ( roč. 286 , č. 5439 ). - S. 509-512 . - doi : 10.1126/science.286.5439.509 . Archivováno z originálu 17. dubna 2012.
↑ SN Dorogovtsev, AV Goltsev a JFF Mendes, e-print cond-mat/0112143.
↑ Yule, G. Udny . Matematická teorie evoluce založená na závěrech Dr. JC Willis, FRS // Journal of the Royal Statistical Society : deník. - 1925. - Sv. 88 , č. 3 . - str. 433-436 . - doi : 10.2307/2341419 . — .
↑ Herbert A. Simon . On a Class of Skew Distribution Functions (anglicky) // Biometrika : journal. - 1955. - prosinec ( roč. 42 , č. 3-4 ). - str. 425-440 . - doi : 10.1093/biomet/42.3-4.425 .
↑ DJ de Solla Price . Obecná teorie bibliometrických a jiných procesů kumulativních výhod (anglicky) // Journal of the American Society for Information Science : deník. - 1976. - Sv. 27 . - S. 292-306 . - doi : 10.1002/asi.4630270505 .

Odkazy

Komplexní sítě