Multidimenzionální síť - Multidimensional network

Síťová věda
Teorie
Graf Složitá síť Nákaza Malý svět Bez měřítka Struktura komunity Perkolace Vývoj Ovladatelnost Grafická kresba Sociální kapital Analýza odkazů Optimalizace Vzájemnost Uzavření Homofilně 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ý nervový Vzájemně závislé Sémantický Prostorový Závislost Tok na čipu
Grafy
Funkce Klika Komponent Střih Cyklus Datová struktura Okraj Smyčka Sousedství Cesta Vrchol Seznam  / matice přilehlosti Seznam incidentů  / matice Typy Bipartit Kompletní Režie Hyper Multi Náhodný Vážený
Metriky Algoritmy
Centrálnost Stupeň Motiv Shlukování Distribuce titulů 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á geometrie (RGG) Hyperbolické (HGN) Hierarchický Stochastický blok Blockmodeling Maximální entropie Měkká konfigurace Srovnávací hodnota LFR Dynamika Booleovská síť na bázi agenta Epidemie / SIR
Seznamy Kategorie
Témata Software Síťoví vědci Kategorie: Teorie sítě Kategorie: Teorie grafů
proti t E

V teorie sítí , vícerozměrných sítích , se zvláštním typem vícevrstvé sítě , jsou sítě s více druhy vztahů. Stále sofistikovanější pokusy modelovat systémy reálného světa jako vícerozměrné sítě poskytly cenné poznatky v oblasti analýzy sociálních sítí , ekonomiky, městské a mezinárodní dopravy , ekologie , psychologie, medicíny, biologie, obchodu, klimatologie, fyziky, počítačové neurovědy , řízení provozu , infrastruktury a financí.

Terminologie

Rychlé zkoumání složitých sítí v posledních letech bylo doprovázeno nedostatkem standardizovaných konvencí pojmenování, protože různé skupiny používají překrývající se a rozporuplnou terminologii k popisu konkrétních konfigurací sítě (např. Multiplex, vícevrstvé, víceúrovňové, multidimenzionální, multirelační, propojené). Formálně jsou vícerozměrné sítě hranami označené multigrafy . Výraz „plně multidimenzionální“ byl rovněž použit pro označení vícedílný hrany značené multigraf. Vícerozměrné sítě byly také nedávno přepracovány jako specifické instance vícevrstvých sítí. V tomto případě existuje tolik vrstev, kolik je dimenzí, a vazby mezi uzly v každé vrstvě jsou jednoduše všechny vazby pro danou dimenzi.

Definice

Nevážené vícevrstvé sítě

V základní teorie sítí, síť je reprezentována grafem , ve kterém je množina uzlů a tyto vazby mezi uzly, obvykle reprezentován jako tice uzlů . I když je tato základní formalizace užitečná pro analýzu mnoha systémů, sítě v reálném světě mají často přidanou komplexnost v podobě více typů vztahů mezi prvky systému. Časná formalizace této myšlenky proběhla díky její aplikaci v oblasti analýzy sociálních sítí (viz např. Dokumenty o relačních algebrách v sociálních sítích), v nichž více forem sociálního spojení mezi lidmi představovalo více typů odkazů. ${\ displaystyle G = (V, E)}$${\ displaystyle V}$${\ displaystyle E}$${\ displaystyle u, v \ v V}$

Aby se přizpůsobila přítomnost více než jednoho typu odkazu, je vícerozměrná síť reprezentována trojkou , kde je množina dimenzí (nebo vrstev), z nichž každý člen je jiný typ odkazu, a skládá se z trojic s a . ${\ displaystyle G = (V, E, D)}$${\ displaystyle D}$${\ displaystyle E}$${\ displaystyle (u, v, d)}$${\ displaystyle u, v \ v V}$${\ Displaystyle d \ v D}$

Všimněte si, že stejně jako ve všech směrovaných grafech jsou odkazy a odlišné. ${\ displaystyle (u, v, d)}$${\ Displaystyle (v, u, d)}$

Podle konvence je počet odkazů mezi dvěma uzly v dané dimenzi buď 0 nebo 1 ve vícerozměrné síti. Celkový počet vazeb mezi dvěma uzly ve všech dimenzích je však menší nebo roven . ${\ displaystyle | D |}$

Vážené vícevrstvé sítě

V případě vážené sítě je tento triplet rozšířen na čtyřnásobek , kde je váha na spojnici mezi a v dimenzi . ${\ Displaystyle e = (u, v, d, w)}$${\ displaystyle w}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle d}$

Multiplexová síť evropských letišť. Každá letecká společnost označuje jinou vrstvu. Vizualizace vytvořená pomocí softwaru muxViz

Navíc, jak je často užitečné při analýze sociálních sítí, mohou váhy odkazů nabývat kladných nebo záporných hodnot. Takto podepsané sítě mohou lépe odrážet vztahy jako přátelství a nepřátelství v sociálních sítích. Alternativně mohou být spojovací značky považovány za samotné dimenze, např. Kde a Tento přístup má zvláštní hodnotu při zvažování nevážených sítí. ${\ displaystyle G = (V, E, D)}$${\ displaystyle D = \ {-1,0,1 \}}$${\ Displaystyle E = \ {(u, v, d); u, v \ v V, d \ v D \}}$

Toto pojetí dimenzionality lze rozšířit, pokud atributy ve více dimenzích vyžadují specifikaci. V tomto případě jsou odkazy n -tuples . Taková rozšířená formulace, ve které mohou existovat odkazy ve více dimenzích, je neobvyklá, ale byla použita při studiu vícerozměrných časově proměnných sítí . ${\ Displaystyle e = (u, v, d_ {1} \ dots d_ {n-2})}$

World Economic Forum mapa globálních rizik a globálních trendů, modelovat jako vzájemně závislé síti (také známý jako síť sítí). Vizualizace vytvořená pomocí softwaru [ http://muxviz.net/ muxViz

Obecná formulace z hlediska tenzorů

Zatímco unidimenzionální sítě mají dvojrozměrné matice sousednosti o velikosti , ve vícerozměrné síti s dimenzemi se matice sousednosti stává vícevrstvým tenzorem sousednosti, čtyřrozměrnou maticí velikosti . Pomocí indexové notace mohou být matice sousednosti označeny pomocí , pro kódování spojení mezi uzly a , zatímco vícevrstvé tenzory sousednosti jsou označeny , pro kódování spojení mezi uzlem ve vrstvě a uzlem ve vrstvě . Stejně jako v neidimenzionálních matricích jsou v tomto rámci snadno umístěny směrované odkazy, podepsané odkazy a váhy. ${\ displaystyle V \ times V}$${\ displaystyle D}$${\ displaystyle (V \ times D) \ times (V \ times D)}$${\ displaystyle A_ {j}^{i}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle M_ {j \ beta}^{i \ alpha}}$${\ displaystyle i}$${\ displaystyle \ alpha}$${\ displaystyle j}$${\ displaystyle \ beta}$

V případě multiplexních sítí , což jsou speciální typy vícevrstvých sítí, kde uzly nelze propojit s jinými uzly v jiných vrstvách, stačí trojrozměrná matice velikosti se záznamy , která bude reprezentovat strukturu systému kódováním spojení mezi uzly a ve vrstvě . ${\ displaystyle (V \ times V) \ times D}$${\ displaystyle A_ {ij}^{\ alpha}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle \ alpha}$

Multiplexová sociální síť ságy Star Wars. Každá vrstva označuje jinou epizodu a dva uzly jsou navzájem spojeny, pokud odpovídající postavy jednaly společně v jedné nebo více scénách. Vizualizace pomocí softwaru muxViz

Multidimenzionální definice specifické pro síť

Vícevrstevní sousedé

V multidimenzionální síti jsou sousedy nějakého uzlu všechny uzly připojené k napříč dimenzemi. ${\ displaystyle v}$${\ displaystyle v}$

Délka vícevrstvé cesty

Cesta mezi dvěma uzly v multidimenzionální síti může být představována vektorem r , ve kterém th vstup do r je počet vazeb, jimiž projíždí v tého rozměru . Stejně jako u překrývajícího se stupně lze součet těchto prvků brát jako hrubé měřítko délky dráhy mezi dvěma uzly. ${\ displaystyle = (r_ {1}, \ dots r_ {| D |})}}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle G}$

Síť vrstev

Existence více vrstev (nebo dimenzí) umožňuje zavést nový koncept sítě vrstev , charakteristický pro vícevrstvé sítě. Ve skutečnosti mohou být vrstvy propojeny takovým způsobem, že jejich strukturu lze popsat sítí, jak je znázorněno na obrázku.

Síť vrstev ve vícevrstvých systémech

Síť vrstev je obvykle vážená (a může být směrovaná), ačkoli obecně hmotnosti závisí na aplikaci zájmu. Jednoduchým přístupem je pro každou dvojici vrstev sečíst všechny váhy ve spojích mezi jejich uzly, aby se získaly váhy hran, které lze zakódovat do matice . Tenzor sousednosti úrovně 2, představující základní síť vrstev v prostoru, je dán vztahem ${\ displaystyle q _ {\ alpha \ beta}}$${\ displaystyle \ mathbb {R} ^{L \ times L}}$

${\ Displaystyle \ Psi _ {\ delta}^{\ gamma} = \ sum \ limits _ {\ alpha, \ beta = 1}^{L} q _ {\ alpha \ beta} E _ {\ delta}^{\ gamma } (\ alpha \ beta)}$

kde je kanonická matice se všemi složkami rovna nule, s výjimkou položky odpovídající řádku a sloupci , která se rovná jedné. Pomocí tenzorové notace je možné získat (váženou) síť vrstev z vícevrstvého tenzorového sousedního as . ${\ Displaystyle E _ {\ delta}^{\ gamma} (\ alpha \ beta)}$${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ Displaystyle \ Psi _ {\ delta}^{\ gamma} = M_ {j \ delta}^{i \ gamma} U_ {i}^{j}}$

Opatření centrálnosti

Stupeň

V nepropojené vícerozměrné síti, kde chybí mezivrstevné odkazy, je stupeň uzlu reprezentován vektorem délky . Zde je alternativní způsob označení počtu vrstev ve vícevrstvých sítích. U některých výpočtů však může být užitečnější jednoduše sečíst počet odkazů sousedících s uzlem ve všech dimenzích. To je překrývající stupeň : . Stejně jako u neidimenzionálních sítí lze podobně rozlišovat příchozí odkazy a odchozí odkazy. Pokud jsou k dispozici mezivrstevné odkazy, musí být výše uvedená definice upravena tak, aby je zohledňovala, a vícevrstvý stupeň je dán symbolem ${\ Displaystyle | D |: \ mathbf {k} = (k_ {i}^{1}, \ dots k_ {i}^{| D |})}$${\ displaystyle | D |}$${\ displaystyle L}$${\ Displaystyle \ sum _ {\ alpha = 1}^{| D |} k_ {i}^{\ alpha}}$

${\ Displaystyle k^{i} = M_ {j \ beta}^{i \ alpha} U _ {\ alpha}^{\ beta} u^{j} = \ sum _ {\ alpha, \ beta = 1}^ {L} \ sum _ {j = 1}^{N} M_ {j \ beta}^{i \ alpha}}$

kde tenzory a mají všechny složky rovné 1. Heterogenitu v počtu spojení uzlu napříč různými vrstvami lze vzít v úvahu prostřednictvím koeficientu participace. ${\ displaystyle U _ {\ alpha}^{\ beta}}$${\ displaystyle u^{j}}$

Všestrannost jako vícevrstevná centrálnost

Když se rozšíří na propojené vícevrstvé sítě, tj. Ty systémy, kde jsou uzly propojeny napříč vrstvami, je koncept centrálnosti lépe chápán z hlediska univerzálnosti. Uzly, které nejsou centrální v každé vrstvě, mohou být v určitých scénářích nejdůležitější pro vícevrstvé systémy. Jedná se například o případ, kdy dvě vrstvy kódují různé sítě s jediným společným uzlem: je velmi pravděpodobné, že takový uzel bude mít nejvyšší skóre centrálnosti, protože je zodpovědný za tok informací napříč vrstvami.

Univerzálnost vlastních vektorů

Pokud jde o neidimenzionální sítě, univerzálnost vlastních vektorů může být definována jako řešení problému vlastních čísel dané pomocí , kde je pro zjednodušení použita Einsteinova konvence součtu . Zde poskytuje vícevrstvé zobecnění centrálnosti Bonacichova vlastního vektoru na uzel a vrstvu. Celková univerzálnost vlastních vektorů se jednoduše získá součtem skóre napříč vrstvami jako . ${\ Displaystyle M_ {j \ beta}^{i \ alpha} \ Theta _ {i \ alpha} = \ lambda _ {1} \ Theta _ {j \ beta}}$${\ Displaystyle \ Theta _ {j \ beta} = \ lambda _ {1}^{-1} M_ {j \ beta}^{i \ alpha} \ Theta _ {i \ alpha}}$${\ Displaystyle \ theta _ {i} = \ Theta _ {i \ alpha} u^{\ alpha}}$

Univerzálnost Katz

Pokud jde o jeho jednorozměrné protějšek se Katz univerzálnost se získá jako roztok v tenzorovostí rovnice , kde , je konstanta menší než největší vlastní hodnoty a je další konstantní obecně roven 1. Celková Katz Všestrannost jednoduše získá sečtením skóre napříč vrstvami jako . ${\ Displaystyle \ Phi _ {j \ beta} = [(\ delta -aM)^{ -1}] _ {j \ beta}^{i \ alpha} U_ {i \ alpha}}$${\ displaystyle \ Phi _ {j \ beta} = aM_ {j \ beta}^{i \ alpha} \ Phi _ {i \ alpha}+bu_ {j \ beta}}$${\ Displaystyle \ delta _ {j \ beta}^{i \ alpha} = \ delta _ {j}^{i} \ delta _ {\ beta}^{\ alpha}}$${\ displaystyle a}$${\ displaystyle b}$${\ Displaystyle \ phi _ {i} = \ Phi _ {i \ alpha} u^{\ alpha}}$

HITS univerzálnost

Pro neidimenzionální sítě původně algoritmus HITS zavedl Jon Kleinberg pro hodnocení webových stránek. Základním předpokladem algoritmu je, že relevantní stránky, pojmenované autority, jsou označeny speciálními webovými stránkami, pojmenovanými rozbočovači. Tento mechanismus lze matematicky popsat dvěma spojenými rovnicemi, které redukují na dva problémy vlastních čísel. Když je síť neorientovaná, autorita a centralita centra jsou ekvivalentní centrálnosti vlastních vektorů. Tyto vlastnosti jsou zachovány přirozeným rozšířením rovnic navržených Kleinbergem pro případ propojených vícevrstvých sítí, daných a , kde označuje transponovaný operátor, a indikují centrálnost centra a autority. Smluvou mezi tenzory rozbočovače a autority získáte celkovou univerzálnost jako a v daném pořadí. ${\ Displaystyle (MM^{t}) _ {j \ beta}^{i \ alpha} \ Gamma _ {i \ alpha} = \ lambda _ {1} \ Gamma _ {j \ beta}}$${\ Displaystyle (M^{t} M) _ {j \ beta}^{i \ alpha} \ Upsilon _ {i \ alpha} = \ lambda _ {1} \ Upsilon _ {j \ beta}}$${\ displaystyle t}$${\ displaystyle \ Gamma _ {i \ alpha}}$${\ Displaystyle \ Upsilon _ {i \ alpha}}$${\ Displaystyle \ gamma _ {i} = \ Gamma _ {i \ alpha} u^{\ alpha}}$${\ Displaystyle \ upsilon _ {i} = \ Upsilon _ {i \ alpha} u^{\ alpha}}$

Univerzálnost hodnocení PageRank

PageRank , lépe známý jako Google Search Algorithm, je dalším měřítkem centrálnosti ve složitých sítích, původně zavedeným za účelem hodnocení webových stránek. Jeho rozšíření na případ propojených vícevrstvých sítí lze získat následujícím způsobem.

Nejprve je třeba poznamenat, že PageRank lze považovat za ustálené řešení speciálního Markovova procesu v horní části sítě. Náhodní chodci zkoumají síť podle speciální přechodové matice a jejich dynamika se řídí hlavní rovnicí náhodných procházek . Je snadné ukázat, že řešení této rovnice je ekvivalentní počátečnímu vlastnímu vektoru přechodové matice.

Náhodné procházky byly definovány také v případě propojených vícevrstvých sítí a vícebarevných barev (také známých jako multiplexní sítě). U propojených vícevrstvých sítí je tenzor přechodu řídící dynamiku náhodných chodců uvnitř a napříč vrstvami dán vztahem , kde je konstanta, obecně nastavená na 0,85, je počet uzlů a je počet vrstev nebo rozměrů. Zde se může jmenovat tenzor Google a je tenzorem stupně 4 se všemi komponentami rovnými 1. ${\ Displaystyle R_ {j \ beta}^{i \ alpha} = rT_ {j \ beta}^{i \ alpha}+{\ frac {(1-r)} {NL}} u_ {j \ beta}^ {i \ alpha},}$${\ displaystyle r}$${\ displaystyle N}$${\ displaystyle L}$${\ displaystyle R_ {j \ beta}^{i \ alpha}}$${\ displaystyle u_ {j \ beta}^{i \ alpha}}$

Univerzálnost PageRank se jako neidimenzionální protějšek skládá ze dvou příspěvků: jednoho kódujícího klasickou náhodnou chůzi s rychlostí a jednoho kódujícího teleportace přes uzly a vrstvy s rychlostí . ${\ displaystyle r}$${\ Displaystyle 1-r}$

Kdybychom vyznačí na eigentensor části tenzoru Google , označující v ustáleném stavu pravděpodobnost najít chodítko v uzlu a vrstvě vícevrstvý PageRank se získá sečtením přes vrstvy na eigentensor:${\ displaystyle \ Omega _ {i \ alpha}}$${\ displaystyle R_ {j \ beta}^{i \ alpha}}$${\ displaystyle i}$${\ displaystyle \ alpha}$${\ displaystyle \ omega _ {i} = \ Omega _ {i \ alpha} u^{\ alpha}}$

Triadické uzavírací a klastrové koeficienty

Stejně jako mnoho jiných statistik sítě se význam klastrovacího koeficientu stává nejednoznačným ve vícerozměrných sítích, protože trojky mohou být uzavřeny v jiných dimenzích, než vznikaly. Bylo učiněno několik pokusů definovat lokální klastrové koeficienty, ale tyto pokusy zdůraznily skutečnost, že koncept musí být ve vyšších dimenzích zásadně odlišný: některé skupiny vycházely z nestandardních definic, zatímco jiné experimentovaly s různými definicemi náhodné procházky a 3 cykly ve vícerozměrných sítích.

Komunitní objev

Přestože byly napříč studovány cross-dimenzionální struktury, nedokáží detekovat jemnější asociace nalezené v některých sítích. Trochu jiný pohled na definici „komunity“ v případě vícerozměrných sítí umožňuje spolehlivou identifikaci komunit bez požadavku, aby byly uzly v přímém kontaktu mezi sebou. Například dva lidé, kteří nikdy nekomunikují přímo, ale přesto prohlížejí mnoho stejných webových stránek, by byli životaschopnými kandidáty pro tento druh algoritmu.

Maximalizace modularity

Zobecnění dobře známé metody maximalizace modularity pro objevování komunity původně navrhli Mucha et al. Tato metoda multiresolution předpokládá trojrozměrnou tenzorovou reprezentaci síťové konektivity uvnitř vrstev, jako u multigrafů s okrajovou barvou, a trojrozměrnou tenzovou reprezentaci síťové konektivity napříč vrstvami. Záleží na parametru rozlišení a hmotnosti mezivrstevných připojení. V kompaktnějším notaci, využitím tenzorovostí notaci, modularita může být psáno jako tam, kde , je vícevrstvá sousednost tenzor, je tenzor kódující model null a hodnotu složky je definována jako 1, když uzel ve vrstvě patří do určité komunity, označené indexem , a 0, pokud ne. ${\ displaystyle \ gamma}$${\ displaystyle \ omega}$${\ Displaystyle Q \ propto S_ {i \ alpha}^{a} B_ {j \ beta}^{i \ alpha} S_ {a}^{j \ beta}}$${\ Displaystyle B_ {j \ beta}^{i \ alpha} = M_ {j \ beta}^{i \ alpha} -P_ {j \ beta}^{i \ alpha}}$${\ displaystyle M_ {j \ beta}^{i \ alpha}}$${\ displaystyle P_ {j \ beta}^{i \ alpha}}$${\ displaystyle S_ {a}^{i \ alpha}}$${\ displaystyle i}$${\ displaystyle \ alpha}$${\ displaystyle a}$

Rozklad tenzoru

Byla navržena nezáporná maticová faktorizace k extrakci struktury komunitních aktivit dočasných sítí. Vícevrstvá síť je reprezentována trojrozměrným tenzorem , jako hranatý barevný multigraf, kde pořadí vrstev kóduje šipku času. Tensorová faktorizace pomocí Kruskalova rozkladu se tedy používá k přiřazení každého uzlu ke komunitě v průběhu času. ${\ displaystyle T_ {ij}^{\ tau}}$${\ displaystyle T_ {ij}^{\ tau}}$

Statistické závěry

Byly navrženy metody založené na statistické inferenci, zobecňující stávající přístupy zavedené pro neidimenzionální sítě. Stochastický blokový model je nejpoužívanějším generativním modelem, vhodně zobecněným pro případ vícevrstvých sítí.

Pro neidimenzionální sítě lze pro výběr modelu v metodách detekce komunity na základě toku informací použít principiální metody, jako je minimální délka popisu .

Strukturální redukovatelnost

Vzhledem k vyšší složitosti vícevrstvých sítí s ohledem na jednodimenzionální sítě je aktivní oblast výzkumu věnována zjednodušení struktury těchto systémů využitím nějakého druhu redukce rozměrů.

Oblíbená metoda je založena na výpočtu kvantové Jensen-Shannonovy divergence mezi všemi páry vrstev, která je následně využívána pro své metrické vlastnosti k vytvoření matice vzdáleností a hierarchického seskupování vrstev. Vrstvy se postupně agregují podle výsledného hierarchického stromu a agregační postup se zastaví, když objektivní funkce založená na entropii sítě získá globální maximum. Tento chamtivý přístup je nezbytný, protože základní problém by vyžadoval ověření všech možných skupin vrstev jakékoli velikosti, vyžadujících obrovské množství možných kombinací (což je dáno Bellovým číslem a superexponenciálně se stupňuje s počtem jednotek). Nicméně u vícevrstvých systémů s malým počtem vrstev se ukázalo, že metoda ve většině případů funguje optimálně.

Jiné vícevrstvé deskriptory sítě

Korelace stupňů

Otázka korelací stupňů v unidimenzionálních sítích je poměrně přímočará: mají sítě podobného stupně tendenci se navzájem propojovat? Ve vícerozměrných sítích se stává méně jasné, co tato otázka znamená. Když mluvíme o stupni uzlu, odkazujeme na jeho stupeň v jedné dimenzi, nebo se zhroutil přes všechny? Když se snažíme prozkoumat konektivitu mezi uzly, porovnáváme stejné uzly napříč dimenzemi nebo různé uzly v dimenzích nebo kombinaci? Jaké jsou důsledky odchylek v každé z těchto statistik na jiné vlastnosti sítě? V jedné studii bylo zjištěno, že asortativita snižuje robustnost v duplexní síti.

Dominance cesty

Vzhledem ke dvěma vícerozměrným cestám, r a s , říkáme, že r dominuje s tehdy a jen tehdy: a tak . ${\ Displaystyle \ forall d \ in \ langle 1, | D | \ rangle, r_ {l} \ leq s_ {l}}$${\ displaystyle \ existuje i}$${\ displaystyle r_ {l} <s_ {l}}$

Objev nejkratší cesty

Mezi jinými statistikami sítě závisí mnoho opatření centrálnosti na schopnosti posoudit nejkratší cesty z uzlu do uzlu. Rozšíření těchto analýz na vícerozměrnou síť vyžaduje začlenění dalších spojení mezi uzly do aktuálně používaných algoritmů (např. Dijkstra ). Aktuální přístupy zahrnují sbalení vícelinkových spojení mezi uzly v kroku předzpracování před provedením variací v širokém prvním hledání sítě.

Vícerozměrná vzdálenost

Jedním ze způsobů, jak posoudit vzdálenost mezi dvěma uzly ve vícerozměrné síti, je porovnat všechny vícerozměrné cesty mezi nimi a zvolit podmnožinu, kterou definujeme jako nejkratší prostřednictvím dominance cesty: budiž množina všech cest mezi a . Pak je vzdálenost mezi a je sada cest tak, že taková, že dominuje . Délka prvků v sadě nejkratších cest mezi dvěma uzly je proto definována jako vícerozměrná vzdálenost . ${\ Displaystyle MP (u, v)}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle P \ subseteq MP}$${\ Displaystyle \ forall p \ in P, \ nexists p '\ in MP}$${\ displaystyle p '}$${\ displaystyle p}$

Relevance dimenze

V multidimenzionální sítě , význam daného rozměru (nebo sadu rozměry) pro jeden uzel může být hodnocena jako poměr: . ${\ displaystyle G = (V, E, D)}$${\ displaystyle D '}$${\ displaystyle {\ frac {{\ text {Neighbors}} (v, D ')} {{\ text {Neighbors}} (v, D)}}}$

Rozměrová konektivita

Ve vícerozměrné síti, ve které mají různé dimenze spojení různé hodnoty v reálném světě, jsou zajímavé statistiky charakterizující distribuci odkazů do různých tříd. Je tedy užitečné vzít v úvahu dvě metriky, které to hodnotí: dimenzionální konektivita a hraniční exkluzivní dimenzionální konektivita. První z nich je prostě poměr celkového počtu článků v daném rozměru k celkovému počtu článků v každé dimenzi: . Posledně jmenované posuzuje, pro daný rozměr, počet páry uzlů připojit pouze odkaz v tomto rozměru: . ${\ Displaystyle {\ frac {| \ {(u, v, d) \ in E | u, v \ in V \} |} {| E |}}}$${\ Displaystyle {\ frac {| \ {(u, v, d) \ in E | u, v \ in V \ wedge \ forall j \ in D, j \ neq d: (u, v, j) \ notin E \} |} {| \ {(u, v, d) \ v E | u, v \ v V \} |}}}$

Detekce prasknutí

Burstiness je známý jev v mnoha sítích reálného světa, např. V e-mailech nebo jiných lidských komunikačních sítích. Další dimenze komunikace poskytují věrnější zobrazení reality a mohou tyto vzorce zvýraznit nebo zmenšit. Proto je zásadní, aby naše metody pro detekci nárazového chování v sítích vyhovovaly vícerozměrným sítím.

Difúzní procesy ve vícevrstvých sítích

Ilustrace náhodné procházky na vrcholu speciálního vícevrstvého systému, tj. Multiplexní sítě

Difúzní procesy jsou široce používány ve fyzice k prozkoumání fyzikálních systémů, stejně jako v dalších oborech, jako jsou sociální vědy, neurovědy, městská a mezinárodní doprava nebo finance. V poslední době byly na vícevrstvé sítě zobecněny jednoduché a složitější difúzní procesy. Jedním z výsledků společných mnoha studiím je, že difúze v multiplexních sítích, což je speciální typ vícevrstvého systému, vykazuje dva režimy: 1) hmotnost mezivrstevných vazeb, které navzájem spojují vrstvy, není dostatečně vysoká a multiplexní systém se chová jako dva (nebo více) odpojených sítí; 2) hmotnost mezivrstevných odkazů je dostatečně vysoká, aby se vrstvy navzájem spojily, což vyvolává neočekávané fyzikální jevy. Ukázalo se, že mezi těmito dvěma režimy dochází k náhlému přechodu.

Ve skutečnosti jsou všechny deskriptory sítě závislé na nějakém difuzivním procesu, od opatření centrálnosti až po detekci komunity, ovlivněny vazbou mezi vrstvou a vrstvou. Například v případě detekce komunity nízká vazba (kde informace z každé vrstvy zvlášť je relevantnější než celková struktura) zvýhodňuje shluky uvnitř vrstev, zatímco vysoká vazba (kde informace ze všech vrstev současně je relevantnější než každá vrstva samostatně ) upřednostňuje shluky mezi vrstvami.

Proces difúzní reakce na vícevrstvém systému studovali Lazaridis et al. Zjistilo se, že pro proces, kde A a B jsou zpočátku v různých vrstvách, dále difundují náhodně a když se setkají, oba zmizí. Bylo zjištěno, že v tomto modelu, v důsledku reakce, jakési odpuzování mezi A a B, které zpomaluje jejich míchání a tedy i jejich reakci. ${\ displaystyle A+B \ rightarrow 0}$

Náhodné procházky

Pokud jde o neidimenzionální sítě, je možné definovat náhodné procházky na vrcholu vícevrstvých systémů. Vzhledem k základní vícevrstvé struktuře se však náhodní chodci neomezují na pohyb z jednoho uzlu do druhého ve stejné vrstvě ( skok ), ale mohou se také pohybovat přes vrstvy ( přepínat ).

Náhodné procházky lze použít k prozkoumání vícevrstvého systému s konečným cílem rozplést jeho mezoskálovou organizaci , tj. Rozdělit jej v komunitách , a v poslední době byly použity k lepšímu porozumění navigovatelnosti vícevrstvých sítí a jejich odolnosti vůči náhodným selháním, jakož i pro efektivně zkoumat tento typ topologií.

V případě propojených vícevrstvých systémů lze pravděpodobnost přesunu z uzlu ve vrstvě do uzlu ve vrstvě zakódovat do tenzoru přechodu stupně 4 a procházení diskrétním časem lze popsat hlavní rovnicí ${\ displaystyle i}$${\ displaystyle \ alpha}$${\ displaystyle j}$${\ displaystyle \ beta}$${\ displaystyle T_ {j \ beta}^{i \ alpha}}$

${\ Displaystyle p_ {j \ beta} (t+1) = \ sum _ {\ alpha = 1}^{L} \ sum _ {i = 1}^{N} T_ {j \ beta}^{i \ alfa} p_ {i \ alpha} (t) = \ sum _ {\ alpha = 1}^{L} \ sum _ {i = 1}^{N} (T^{t}) _ {j \ beta} ^{i \ alpha} p_ {i \ alpha} (0)}$

kde udává pravděpodobnost nalezení chodce v uzlu ve vrstvě v čase . ${\ displaystyle p_ {i \ alpha} (t)}$${\ displaystyle i}$${\ displaystyle \ alpha}$${\ displaystyle t}$

Existuje mnoho různých typů procházek, které lze zakódovat do tenzoru přechodu , v závislosti na tom, jak mohou chodci skákat a přepínat. Chodec například může buď skočit, nebo přepnout v jednom časovém kroku bez rozlišení mezi mezivrstevnými a mezivrstvovými vazbami ( klasická náhodná procházka ), nebo se může rozhodnout buď zůstat v aktuální vrstvě a skočit, nebo přepnout vrstvu a poté přeskočte na jiný uzel ve stejném časovém kroku ( fyzická náhodná procházka ). Složitější pravidla, odpovídající konkrétním problémům k řešení, lze nalézt v literatuře. V některých případech je možné analyticky najít stacionární řešení hlavní rovnice. ${\ displaystyle T_ {j \ beta}^{i \ alpha}}$

Klasická difúze

Problém klasické difúze ve složitých sítích je pochopit, jak množství protéká systémem a kolik času bude potřeba k dosažení stacionárního stavu. Klasická difúze v multiplexních sítích byla nedávno studována zavedením konceptu supra-sousední matice , později uznávané jako speciální zploštění vícevrstvého tenzoru sousednosti. V tenzorové notaci lze difúzní rovnici na vrcholu obecného vícevrstvého systému napsat stručně jako

${\ Displaystyle {\ frac {dX_ {j \ beta} (t)} {dt}} =-L_ {j \ beta}^{i \ alpha} X_ {i \ alpha} (t)}$

kde je množství difuzního množství v čase v uzlu ve vrstvě . Tensor hodnosti 4, který řídí rovnici, je laplaciánský tenzor, zobecňující kombinatorickou laplaciánskou matici unidimenzionálních sítí. Stojí za zmínku, že v non-tenzorové notaci má rovnice složitější formu. ${\ Displaystyle X_ {i \ alpha} (t)}$${\ displaystyle t}$${\ displaystyle i}$${\ displaystyle \ alpha}$

Mnoho vlastností tohoto difuzního procesu je zcela chápáno ve smyslu druhé nejmenší vlastní hodnoty laplaciánského tenzoru. Je zajímavé, že difúze v multiplexním systému může být rychlejší než difúze v každé vrstvě samostatně nebo při jejich agregaci za předpokladu, že jsou splněny určité spektrální vlastnosti.

Šíří se informace a epidemie

V poslední době je předmětem intenzivního výzkumu, jak se informace (nebo nemoci) šíří vícevrstvým systémem.

Perkolace vícevrstvých vzájemně závislých sítí

Buldyrev a kol. vyvinul rámec pro studium perkolace ve vícevrstvých sítích se závislými vazbami mezi vrstvami. Byly nalezeny nové fyzikální jevy, včetně náhlých přechodů a kaskádových selhání. Když jsou sítě vloženy do prostoru, stanou se extrémně zranitelnými i pro velmi malý zlomek odkazů závislostí a pro lokalizované útoky na nulovou část uzlů. Když je zavedena obnova uzlů, je nalezen bohatý fázový diagram, který zahrnuje vícekritické body, hysterezi a metastabilní režimy.

Vzájemná závislost na komunitách

Vícevrstvé vzájemně závislé sítě (viz obrázek) byly studovány také za přítomnosti komunit v různých sítích. Prostorová společenství ve vícerozměrných vzájemně závislých sítích viz Vaknin et al.

Zkoumáme dvě možné konfigurace sítě sítí. (a) Stromová síť sítí s plnou vazbou a obousměrnými závislými odkazy a (b) smyčková síť sítí se zlomkem závislých uzlů, q a jednosměrných závislých vazeb. V obou (a) a (b) jsou odkazy závislosti omezeny tak, že spojují pouze uzly ve stejných komunitách, tj. Uzel v modulu ma v síti i bude záviset na uzlu také v modulu ma v síti j. c) Demonstrace závislosti mezi dvojicí vzájemně závislých sítí uvedených v písmenech a) ab). Závislost je mezi stejnými komunitami v různých sítích (stejné barvy).

Dynamická vzájemná závislost ve vícevrstvých sítích

Na základě vícevrstvých sítí byl vyvinut přístup dynamické závislosti představující vzájemnou závislost dynamických systémů, jako je synchronizace a šíření. Studie zjistila jevy, jako jsou sdružené kolektivní jevy, včetně multistability, hystereze, oblastí soužití a makroskopického chaosu.

Software

• muxViz , bezplatný a účinný rámec pro analýzu a vizualizaci vícevrstvých sítí, založený na R [1]
• Knihovna vícevrstvých sítí pro Python (Pymnet) od Mikka Kivelä
• MAMMULT Metrics a modely pro sítě vícevrstvé (sbírka C / Pythonu)
• GenLouvain MATLAB kód pro detekci komunity na základě maximalizace vícevrstvé modularity
• Knihovna Multinet R a C ++ pro analýzu vícevrstvých sítí.

Reference

externí odkazy