Randomizace zachovávající stupeň - Degree-preserving randomization

Síťová věda
Teorie
Graf Komplexní síť Nákaza Malý svět Bez vodního kamene Struktura Společenství Perkolace Vývoj Ovladatelnost Kreslení grafu Sociální kapital Analýza odkazů Optimalizace Vzájemnost Uzavření Homofilie 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ý neurální Vzájemně závislé Sémantický Prostorový Závislost Tok na čipu
Grafy
Funkce Klika Součástka Střih Cyklus Datová struktura Okraj Smyčka Sousedství Cesta Vrchol Seznam sousedů  / matice Seznam případů  / matice Typy Bipartitní Kompletní Režie Hyper Multi Náhodný Vážený
Metriky Algoritmy
Centrálnost Stupeň Mezi Blízkost PageRank Motiv Shlukování Rozdělení stupňů 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é geometrické (RGG) Hyperbolický (HGN) Hierarchický Stochastický blok Maximální entropie Měkká konfigurace Referenční hodnota LFR Dynamika Booleovská síť agent Epidemický /VÁŽENÝ PANE
Seznamy Kategorie
Témata Software Síťoví vědci Kategorie: Teorie sítí Kategorie: Teorie grafů

Randomizace pro uchování titulu je technika používaná v Síťová věda který si klade za cíl posoudit, zda by variace pozorované v daném grafu mohly být v pozorované síti jednoduše artefaktem inherentních strukturálních vlastností grafu, spíše než vlastnostmi jedinečnými pro uzly.

Pozadí

Katalogizováno již v roce 1996,^[1] nejjednodušší implementace randomizace zachovávající stupeň spoléhá na a Monte Carlo algoritmus, který náhodně přeuspořádává nebo „přepojuje“ síť tak, že při dostatečném počtu přepojení je distribuce stupně sítě identická s počátečním rozdělením sítě, ačkoli topologická struktura sítě se zcela odlišuje od původní síť.

Demonstrace jediné iterace algoritmu Randomizace pro uchování titulu.

Randomizace pro uchování titulu, i když má mnoho různých forem, má obvykle podobu relativně jednoduchého přístupu: pro jakoukoli síť skládající se z ${ displaystyle N}$ uzly s ${ displaystyle E}$ okraje, vyberte dva dyadicky vázané uzly. U každého z těchto dvojic dvojic přepněte okraje tak, aby se nové dvojice dvojic neodpovídaly. Po dostatečném počtu těchto nesouladů síť stále více ztrácí svou původní pozorovanou topografii.

Jak je běžné u algoritmů založených na Markovovy řetězy, počet iterací nebo jednotlivých drátů, které se musí na daném grafu vyskytnout tak, aby byl graf dostatečně náhodný a odlišný od původního grafu, není znám, ačkoli Espinoza^[2] tvrdí, že bezpečná minimální prahová hodnota je ${ displaystyle Q * E}$, kde ${ displaystyle Q}$ „je nejméně 100“ (Espinoza). Jiní poskytli informace k tomuto číslu, včetně jednoho autora, který uvádí, že bezpečné minimum může být místo toho alespoň ${ displaystyle { frac {E} {2}} * ln (1 / epsilon)}$kde epsilon leží v rozmezí mezi ${ displaystyle 10 ^ {- 6}}$ a ${ displaystyle 10 ^ {- 7}}$, ačkoli správné číslo v současné době není známo.^[3][4]

Použití

Existuje několik případů, kdy publikovaný výzkum výslovně použil stupeň zachování randomizace za účelem analýzy vlastností sítě. Dekker^[5] použité přepojení za účelem přesnějšího modelování pozorovaných sociálních sítí přidáním sekundární proměnné, ${ displaystyle pi}$, který zavádí zaujatost na vysoké úrovni. Liu a kol.^[6] dále použili stupeň zachování randomizace, aby tvrdili, že Centrální kontrola, metrika, kterou identifikují, se ve srovnání s Control Centrality an Erdős – Rényiho model obsahující stejný počet ${ displaystyle N}$ uzly v jejich simulacích - Liu et al. také využili randomizační modely zachovávající stupeň při následném zkoumání práce ovladatelnost v síti.^[7]

Dále byla provedena určitá práce při zkoumání toho, jak lze randomizaci při uchování titulu použít při řešení úvah o anonymitě ve výzkumu síťových dat, což se ukázalo jako důvod k obavám v Analýza sociálních sítí, jako v případě studie Lewis et al.^[8][9] Nakonec práce provedená Yingem a Wu, počínaje základem Randomizace uchování titulu a poté předáním několika modifikací, ukázala mírný pokrok v ochraně anonymity, aniž by byla ohrožena integrita základní užitečnosti sledované sítě.^[10]

Metoda je navíc svou povahou podobná široce používané Exponenciální modely náhodných grafů popularizovaný ve společenských vědách,^[11][12] a skutečně různé formy modelování sítí proti pozorovaným sítím, aby bylo možné identifikovat a teoretizovat rozdíly vyjádřené ve skutečných sítích. Důležité je, že randomizace uchování titulu poskytuje jednoduchý algoritmický návrh pro ty, kteří jsou obeznámeni s programováním, aby použili model na dostupnou pozorovanou síť.

Příklad

Následuje malý příklad, který ukazuje, jak lze aplikovat randomizaci na uchování titulu na pozorovanou síť ve snaze porozumět síti proti jinak náhodným změnám při zachování aspektu distribuce stupňů v síti. The Asociace internetových výzkumníků má Listserv která tvoří většinu diskusních vláken obklopujících jejich práci. Na něm členové zveřejňují informace o svém vlastním výzkumu, nadcházejících konferencích, výzvách k předložení příspěvků a také se navzájem zapojují do věcných diskusí ve svém oboru. Tyto e-maily mohou zase tvořit cílený a dočasný síťový graf, kde uzly jsou jednotlivé e-mailové účty patřící do Listservu a okraje jsou případy, kdy jedna e-mailová adresa odpovídá na jinou e-mailovou adresu v Listservu.

Výsledky randomizačních pokusů o zachování stupně.

V této pozorované síti jsou vlastnosti Listservu relativně snadné vypočítat - pro síť 3 235 jednotlivých e-mailových účtů a celkem 9 824 burz pozorované vzájemnost sítě je přibližně 0,074 a [Průměrná délka cesty | průměrná délka cesty] je přibližně 4,46. Lze k těmto hodnotám dospět jednoduše prostřednictvím povahy vlastní struktury sítě?

Uplatnění ${ displaystyle { frac {E} {2}} * ln (1 / epsilon)}$ pravidlo, tato síť by vyžadovala přibližně 67 861 jednotlivých okrajových drátů, aby se vytvořil pravděpodobně dostatečně náhodný graf se zachováním stupně. Pokud zkonstruujeme mnoho náhodných grafů zachovávajících stupeň ze skutečného grafu, můžeme vytvořit prostor pravděpodobnosti pro charakteristiky, jako je reciprocita a průměrná délka dráhy, a posoudit míru, do jaké mohla síť tyto charakteristiky náhodně vyjádřit. 534 sítí bylo vygenerováno pomocí randomizace uchování titulu. Protože reciprocita i průměrná délka cesty v tomto grafu jsou normálně distribuovány a protože standardní odchylka pro reciprocitu i průměrnou délku cesty jsou příliš úzké, aby zahrnovaly pozorovaný případ, můžeme rozumně předpokládat, že tato síť vyjadřuje charakteristiky, které nejsou náhodné (a tedy otevřené pro další teorii a modelování).

Reference

externí odkazy

• Například poskytnuta datová sada