Suppenemislaki satunnaisverkoille
Nyström, Mikael (2020)
2020
Matematiikan maisteriohjelma - Master´s Programme in Mathematics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2020-05-25
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202005155383
https://urn.fi/URN:NBN:fi:tuni-202005155383
Tiivistelmä
Tässä tutkielmassa todistetaan, että satunnaisesti muodostetun verkon kasvaessa rajatta voidaan aina löytää raja-arvo todennäköisyydelle, että verkkoa koskeva ensimmäisen kertaluvun logiikan väittämä pitää paikkansa. Tätä varten tehdään joitakin tarpeellisia satunnaisverkon astejonoa koskevia oletuksia. Tutkielma perustuu James F. Lynchin artikkelissaan Convergence Law for Random Graphs With Specified Degree Sequence tekemään tutkimukseen.
Tullaan huomaamaan, että raja-arvon olemassaoloa koskevan väitteen todistuksessa ei tarvitse perehtyä satunnaisten skaalautumattomien verkkojen tutkimiseen, mikä olisi vaivalloista. Sen sijaan näytetään, että riittää tarkastella helpommin satunnaisesti muodostettavaa rakennetta, jota kutsutaan kokoonpanoksi. Samalla perehdytään verkkojen ominaisuuksia kuvaaviin rakenteisiin, kuten puihin, metsiin sekä ympäristöihin.
Verkkojen ominaisuuksien vertailemiseen käytetään Ehrenfeuchtin peliä, joka esitellään pinnallisesti. Tämän ohella suuri osa todistuksesta pohjautuu verkkojen kombinatoriseen tarkasteluun samaistamalla verkkojen käyttäytyminen niin kutsuttuihin haarautumisprosesseihin. Lisäksi esitellään tarvittavia todennäköisyyslaskennan ja kombinatoriikan tuloksia, jotka helpottavat päälauseen todistamista.
Tullaan huomaamaan, että raja-arvon olemassaoloa koskevan väitteen todistuksessa ei tarvitse perehtyä satunnaisten skaalautumattomien verkkojen tutkimiseen, mikä olisi vaivalloista. Sen sijaan näytetään, että riittää tarkastella helpommin satunnaisesti muodostettavaa rakennetta, jota kutsutaan kokoonpanoksi. Samalla perehdytään verkkojen ominaisuuksia kuvaaviin rakenteisiin, kuten puihin, metsiin sekä ympäristöihin.
Verkkojen ominaisuuksien vertailemiseen käytetään Ehrenfeuchtin peliä, joka esitellään pinnallisesti. Tämän ohella suuri osa todistuksesta pohjautuu verkkojen kombinatoriseen tarkasteluun samaistamalla verkkojen käyttäytyminen niin kutsuttuihin haarautumisprosesseihin. Lisäksi esitellään tarvittavia todennäköisyyslaskennan ja kombinatoriikan tuloksia, jotka helpottavat päälauseen todistamista.