Prírodou inšpirované algoritmy

Jin, Girvan, and Newman Model II

Emily M. Jin, Michelle Girvan, a M. E. J. Newman navrhli jednoduchý model rozširujúcej sa sociálnej siete založenej na troch princípoch:

• stretnutie medzi dvomi jedincami je tým pravdepodobnejšie, čím majú títo dvaja viac spoločných priateľov; inak je nepravdepodobné,

• pravdepodobnosť zoznámenia sa takého páru jedincov, ktorí sa stretávajú zriedka s časom klesá a

• existuje horný limit priateľstiev, ktoré môže jeden jedinec udržiavať.

Použitím počítačovej simulácie našli model, ktorý obsahuje všetky tieto črty a napodobňuje mnohé črty reálnych sociálnych sietí zahŕňajúc vysokoúrovňové zoskupovanie a silnú spoločenskú štrukturovanosť, v ktorej má jedinec podstatne viac kontaktov s ostatnými v jeho komunite ako s jedincami s iných komunít. V nasledujúcom dokumente je tento model aj matematicky popísaný:

growth-social-network.pdf (228kB)
growth-social-network.pdf.gz (197kB)

Výsledok simulácie je zobrazený na prvom obrázku. Počas simulácie sa vytvorili tri izolované skupiny, ktoré sa už ďalej nespojili. Aj v rámci najväčšej skupiny možno sledovať lokálne zhluky vrcholov, ktoré sú navzájom veľmi husto poprepájané, a so zvyškom skupiny sú spojené iba niekoľkými málo linkami. Jednou z možností ako ohodnotiť sociálnu štruktúru reprezentovanú grafom na obrázku je použiť silu spojenia medzi dvomi vrcholmi, ktorá je váženou sumou počtu rozličných ciest v sieti medzi dvomi vrcholmi, pričom kratšia cesta má vyššiu váhu ako dlhšia.

Spomínaní autori sa rozhodli model zjednodušiť, pretože obsahoval nelineárne závislosti a zložité parametre. Váhy jednotlivých spojení dvoch vrcholov v novom modeli nie sú vážené, len "existujú" alebo "neexistujú". Vytvorili nové pravidlá vytvárania vzťahov založené na náhodnom a kvazináhodnom stretávaní sa jedincov. Na začiatku v sieti neexistujú žiadne spojenia a sieť sa inicializuje umelým vytvorením príbuznosti (červené linky) a náhodnými "stretnutiami" jedincov (zelené linky); existujúce linky sa neodstraňujú (používajú sa iba dve z troch pravidiel) až kým všetci jedinci nedosiahnú maximálny počet "priateľstiev". Keď sa tak stane, začnú sa uplatňovať všetky tri pravidlá (linky sa pridávajú aj odstraňujú) a postupne červené linky úplne vymiznú a vzťahy sa nahradia novými. Priebeh demonštruje nasledujúca trojica obrázkov:

Tri fázy simulácie:
Prvá je sieť na začiatku, bez akýchkoľvek spojení vrcholov; v strede môžeme sledovať počiatočné tvorenie spojení, kedy sa ešte existujúce spojenia neodstraňujú; v posledný je výsledok simulácie - počiatočne generované sú takmer úplne nahradené novými. Kliknutím na ktorýkoľvek obrázok sa zobrazí animácia.

Domovská stránka JIN, GIRVAN, and NEWMAN MODEL II