Rozvíjející se síť - Evolving network

Animace vyvíjející se sítě podle původního modelu Barabasi – Albert

Rozvíjející se sítě jsou sítí že se mění jako funkce času. Jsou přirozeným rozšířením síťová věda protože téměř všechny sítě reálného světa se časem vyvíjejí, a to buď přidáváním nebo odebíráním uzly nebo odkazy v průběhu času. Všechny tyto procesy se často vyskytují současně, například v sociální sítě kde si lidé postupem času vytvářejí a ztrácejí přátele, čímž vytvářejí a ničí hrany, a někteří lidé se stávají součástí nových sociálních sítí nebo opouštějí své sítě a mění uzly v síti. Vyvíjející se koncepty sítí staví na zavedených teorie sítí a nyní se zavádějí do studia sítí v mnoha různých oborech.

Pozadí teorie sítí

Studium sítí sleduje jeho základy k rozvoji teorie grafů, který nejprve analyzoval Leonhard Euler v roce 1736, kdy napsal slavný Sedm mostů v Königsbergu papír. Pravděpodobnostní teorie sítí se poté vyvinula pomocí osmi slavných studijních prací náhodné grafy napsáno Paul Erdős a Alfréd Rényi. The Erdős – Rényiho model (ER) předpokládá, že graf se skládá z N označené uzly, kde je každá dvojice uzlů spojena přednastavenou pravděpodobností p.

Watts – Strogatzův graf

Ačkoli jednoduchost modelu ER pomohla najít mnoho aplikací, nepopisuje přesně mnoho sítí v reálném světě. Model ER se nepodařilo generovat místní shlukování a triadické uzávěry tak často, jak se nacházejí v sítích reálného světa. Proto Watts a Strogatzův model Bylo navrženo, že síť je konstruována jako pravidelná prstencová mřížka a poté jsou uzly podle určité pravděpodobnosti znovu propojeny β.^[1] To vytváří lokálně seskupenou síť a dramaticky snižuje průměrná délka cesty, vytváření sítí, které představují fenomén malého světa pozorováno v mnoha sítích reálného světa.^[2]

Navzdory tomuto úspěchu modely ER a Watts a Storgatz nezohledňují formulaci hubů, jak je pozorováno v mnoha sítích reálného světa. Rozložení stupňů v modelu ER následuje a Poissonovo rozdělení, zatímco model Watts a Strogatz vytváří grafy, které jsou homogenní v stupeň. Mnoho sítí je místo toho škálovatelných, což znamená, že jejich rozložení stupňů následuje mocenský zákon formuláře:

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

Ukázalo se, že tento exponent je přibližně 3 pro mnoho sítí v reálném světě, nejedná se však o univerzální konstantu a neustále závisí na parametrech sítě ^[3]

První vyvíjející se síťový model - sítě bez měřítka

Model Barabási – Albert (BA) byl prvním široce přijímaným modelem sítě bez měřítka. Toho bylo dosaženo začleněním preferenční přílohu a růst, kdy jsou uzly do sítě přidávány v průběhu času a je větší pravděpodobnost, že budou propojeny s jinými uzly s vysokými distribucemi. Model BA byl poprvé aplikován na distribuci stupňů na webu, kde lze jasně vidět oba tyto efekty. Nové webové stránky jsou přidávány v průběhu času a každá nová stránka pravděpodobně odkazuje na vysoce viditelné rozbočovače Google které mají vysoký stupeň distribuce než do uzlů pouze s několika odkazy. Formálně je tato preferenční příloha:

${ displaystyle p_ {i} = { frac {k_ {i}} { displaystyle sum _ {j} k_ {j}}},}$

Dodatky k modelu BA

Model BA byl prvním modelem, který odvodil topologii sítě ze způsobu, jakým byla síť konstruována s přidáváním uzlů a odkazů v průběhu času. Model však vytváří pouze nejjednodušší předpoklady nezbytné pro vznik bezškálové sítě, konkrétně že existuje lineární růst a lineární preferenční připojení. Tento minimální model nezachycuje odchylky ve tvaru rozložení stupňů, odchylky v exponentu stupňů ani nezávislé na velikosti shlukovací koeficient. Proto byl původní model od té doby upraven^{[kým? ]} plněji zachytit vlastnosti rozvíjejících se sítí zavedením několika nových vlastností.

Zdatnost

Jednou z obav modelu BA je, že rozložení stupňů každého uzlu je silné Pozitivní zpětná vazba přičemž nejčasnější uzly s vysokým stupněm distribuce nadále dominují síti po neomezenou dobu. To však lze zmírnit zavedením vhodnosti pro každý uzel, což upravuje pravděpodobnost vytvoření nových odkazů s daným uzlem nebo dokonce odstranění odkazů na tento uzel.^[4]

Aby byla zachována preferenční příloha z modelu BA, je tato vhodnost vynásobena preferenční přílohou založenou na rozdělení stupňů, aby byla skutečná pravděpodobnost, že je vytvořen odkaz, který se připojuje k uzlu i.

${ displaystyle Pi (k_ {i}) = { frac { eta _ {i} k_ {i}} { displaystyle sum _ {j} eta _ {j} k_ {j}}},}$

Kde ${ displaystyle eta}$ je fitness, který může také záviset na čase. Může dojít k úbytku zdatnosti s ohledem na čas, který lze formalizovat pomocí

${ displaystyle Pi (k_ {i}) propto k_ {i} (t-t_ {i}) ^ {- nu},}$

kde ${ displaystyle gamma}$ se zvyšuje s ${ displaystyle nu.}$

Odebrání uzlů a opětovné propojení

Další komplikace vznikají, protože uzly mohou být ze sítě odstraněny s určitou pravděpodobností. Kromě toho mohou být zničeny existující odkazy a mohou být vytvořena nová propojení mezi existujícími uzly. Pravděpodobnost výskytu těchto akcí může záviset na čase a může také souviset s kondicí uzlu. Pravděpodobnosti lze těmto událostem přiřadit studiem charakteristik dané sítě, aby se rozšířila modelová síť se stejnými vlastnostmi. K tomuto růstu by došlo v každém časovém kroku s jednou z následujících akcí:

Problém p: přidat interní odkaz.

Problém q: smazat odkaz.

Problém r: smazat uzel.

Prob 1-p-q-r: přidat uzel.

Další způsoby charakterizace vyvíjejících se sítí

Kromě rozšiřování síťových modelů, jak je popsáno výše, mohou nastat situace, kdy jsou pro charakterizaci určitých vlastností vyvíjejících se sítí užitečnější nebo pohodlnější jiné metody.

Konvergence k rovnováze

V síťových systémech, kde probíhá soutěžní rozhodování, se teorie her často používá k modelování dynamiky systému a konvergenci směrem k rovnováze lze považovat za hnací sílu topologické evoluce. Například Kasthurirathna a Piraveenan ^[5] prokázali, že když jednotlivci v systému vykazují různé úrovně racionality, může být zlepšení celkové racionality systému evolučním důvodem pro vznik sítí bez měřítka. Ukázali to použitím evolučního tlaku na původně náhodnou síť, která simuluje řadu klasických her, takže síť konverguje k Nashovým rovnováhám, zatímco je dovoleno znovu se zapojit. Sítě se během tohoto procesu stávají čím dál více bezrozměrnějšími.

Zacházejte s vyvíjejícími se sítěmi jako s po sobě jdoucími snímky statické sítě

Nejběžnějším způsobem, jak zobrazit vyvíjející se sítě, je považovat je za postupné statické sítě. To by mohlo být koncipováno jako jednotlivé statické obrazy, které tvoří a film. Existuje mnoho jednoduchých parametrů k popisu statické sítě (počet uzlů, hran, délky cesty, připojených komponent) nebo k popisu konkrétních uzlů v grafu, jako je počet odkazů nebo koeficient shlukování. Tyto vlastnosti lze poté individuálně studovat jako časovou řadu pomocí pojmů zpracování signálu.^[6] Například můžeme sledovat počet odkazů navázaných na server za minutu tím, že se podíváme na po sobě jdoucí snímky sítě a spočítáme tyto odkazy v každém snímku.

Analogie snímků k filmu bohužel také odhaluje hlavní potíže s tímto přístupem: použité časové kroky jsou velmi zřídka navrhovány sítí a jsou namísto toho libovolné. Použití extrémně malých časových kroků mezi jednotlivými snímky zachovává rozlišení, ale může ve skutečnosti zakrýt širší trendy, které se stanou viditelnými pouze v delších časových intervalech. Naopak použití větších časových rozsahů ztrácí časové pořadí událostí v každém snímku. Proto může být obtížné najít vhodný časový rámec pro rozdělení vývoje sítě na statické snímky.

Definujte dynamické vlastnosti

Může být důležité podívat se na vlastnosti, které nelze přímo pozorovat, když budeme vyvíjející se sítě považovat za posloupnost snímků, jako je doba trvání kontaktů mezi uzly^[7] Lze definovat další podobné vlastnosti a pak je možné místo toho sledovat tyto vlastnosti prostřednictvím vývoje sítě a přímo je vizualizovat.

Dalším problémem při používání postupných snímků je, že pouze nepatrné změny v topologii sítě mohou mít velký vliv na výsledek algoritmů určených k hledání komunit. Proto je nutné použít neklasickou definici komunit, která umožňuje sledovat vývoj komunity prostřednictvím souboru pravidel, jako je narození, smrt, sloučení, rozdělení, růst a kontrakce.^[8][9]

Aplikace

Mapa tras plánovaného komerčního leteckého provozu na světě, 2009. Tato síť se neustále vyvíjí, protože jsou naplánovány nebo zrušeny nové trasy.

Téměř všechny sítě v reálném světě se vyvíjejí, protože jsou budovány v průběhu času. Změnou příslušných pravděpodobností popsaných výše je možné použít rozšířený model BA ke konstrukci sítě s téměř identickými vlastnostmi jako mnoho pozorovaných sítí.^[10] Koncept bezškálových sítí nám navíc ukazuje, že vývoj času je nezbytnou součástí pochopení vlastností sítě a že je obtížné modelovat stávající síť tak, jak byla vytvořena okamžitě. Mezi skutečně vyvíjející se sítě, které jsou v současné době studovány, patří sociální sítě, komunikační sítě, Internet, síť filmových herců, Celosvětová Síť, a dopravní sítě.

Další čtení

• „Understanding Network Science,“ https://web.archive.org/web/20110718151116/http://www.zangani.com/blog/2007-1030-networkingscience
• „Linked: The New Science of Networks“, A.-L. Nakladatelství Barabási Perseus, Cambridge.

Reference