1267. sredin seminar: M. Cugmas: Generiranje omrežij z izbrano globalno strukturo z uporabo lokalnih podstruktur

Glede na empirične podatke in različna teoretična izhodišča, so raziskovalci definirali različne tipične globalnih struktur omrežij, na primer model 'ballance' (Cartwright in Harary 1956), model 'clustering' (Davis 1967) in model 'transitivity' (Holland i Leinhardt 1971). Davis in Leinhardt (1967) sta predstavila klasifikacijo vseh možnih tipov grafov velikosti tri in v okviru slednje je nastal seznam prepovedanih in dovoljenih tipov trikotnikov za omenjene globalne strukture. Davis in Leinhardt (1970) sta ugovarjala, da je zaradi možnosti prisotnosti napak v omrežju potreben manj deterministični pristop k ugotavljanju globalnih struktur. Tako sta, na podlagi porazdelitev trikotnikov v slučajih omrežjih, zasnovala teste za preverjanje domnev o številu prepovedanih in dovoljenih tipov trikotnikov v empiričnih omrežjih.

Na tokratnem Sredinem seminarju bomo globalno strukturo omrežij definirali z različnimi tipi bločnih modelov (koheziven, tranzitiven, center-periferija, hierarhičen), poleg različnih tipov trikotnikov pa bomo preučevali tudi nekaj drugih lokalnih značilnosti omrežij. Pokazali bomo, katere statistike, povezane z lokalnimi značilnostmi omrežij so enake 0 v primeru omrežij brez napak in nadalje, kako različni deleži napak v omrežju vplivajo na te statistike. Glede na slednje bomo izbrali tiste lokalne značilnosti omrežij, ki jih je potrebno upoštevati pri generiranju slučajnih omrežij, da bi dobili določeno globalno strukturo omrežja. V okviru tega bomo predstavili dva načina simuliranja omrežij z določeno globalno strukturo: bolj determinističen iterativni postopek s prestavljanjem povezav in, v okviru Exponential Random Graph Modeling (ERGM), manj deterministični Monte Carlo Multi Chain algoritem.

Zgolj na podlagi informacije o prepovedanih tipih trikotnikov (ob predpostavljeni fiksni gostoti) je mogoče generirati skoraj popolna omrežja z različnimi globalnimi strukturami, kar pa ne velja za hierarhični model z več skupinami, kjer so potrebne dodatne omejitve.