Flerdimensionellt nätverk

I nätverksteori är flerdimensionella nätverk , en speciell typ av flerskiktsnätverk, nätverk med flera typer av relationer. Allt mer sofistikerade försök att modellera verkliga system som multidimensionella nätverk har gett värdefull insikt inom områdena sociala nätverksanalys , ekonomi, urbana och internationella transporter , ekologi , psykologi, medicin, biologi, handel, klimatologi, fysik, beräkningsneurovetenskap , driftledning och finans.

Terminologi

snabba utforskning av komplexa nätverk har förföljts av en brist på standardiserade namnkonventioner, eftersom olika grupper använder överlappande och motsägelsefull terminologi för att beskriva specifika nätverkskonfigurationer (t.ex. multiplex, flerskikts, flernivå, multidimensionell, multirelationell, sammankopplad). För att till fullo utnyttja datauppsättningsinformationen om kommunikationens riktningsbeskaffenhet, överväger vissa författare endast direkta nätverk utan några etiketter på hörn, och introducerar definitionen av kantmärkta multigrafer som kan täcka många flerdimensionella situationer. Termen "helt flerdimensionell" har också använts för att hänvisa till en multi-partite kantmärkt multigraf. Flerdimensionella nätverk har också nyligen ändrats till specifika instanser av flerskiktsnätverk. I det här fallet finns det lika många lager som det finns dimensioner, och länkarna mellan noder inom varje lager är helt enkelt alla länkar för en given dimension.

Definition

Oviktade flerskiktsnätverk

I elementär nätverksteori representeras ett nätverk av en graf $G=(V,E)$ där $V$ är uppsättningen av noder och $E$ länkarna mellan noder, typiskt representerade som en tuppel av noder $v\in V}$ , . Även om denna grundläggande formalisering är användbar för att analysera många system, har verkliga nätverk ofta ökad komplexitet i form av flera typer av relationer mellan systemelement. En tidig formalisering av denna idé kom genom dess tillämpning inom området för sociala nätverksanalyser (se t.ex. och artiklar om relationella algebror i sociala nätverk) där flera former av social koppling mellan människor representerades av flera typer av länkar.

För att tillgodose närvaron av mer än en typ av länk representeras ett flerdimensionellt nätverk av en trippel $G=(V,E,D)$ , där $D$ är en uppsättning dimensioner (eller lager), där varje medlem är en annan typ av länk, och $E$ består av trippel $(u,v,d)$ med $u,v\in V$ och $d\in D$ .

Observera att som i alla riktade grafer är länkarna $(u,v,d)$ och $(v,u,d)$ distinkta.

Enligt konvention är antalet länkar mellan två noder i en given dimension antingen 0 eller 1 i ett flerdimensionellt nätverk. Det totala antalet länkar mellan två noder över alla dimensioner är dock mindre än eller lika med $|D|$ .

Viktade flerskiktsnätverk

I fallet med ett viktat nätverk utökas denna triplett till en kvadruplett ${\displaystyle e=(u,v,d,w)} ,$ där $w$ är vikten på länken mellan $u$ och $v$ i dimensionen $d$ .

Multiplexnätverket av europeiska flygplatser. Varje flygbolag betecknar ett annat lager. Visualisering gjord med mjukvaran muxViz

Vidare, som ofta är användbart i sociala nätverksanalyser, kan länkvikter anta positiva eller negativa värden. Sådana undertecknade nätverk kan bättre återspegla relationer som vänskap och fiendskap i sociala nätverk. Alternativt kan länktecken anges som själva dimensionerna, t.ex. $G=(V,E,D)$ där $D=\ {-1,0,1\}$ och $E=\{(u,v,d);u,v\in V,d\in D\}$ Detta tillvägagångssätt har särskilt värde när man överväger oviktade nätverk.

Denna uppfattning om dimensionalitet kan utökas om attribut i flera dimensioner behöver specifikation. I det här fallet är länkarna n -tupler $e=(u,v,d_{1}\dots d_{n-2})$ . En sådan utökad formulering, där länkar kan finnas inom flera dimensioner, är ovanlig men har använts i studien av flerdimensionella tidsvarierande nätverk .

World Economic Forums karta över globala risker och globala trender, modellerad som ett ömsesidigt beroende nätverk (även känt som nätverk av nätverk).

Allmän formulering i termer av tensorer

Medan endimensionella nätverk har tvådimensionella angränsande matriser av storleken ${\displaystyle V\times V},$ i ett flerdimensionellt nätverk med $D$ -dimensioner, blir angränsande matris en flerlagers angränsande tensor, en fyrdimensionell matris av storlek $(V\times D)\times (V\times D)$ . Genom att använda indexnotation kan närliggande matriser indikeras med ${\displaystyle A_{j}^{i}} ,$ för att koda kopplingar mellan noderna $i$ och $j$ , medan flerskiktiga angränsande tensorer indikeras av $M_{j\beta }^{i\alpha }$ , för att koda förbindelser mellan nod $i$ i lager $\alpha$ och nod ${\ displaystyle j}$ i lager $\beta$ . Precis som i endimensionella matriser, är riktade länkar, signerade länkar och vikter lätt anpassade till detta ramverk.

I fallet med multiplexnätverk , som är speciella typer av flerskiktsnätverk där noder inte kan kopplas samman med andra noder i andra lager, en tredimensionell matris av storlek ( $\displaystyle (V\x V) \times D}$ med poster $A_{ij}^{\alpha }$ räcker för att representera systemets struktur genom att koda kopplingar mellan noderna $i$ och $j$ i lager $\alpha$ .

Star Wars-sagans multiplexa sociala nätverk. Varje lager betecknar en annan episod och två noder är sammankopplade med varandra om motsvarande karaktärer agerade tillsammans i en eller flera scener. Visualisering gjord med muxViz programvara

Flerdimensionella nätverksspecifika definitioner

Flera lager grannar

I ett flerdimensionellt nätverk är grannarna till någon nod $v$ alla noder kopplade till $v$ över dimensioner.

Banlängd i flera lager

En väg mellan två noder i ett flerdimensionellt nätverk kan representeras av en vektor r $=(r_{1},\dots r_{|D|})$ där ${\displaystyle i}:$ e posten i r är antalet länkar som korsas i den ${\displaystyle i}:$ e dimensionen av $G$ . Som med överlappande grad kan summan av dessa element tas som ett grovt mått på en väglängd mellan två noder.

Nätverk av lager

Förekomsten av flera lager (eller dimensioner) gör det möjligt att introducera det nya konceptet med nätverk av lager , speciellt med flerlagersnätverk. Faktum är att lager kan vara sammankopplade på ett sådant sätt att deras struktur kan beskrivas av ett nätverk, som visas i figuren.

Nätverk av lager i flerlagersystem

Nätverket av lager är vanligtvis viktat (och kan vara riktat), även om vikterna i allmänhet beror på tillämpningen av intresse. Ett enkelt tillvägagångssätt är att, för varje par av lager, summera alla vikter i kopplingarna mellan deras noder för att erhålla kantvikter som kan kodas in i en matris $q_{\alpha \beta }$ . Rank-2 angränsande tensor, som representerar det underliggande nätverket av lager i rymden $\mathbb {R} ^{L\ gånger L}$ ges av

$\Psi _{\delta }^{\gamma }=\summa \limits _{\alpha ,\beta =1 }^{L}q_{\alpha \beta }E_{\delta }^{\gamma }(\alpha \beta )$

där $E_{\delta }^{\gamma }(\alpha \beta )$ är den kanoniska matrisen med alla komponenter lika med noll förutom posten som motsvarar rad $\ alpha$ och kolumn ${\displaystyle \beta } ,$ som är lika med en. Genom att använda tensorialnotationen är det möjligt att erhålla det (viktade) nätverket av lager från flerlagers angränsande tensor som $\Psi _{\delta }^{\gamma } =M_{j\delta }^{i\gamma }U_{i}^{j}$ .

Centralitetsåtgärder

Grad

I ett icke sammankopplat flerdimensionellt nätverk, där mellanskiktslänkar saknas, representeras graden av en nod av en vektor med längd $|D|:\mathbf {k} =(k_{i}^{1},\dots k_{i}^{|D|} )$ . Här $|D|$ är ett alternativt sätt att beteckna antalet lager $L$ i flerskiktsnätverk. För vissa beräkningar kan det dock vara mer användbart att helt enkelt summera antalet länkar intill en nod över alla dimensioner. Detta är den överlappande graden : $\sum _{\alpha =1}^{|D|}k_{i}^{\alpha }$ . Liksom med endimensionella nätverk kan skillnad på liknande sätt göras mellan inkommande länkar och utgående länkar. Om mellanskiktslänkar finns måste definitionen ovan anpassas för att ta hänsyn till dem, och flerskiktsgraden ges av

$k^{i}=M_{j\beta }^{i\ alpha }U_{\alpha }^{\beta}u^{j}=\summa _{\alpha ,\beta =1}^{L}\summa _{j=1}^{N}M_{j\ beta }^{i\alpha }$

där tensorerna $U_{\alpha }^{\beta }$ och $u^{j}$ har alla komponenter lika med 1. Heterogeniteten i antalet anslutningar av en nod över de olika skikten kan beaktas genom deltagandekoefficienten.

Mångsidighet som centralitet i flera lager

När det utvidgas till sammankopplade flerskiktsnätverk, dvs de system där noder är anslutna över skikt, förstås begreppet centralitet bättre i termer av mångsidighet. Noder som inte är centrala i varje lager kan vara de viktigaste för flerskiktssystemen i vissa scenarier. Till exempel är detta fallet när två lager kodar olika nätverk med endast en nod gemensam: det är mycket troligt att en sådan nod kommer att ha den högsta centralitetspoängen eftersom den är ansvarig för informationsflödet över lagren.

Egenvektors mångsidighet

När det gäller endimensionella nätverk kan egenvektors mångsidighet definieras som lösningen av egenvärdesproblemet som ges av ${\displaystyle M_{j\beta }^{i\alpha }\Theta _{i\alpha }=\lambda _{1}\Theta _{j\beta }} ,$ där Einsteins summeringskonvention används för enkelhetens skull. Här är $\Theta _{j\beta }=\lambda _{1}^{-1}M_{j\beta }^{i \alpha }\Theta _{i\alpha }$ ger flerskiktsgeneraliseringen av Bonacichs egenvektorcentralitet per nod och lager. Den övergripande egenvektorns mångsidighet erhålls helt enkelt genom att summera poängen över skikten som $\theta _{i}=\Theta _{i\alpha }u^{\alpha }$ .

Katz mångsidighet

När det gäller dess endimensionella motsvarighet erhålls Katz mångsidighet som lösningen $\Phi _{j\beta }=[(\ delta -aM)^{-1}]_{j\beta }^{i\alpha }U_{i\alpha }$ av tensorialekvationen ${\displaystyle \Phi _{j\beta }=aM_{j\beta }^{i\alpha }\Phi _{i\alpha }+bu_{j\beta }} ,$ där ${\displaystyle \delta _{j\beta }^{i\alpha }=\delta _{j}^{i}\delta _{\beta }^{\alpha }} ,$ en $\ displaystyle a}$ är en konstant mindre än det största egenvärdet och $b$ är en annan konstant som vanligtvis är lika med 1. Den övergripande Katz mångsidigheten erhålls helt enkelt genom att summera poängen över skikten som ${ \displaystyle \phi _{i}=\Phi _{i\alpha }u^{\alpha }}$ .

HITS mångsidighet

För endimensionella nätverk har HITS-algoritmen ursprungligen introducerats av Jon Kleinberg för att betygsätta webbsidor. Algoritmens grundantagande är att relevanta sidor, namngivna auktoriteter, pekas av speciella webbsidor, namngivna nav. Denna mekanism kan matematiskt beskrivas av två kopplade ekvationer som reducerar till två egenvärdesproblem. När nätverket är oriktat är auktoritets- och navcentralitet ekvivalenta med egenvektorcentralitet. Dessa egenskaper bevaras av den naturliga utvidgningen av de ekvationer som Kleinberg föreslagit till fallet med sammankopplade flerskiktsnätverk, givet av $(MM^{t) })_{j\beta }^{i\alpha }\Gamma _{i\alpha }=\lambda _{1}\Gamma _{j\beta }$ och $(M^{t}M)_{j\beta }^{i\alpha }\Upsilon _{i\alpha }=\lambda _{1}\Upsilon _{j \beta }$ , där $t$ indikerar transponeringsoperatorn, $\Gamma _{i\alpha }$ och $\Upsilon _{i\alpha }$ indikerar nav respektive myndighetscentralitet. Genom att kontrahera navet och auktoritetstensorerna får man de övergripande mångsidigheten som $\gamma _{i}=\Gamma _{i\alpha }u^{\alpha }$ och $\upsilon _{i}=\Upsilon _{i\alpha }u^{\alpha }$ .

PageRank mångsidighet

PageRank , mer känd som Google Search Algorithm är ett annat mått på centralitet i komplexa nätverk, som ursprungligen introducerades för att rangordna webbsidor. Dess utvidgning till fallet med sammankopplade flerskiktsnätverk kan erhållas enligt följande.

För det första är det värt att notera att PageRank kan ses som steady-state-lösningen för en speciell Markov-process på toppen av nätverket. Random walkers utforskar nätverket enligt en speciell övergångsmatris och deras dynamik styrs av en random walk master-ekvation . Det är lätt att visa att lösningen av denna ekvation är ekvivalent med den ledande egenvektorn för övergångsmatrisen.

Slumpmässiga vandringar har definierats även i fallet med sammankopplade flerskiktsnätverk och kantfärgade multigrafer (även kända som multiplexnätverk). För sammankopplade flerskiktsnätverk ges den övergångstensor som styr dynamiken hos de slumpmässiga vandrare inom och över skikten av ${\ displaystyle R_{j\beta }^{i\alpha }=rT_{j\beta }^{i\alpha }+{\frac {(1-r)}{NL}}u_{j\beta }^{i \alpha },}$ , där $r$ är en konstant, vanligtvis satt till 0,85, $N$ är antalet noder och $L$ är antalet lager eller dimensioner. Här $R_{j\beta }^{i\alpha }$ heta Google-tensor och $u_{j\beta }^{i\alpha }$ är rank-4 tensor med alla komponenter lika med 1.

Som sin endimensionella motsvarighet består PageRank-mångsidigheten av två bidrag: ett som kodar en klassisk slumpmässig promenad med hastighet $r$ och en kodar teleportering över noder och lager med hastighet $1-r$ .

Om vi ​​anger med $\Omega _{i\alpha }$ egentensorn för Google-tensorn ${\displaystyle R_{j\beta }^{i\alpha }} ,$ vilket betecknar den konstanta -ange sannolikhet för att hitta rullatorn i nod $i$ och lager $\alpha$ , flerskikts PageRank erhålls genom att summera över lager egentensorn: $\ omega _{i}=\Omega _{i\alpha }u^{\alpha }$

Triadisk stängning och klustringskoefficienter

Ytterligare information: Triadisk stängning

Liksom många annan nätverksstatistik blir innebörden av en klustringskoefficient tvetydig i flerdimensionella nätverk, på grund av det faktum att trippel kan stängas i andra dimensioner än de uppstod. Flera försök har gjorts för att definiera lokala klustringskoefficienter, men dessa försök har belyst det faktum att konceptet måste vara fundamentalt annorlunda i högre dimensioner: vissa grupper har baserat sitt arbete på icke-standardiserade definitioner, medan andra har experimenterat med olika definitioner av slumpmässiga promenader och 3-cykler i flerdimensionella nätverk.

Gemenskapsupptäckt

Även om tvärdimensionella strukturer har studerats tidigare, misslyckas de med att upptäcka mer subtila associationer som finns i vissa nätverk. Att ta en något annorlunda uppfattning om definitionen av "gemenskap" i fallet med flerdimensionella nätverk möjliggör tillförlitlig identifiering av gemenskaper utan krav på att noder är i direkt kontakt med varandra. Till exempel skulle två personer som aldrig kommunicerar direkt men ändå surfar på många av samma webbplatser vara livskraftiga kandidater för denna typ av algoritm.

Modularitetsmaximering

En generalisering av den välkända modularitetsmaximeringsmetoden för gemenskapsupptäckt har ursprungligen föreslagits av Mucha et al. Denna multiupplösningsmetod förutsätter en tredimensionell tensorrepresentation av nätverksanslutningen inom lager, som för kantfärgade multigrafer, och en tredimensionell tensorrepresentation av nätverksanslutningen över lager. Det beror på upplösningsparametern $\gamma$ och vikten $\omega$ för mellanskiktsanslutningar. I en mer kompakt notation, med användning av tensorial notation, kan modularitet skrivas som $Q\propto S_{i\alpha }^{a}B_ {j\beta }^{i\alpha }S_{a}^{j\beta }$ , där ${\displaystyle B_{j\beta } ^{i\alpha }=M_{j\beta }^{i\alpha }-P_{j\beta }^{i\alpha }} , M j β i α {\displaystyle M_$ { ${ i\alpha }}$ är den flerskiktiga adjacency-tensorn, $P_{j\beta }^{i\alpha }$ är tensorn som kodar nollmodellen och värdet på komponenterna i ${ \displaystyle S_{a}^{i\alpha }}$ definieras som 1 när en nod $i$ i lager $\alpha$ tillhör en viss gemenskap, märkt med index $a$ , och 0 när det inte gör det.

Tensornedbrytning

Icke-negativ matrisfaktorisering har föreslagits för att extrahera gemenskapsaktivitetsstrukturen för temporala nätverk. Flerskiktsnätverket representeras av en tredimensionell tensor ${\displaystyle T_{ij}^{\tau }},$ som en kantfärgad multigraf, där lagrens ordning kodar för tidens pil. Tensorfaktorisering med hjälp av Kruskal-nedbrytning tillämpas alltså på $T_{ij}^{\tau }$ för att tilldela varje nod till en gemenskap över tiden.

Statistisk slutsats

Metoder baserade på statistisk slutledning, som generaliserar befintliga tillvägagångssätt införda för endimensionella nätverk, har föreslagits. Stokastisk blockmodell är den mest använda generativa modellen, lämpligt generaliserad till fallet med flerskiktsnätverk.

När det gäller endimensionella nätverk kan principiella metoder som minsta beskrivningslängd användas för modellval i gemenskapsdetekteringsmetoder baserade på informationsflöde.

Strukturell reducerbarhet

Med tanke på den högre komplexiteten hos flerskiktsnätverk med avseende på endimensionella nätverk, ägnas ett aktivt forskningsfält åt att förenkla strukturen hos sådana system genom att använda någon form av dimensionsreduktion.

En populär metod är baserad på beräkningen av Jensen-Shannon-kvantdivergensen mellan alla par av lager, som sedan utnyttjas för sina metriska egenskaper för att bygga en avståndsmatris och hierarkiskt gruppera lagren. Lager aggregeras successivt enligt det resulterande hierarkiska trädet och aggregeringsproceduren stoppas när objektivfunktionen, baserat på nätverkets entropi , får ett globalt maximum. Detta giriga tillvägagångssätt är nödvändigt eftersom det underliggande problemet skulle kräva att alla möjliga lagergrupper av vilken storlek som helst måste verifieras, vilket kräver ett stort antal möjliga kombinationer (vilket ges av Bell-numret och skalas superexponentiellt med antalet enheter). För flerskiktssystem med ett litet antal lager har det dock visat sig att metoden fungerar optimalt i de flesta fall.

Andra flerskiktsnätverksbeskrivningar

Gradkorrelationer

Frågan om gradkorrelationer i endimensionella nätverk är ganska okomplicerad: tenderar nätverk av liknande grad att ansluta till varandra? I flerdimensionella nätverk blir vad denna fråga betyder mindre tydlig. När vi hänvisar till en nods grad, hänvisar vi till dess grad i en dimension, eller kollapsade över allt? När vi försöker undersöka anslutningar mellan noder, jämför vi samma noder över dimensioner, eller olika noder inom dimensioner, eller en kombination? Vilka är konsekvenserna av variationer i var och en av denna statistik på andra nätverksfastigheter? I en studie visade sig assortativitet minska robustheten i ett duplexnätverk.

Vägdominans

Givet två flerdimensionella banor, r och s , säger vi att r dominerar s om och endast om: ${\displaystyle \forall d\in \langle 1,|D|\rangle ,r_{l}\leq s_{l}} och ∃ i {\$ displaystyle $i}$ så att $r_{l}<s_{l}$ .

Kortaste vägen upptäckt

Bland annan nätverksstatistik är många centralitetsmått beroende av förmågan att bedöma kortaste vägarna från nod till nod. Att utöka dessa analyser till ett flerdimensionellt nätverk kräver att ytterligare anslutningar mellan noder införlivas i de algoritmer som för närvarande används (t.ex. Dijkstras ) . Nuvarande tillvägagångssätt inkluderar att kollapsa flerlänksanslutningar mellan noder i ett förbearbetningssteg innan variationer utförs på en bredd-första sökning av nätverket.

Flerdimensionellt avstånd

$\displaystyle MP(u, v)}$ två noder i ett flerdimensionellt nätverk är genom att jämföra alla flerdimensionella vägar mellan dem och välja den delmängd som vi definierar som kortast via vägdominans: låt MP ( vara uppsättningen av alla vägar mellan $u$ och $v$ . Då $\displaystyle \forall p\in P,\nfinns p'\in MP}$ avståndet mellan $u$ och $v$ en uppsättning banor $P\subseteq MP$ så att så att $p'$ dominerar $p$ . Längden på elementen i uppsättningen av kortaste vägar mellan två noder definieras därför som det flerdimensionella avståndet .

Dimensionsrelevans

I ett flerdimensionellt nätverk $G=(V,E,D)$ , relevansen av en given dimension (eller uppsättning dimensioner) $D'$ för en nod kan bedömas utifrån förhållandet: ${\frac {{\text{Granar}}(v,D')}{{\text{Granar}}( v,D)}}$ .

Dimensionsanslutning

I ett flerdimensionellt nätverk där olika dimensioner av samband har olika verkliga värden, är statistik som kännetecknar fördelningen av länkar till de olika klasserna av intresse. Det är därför användbart att överväga två mått som bedömer detta: dimensionsanslutning och kantexklusiv dimensionsanslutbarhet. Det förra är helt enkelt förhållandet mellan det totala antalet länkar i en given dimension och det totala antalet länkar i varje dimension: ${\frac {|\{(u,v,d)\in E|u,v\in V\}|}{|E|}}$ . Den senare bedömer, för en given dimension, antalet par av noder som endast är sammankopplade med en länk i den dimensionen: ${\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)\in E|u,v\in V\}|}}$ .

Burstdetektering

Burstiness är ett välkänt fenomen i många verkliga nätverk, t.ex. e-post eller andra mänskliga kommunikationsnätverk. Ytterligare dimensioner av kommunikation ger en mer trogen återgivning av verkligheten och kan lyfta fram dessa mönster eller minska dem. Därför är det av avgörande betydelse att våra metoder för att upptäcka bursty beteende i nätverk rymmer flerdimensionella nätverk.

Diffusionsprocesser på flerskiktsnätverk

Illustration av en slumpmässig promenad på toppen av ett speciellt flerskiktssystem, dvs ett multiplexnätverk

Diffusionsprocesser används i stor utsträckning inom fysiken för att utforska fysiska system, såväl som inom andra discipliner som samhällsvetenskap, neurovetenskap, urban och internationell transport eller finans. Nyligen har enkla och mer komplexa diffusiva processer generaliserats till flerskiktsnätverk. Ett resultat som är gemensamt för många studier är att diffusion i multiplexnätverk, en speciell typ av flerskiktssystem, uppvisar två regimer: 1) vikten av mellanskiktslänkar, som förbinder skikt med varandra, inte är tillräckligt hög och multiplexsystemet beter sig som två (eller fler) frikopplade nätverk; 2) vikten av länkar mellan skikten är tillräckligt hög för att skikten kopplas ihop, vilket ger upphov till oväntade fysiska fenomen. Det har visat sig att det sker en abrupt övergång mellan dessa två regimer.

Faktum är att alla nätverksbeskrivningar som är beroende av någon diffusiv process, från centralitetsåtgärder till gemenskapsdetektering, påverkas av lager-lager-kopplingen. Till exempel, i fallet med gemenskapsdetektering, gynnar låg koppling (där information från varje lager separat är mer relevant än den övergripande strukturen) kluster inom lager, medan hög koppling (där information från alla lager samtidigt är mer relevant än varje lager separat) ) gynnar tvärskiktskluster.

Slumpmässiga promenader

När det gäller endimensionella nätverk är det möjligt att definiera slumpmässiga vandringar på toppen av flerskiktssystem. Men med tanke på den underliggande flerskiktsstrukturen är slumpmässiga vandrare inte begränsade till att flytta från en nod till en annan inom samma lager ( hopp ), utan tillåts också att röra sig över lager ( växel ).

Random walks kan användas för att utforska ett flerskiktssystem med det slutliga målet att nysta upp dess mesoskaliga organisation , dvs. att dela upp det i gemenskaper , och har nyligen använts för att bättre förstå navigerbarheten hos flerskiktsnätverk och deras motståndskraft mot slumpmässiga fel, såväl som för effektivt utforska denna typ av topologier.

I fallet med sammankopplade flerskiktssystem kan sannolikheten att flytta från en nod $i$ i lager $\alpha$ till nod $j$ i lager $\beta$ kodas in i rank-4 övergångstensorn $T_{j\beta }^{i\alpha }$ och den diskreta tidsvandringen kan beskrivas med masterekvationen

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

där $p_{i\alpha }(t)$ indikerar sannolikheten att hitta rullatorn i nod $i$ i lager $\alpha$ vid tidpunkten $t$ .

Det finns många olika typer av promenader som kan kodas in i övergångstensorn ${\displaystyle T_{j\beta }^{i\alpha }} ,$ beroende på hur vandrare får hoppa och byta. Till exempel kan vandraren antingen hoppa eller byta i ett enda tidssteg utan att skilja mellan mellan- och intralagerlänkar ( klassisk slumpmässig gång ), eller så kan den välja att antingen stanna i det aktuella lagret och hoppa, eller att byta lager och hoppa sedan till en annan nod i samma tidssteg ( physical random walk ). Mer komplicerade regler, motsvarande specifika problem att lösa, finns i litteraturen. I vissa fall är det möjligt att analytiskt hitta den stationära lösningen av masterekvationen.

Klassisk diffusion

Problemet med klassisk diffusion i komplexa nätverk är att förstå hur en kvantitet kommer att flöda genom systemet och hur lång tid det tar att nå det stationära tillståndet. Klassisk diffusion i multiplexnätverk har nyligen studerats genom att introducera begreppet supra-adjacency-matris, som senare erkändes som en speciell utjämning av multilayer-adjacency-tensorn. I tensorial notation kan diffusionsekvationen på toppen av ett allmänt flerskiktssystem skrivas kortfattat som

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

där $X_{i\alpha }(t)$ är mängden spridande kvantitet vid tidpunkten $t$ i nod $i$ i lager $\alpha$ . Rang-4-tensorn som styr ekvationen är den laplaciska tensoren, som generaliserar den kombinatoriska laplaciska matrisen av endimensionella nätverk. Det är värt att notera att i icke-tensorial notation tar ekvationen en mer komplicerad form.

Många av egenskaperna hos denna diffusionsprocess är fullständigt förstådda i termer av det näst minsta egenvärdet för den laplaciska tensorn. Det är intressant att diffusion i ett multiplexsystem kan vara snabbare än diffusion i varje lager separat, eller i deras aggregering, förutsatt att vissa spektrala egenskaper är uppfyllda.

Information och epidemier sprider sig

Se även: epidemiologi

Hur information (eller sjukdomar) sprids genom ett flerskiktssystem har nyligen varit föremål för intensiv forskning.