Tipikus távolságok a Newman-Watts kis világ modellen exponenciális élsúlyokkal

Tipikus távolságok a Newman-Watts kis világ modellen exponenciális élsúlyokkal

Vadon Viktória, MSc 1. évfolyam

Konzulens: Dr. Komjáthy Júlia, Stochastic Section, Eindhoven University of Technology

Manapság hálózatokkal vagyunk körülvéve, a közlekedési, biológiai, elektromos és szociális hálók az életünk részét képezik. Ezért hát természetes, hogy a tudósok, mint informatikusok, fizikusok, biológusok és matematikusok figyelmet fordítanak rájuk. A hálózatok struktúráját és a rajtuk végbemenő különböző folyamatokat is vizsgálják. Modellek, szimulációk és számítások készülnek, hogy meghatározzák például mennyi ideig tart, míg az információ eljut a hálózat egyik pontjából a másikba, milyen gyorsan fertőződik meg a teljes populáció egy vírus terjedése esetén, és "mennyit kaphat" az egyik, vagyis a verseny végén mekkore részét birtokolja a csúcsoknak, ha két folyamat terjed versengve a gráfon.

Ezen dolgozatban a Newman-Watts kis világ modellel dolgozunk, melyet független azonos eloszlású exponenciális élsúlyokkal látunk el. Ez az egyik legrégibb hálózatokat modellező véletlen gráf, ami egyben - egyszerű - geometriával is rendelkezik. A modellt a következőképpen konstruáljuk: veszünk egy kört n csúcson, majd egy adott r>0 valós konstansra minden más lehetséges élet egymástól fügetlenül r/n valószínűséggel adunk a gráfhoz. Ha az élek már adottak, független azonos eloszlású Exp(1) élsúlyokat rendelünk hozzájuk. Ezen a gráfon a legrövidebb utak által meghatározott metrikát tekintjük: a két csúcs közti összes lehetséges útra minimalizáljuk az út mentén található élek összsúlyát. A kérdés, mi két egyenletesen választott csúcs távolsága ebben a véletlen metrikus térben? Hány lépést kell tennünk ezen a legrövidebb úton? Az úgynevezett first passage percolation módszerét használjuk a válasz megtalálására.

Először a csúcs lokális környezetét jellemezzük, megfigyeljük a legrövidebb utak alkotta fát, majd definiálunk egy ennek megfelelő folytonos idejű, többtípusos elágazó folyamatot. Megmutatjuk, hogy a két csúcstól vett legrövidebb utak fái közt végbemenő csatlakozás inhomogén Poisson pontfolyamatot alkot, amelyben a ténylegesen csatlakozó pontot geometriailag jellemezhetjük. Ezekból az informciókból kiszámolhatjuk a legrövidebb út eloszlását. A fő eredményünk, hogy bizonyítjuk, a tipikus távolság log n nagyságrendű, a kisebb tagok pedig kifejezhetők az elágazó folyamatot, illetve az exponenciális eloszlást jellemző konstansokkal és valószínűségi változókkal. A lépések számára a legrövidebb út mentén, az úgynevezett hopcount-ra centrális határeloszlástételt bizonyítunk, ahol a várható érték és szórásnégyzet log n-nek konstans többszörösei. Származtatjuk az úgynevezett epidemic curve-öt is, ami a fertőzött egyedek aránya az összeshez képest az idő függvényeként, azon vírusterjedési modellben, ahol az egyedek először fogékonyak, majd fertőzöttek (és fertőzők).

szerző

• 
  Vadon Viktória
  alkalmazott matematikus
  nappali

konzulens

• 
  Dr. Komjáthy Júlia
  adjunktus, Eindhoven University of Technology (külső)

helyezés