Hierarkisk nätverksmodell

Hierarkiska nätverksmodeller är iterativa algoritmer för att skapa nätverk som kan reproducera de unika egenskaperna hos den skalfria topologin och den höga klustringen av noderna på samma gång. Dessa egenskaper är allmänt observerade i naturen, från biologi till språk till vissa sociala nätverk .

Begrepp

Den hierarkiska nätverksmodellen är en del av den skalfria modellfamiljen som delar sin huvudsakliga egenskap att ha proportionellt fler nav bland noderna än genom slumpmässig generering; den skiljer sig dock väsentligt från de andra liknande modellerna ( Barabási–Albert , Watts–Strogatz ) i fördelningen av nodernas klusteringskoefficienter: eftersom andra modeller skulle förutsäga en konstant klusteringskoefficient som funktion av nodens grad , i hierarkisk form. modellnoder med fler länkar förväntas ha en lägre klustringskoefficient. Dessutom, medan Barabási-Albert-modellen förutsäger en minskande genomsnittlig klusteringskoefficient när antalet noder ökar, finns det i fallet med de hierarkiska modellerna inget samband mellan storleken på nätverket och dess genomsnittliga klustringskoefficient.

Utvecklingen av hierarkiska nätverksmodeller motiverades huvudsakligen av att de andra skalfria modellerna misslyckades med att införliva den skalfria topologin och höga klustringen i en enda modell. Eftersom flera verkliga nätverk ( metaboliska nätverk , proteininteraktionsnätverket , World Wide Web eller några sociala nätverk ) uppvisar sådana egenskaper , introducerades olika hierarkiska topologier för att ta hänsyn till dessa olika egenskaper.

Algoritm

Hierarkiska nätverksmodeller härleds vanligtvis på ett iterativt sätt genom att replikera det initiala klustret av nätverket enligt en viss regel. Betrakta till exempel ett initialt nätverk av fem helt sammankopplade noder (N=5). Som ett nästa steg, skapa fyra repliker av detta kluster och anslut de perifera noderna för varje replik till den centrala noden av det ursprungliga klustret (N=25). Detta steg kan upprepas i oändlighet, varigenom för alla k steg kan antalet noder i systemet härledas av N=5k +1 .

Naturligtvis har det funnits flera olika sätt att skapa hierarkiska system som föreslagits i litteraturen. Dessa system skiljer sig i allmänhet i strukturen av det initiala klustret såväl som i graden av expansion som ofta kallas modellens replikeringsfaktor .

Exempel på en hierarkisk nätverksstruktur.

Egenskaper

Examensfördelning

Som en del av den skalfria modellfamiljen följer gradfördelningen av den hierarkiska nätverksmodellen kraftlagen vilket innebär att en slumpmässigt vald nod i nätverket har k kanter med en sannolikhet

där c är en konstant och γ är gradexponenten. I de flesta verkliga nätverk som uppvisar skalfria egenskaper γ i intervallet [2,3].

Som ett specifikt resultat för hierarkiska modeller har det visat sig att gradexponenten för fördelningsfunktionen kan beräknas som

där M representerar modellens replikationsfaktor.

Klusteringskoefficient

Till skillnad från de andra skalfria modellerna ( Erdős–Rényi , Barabási–Albert, Watts–Strogatz) där klustringskoefficienten är oberoende av graden av en specifik nod, kan klusteringskoefficienten i hierarkiska nätverk uttryckas som en funktion av examen på följande sätt:

Det har analytiskt visat sig att i deterministiska skalfria nätverk tar exponenten β värdet 1.

Exempel

Skådespelare nätverk

Baserat på skådespelaredatabasen som finns tillgänglig på www.IMDB.com definieras nätverket av Hollywood- skådespelare som är anslutna till varandra om de båda medverkade i samma film, vilket resulterar i en datamängd på 392 340 noder och 15 347 957 kanter. Som tidigare studier har visat uppvisar detta nätverk skalfria egenskaper åtminstone för höga värden på k . Dessutom verkar klustringskoefficienterna följa den erforderliga skalningslagen med parametern -1 som ger bevis för nätverkets hierarkiska topologi. Intuitivt har enframträdande skådespelare per definition en klusteringskoefficient på en medan skådespelare som spelar i flera filmer är högst osannolikt att arbeta med samma besättning, vilket i allmänhet resulterar i en minskande klusteringskoefficient när antalet medskådespelare växer.

Språknätverk

Ord kan betraktas som nätverk om man specificerar kopplingskriterierna mellan dem. Genom att definiera länkar som utseende som en synonym i Merriam-Webster- ordboken konstruerades en semantisk väv av 182 853 noder med 317 658 kanter. Som det visade sig, följer det erhållna nätverket av ord verkligen en maktlag i sin gradfördelning medan fördelningen av klustringskoefficienten indikerar att den underliggande webben följer en hierarkisk struktur med γ =3,25 och β =1.

Nätverk av webbsidor

Genom att kartlägga www.nd.edu-domänen erhölls ett nätverk av 325 729 noder och 1 497 135 kanter vars gradfördelning följde en kraftlag med γ ut =2,45 och γ in =2,1 för ut- respektive in-graderna. Bevisen för skalningslagsfördelningen av klustringskoefficienterna är betydligt svagare än i de tidigare fallen även om det finns ett tydligt avtagande mönster i fördelningen av C(k) som indikerar att ju fler länkar en domän har desto mindre sammankopplad är den länkade/länkningen webbsidor är.

Domännätverk

Domännätverket , dvs internet på den autonoma systemnivån (AS) där de administrativa domänerna sägs vara anslutna ifall det finns en router som kopplar dem, visade sig omfatta 65 520 noder och 24 412 länkar mellan dem och uppvisa egenskaperna hos ett skalfritt nätverk. Sampelfördelningen av klustringskoefficienterna anpassades av skalningsfunktionen C(k)~k −0,75 vars exponent är (i absoluta termer) något mindre än den teoretiska parametern för deterministiska skalfria nätverk.