Wattsin ja Strogatzin satunnaisverkkomallin klusteroituneisuus

Abstract

Duncan J. Watts ja Steven H. Strogatz määrittivät vuonna 1998 verkon klusterointikertoimen, joka on yleisesti käytetty tilastollinen mitta verkon klusteroituneisuuden analysointiin. Esimerkiksi sosiaalisen verkoston henkilöiden tuttavapiireillä on taipumus klusteroitua siten, että monet henkilön tuttavista ovat myös keskenään tuttavia. Verkon klusterointikerroin laskee keskiarvoisen murtoluvun henkilön tuttavapareista, jotka ovat myös keskenään tuttavia. Alain Barrat ja Martin Weigt sekä Mark E. J. Newman, Duncan J. Watts ja Steven H. Strogatz määrittävät verkon transitiivisuuskertoimen vaihtoehtoisena klusterointikertoimena. Sosiaalisessa verkostossa se laskee millä todennäköisyydellä kaksi henkilöä, jotka ovat saman henkilön tuttavia ovat myös keskenään tuttavia. Satunnaisverkkomalleja on pitkään käytetty isojen monimutkaisten verkostojen analysointiin. Klusterointikertoimen käyttöönotosta alkaen on ollut mahdollista osoittaa tilastollisesti, että monet sosiaaliset verkostot sekä ihmisten tekemät verkostot ovat pieni maailma -verkkoja. Esimerkiksi Facebook ja Internet ovat pieni maailma -verkkoja, eli harvoja ja hyvin klusteroituneita verkkoja, joissa verkon solmuparien keskimääräinen etäisyys on lyhyt. On osoittautunut, että pieni maailma -verkkorakennetta ei ole mahdollista mallintaa perinteisillä satunnaisverkoilla tai säännöllisillä hiloilla. D. J. Watts ja S. H. Strogatz esittivät vuonna 1998 uuden satunnaisverkkomallin, jolla on mahdollista generoida pieni maailma -verkkoja. Mallillaan he tutkivat muun muassa epidemian leviämistä sekä signaalin etenemisnopeutta pieni maailma -verkoissa. Tämän tutkielman tarkoitus on laskea matemaattiset lausekkeet Wattsin ja Strogatzin verkkomallin satunnaisverkon klusterointikertoimelle ja transitiivisuuskertoimelle. Tutkielmassa määritellään matemaattisesti verkon tilastolliset klusterointi- ja transitiivisuuskertoimien eri muodot sekä esitetään lauseita niiden yhteyksistä ja eroista. Lisäksi määritellään satunnaisverkon klusterointi- ja transitiivisuuskerroin matemaattisesti tarkkaan sekä esitetään kaavoja näiden laskemiseen. Wattsin ja Strogatzin verkkomallin satunnaisverkolle lasketaan solmuparien kytkentätodennäköisyydet, joiden avulla lasketaan matemaattiset lausekkeet verkkomallin satunnaisverkon klusterointi- ja transitiivisuuskertoimelle.