Cecilia Holmgren forskar på slumpgrafer

Redan vid femton års ålder, 1999, hade Cecilia Holmgren tentat av matematiken på gymnasiets naturvetarprogram och fick dispens för att börja läsa matematik vid Chalmers. Hon fastnade tidigt för slumpgrafer, slumpträd och splitträd. När hon försvarade sin avhandling "Split trees, Cuttings and Explosions" i Uppsala (2010) var hon först i världen med att bevisa generella egenskaper hos splitträden som är en stor klass av slumpträd. En känd typ av splitträd är binära sökträd, som motsvaras av sorteringsalgoritmen Quicksort, som används för att sortera data.

Cecilias forskning är rent matematisk. Den ligger i skärningen mellan de två områdena sannolikhetsteori och kombinatorik, men stora delar av den har praktiska tillämpningar.

– Slumpgrafer och splitträd används bland annat för att utveckla algoritmer för sökningar och rekommendationer på internet, studera hur smittor eller rykten sprids och analysera sorteringsalgoritmer i datorer för att sortera data.

Resultaten kan också tillämpas inom artificiell intelligens där studiet av sociala nätverk och utvecklingen av olika typer av algoritmer är viktigt. Cecilia, som numera är docent och lektor, arbetar också med betingade Galton Watson-träd, som är en annan stor klass av slumpträd som bland annat kan beskriva en släkts överlevnad.

– Jag tycker om att arbeta med stora klasser av slumpgrafer på en gång i stället för enskilda slumpgrafer, säger hon.

En intressant egenskap hos flera slumpstrukturer är att relativt små förändringar hos sannolikheterna ger stora förändringar totalt. Ett exempel är släktträd. Om antalet barn i släkten i medeltal är mindre än 1 dör den ut, men är antalet i medeltal större än 1 överlever den. Ett annat exampel är smittspridning där en liten förändring i immunitet/spridning (via exempelvis hur många procent som vaccinerar sig) kan avgöra om en smitta dör ut eller sprider sig över världen. Sådana brytpunkter kallas tröskelvärden och är kopplade till s.k. perkolationsteori.

Utöver det arbetar Cecilia med konfigurationsmodellen, en allmän slumpgrafsmodell, som används i alltifrån Facebook och andra sociala nätverk, biologiska nätverk som hjärnan, telekommunikationer och elektriska kraftnät.

Cecilias framgångar har gjort att hon fått flera stora anslag och på så vis haft möjlighet att knyta duktiga doktorander och postdoktorer till sin forskargrupp.

– Jag är glad över att ha en stark forskargrupp. Mina doktorander och postdocs arbetar med spännande projekt och håller många intressanta seminarier och föredrag på konferenser. Detta kan i sin tur attrahera andra duktiga forskare och knyta internationella kontakter.

Bilden av matematikforskaren som sitter ensam i ett rum med travar av böcker omkring sig stämmer inte på Cecilia:

– Jag trivs bäst när jag samarbetar med andra, det gäller både seniora forskare, postdocs och doktorander. På Uppsala universitet träffar jag även studenter och får tillfälle att väcka intresse för mitt område hos dem, vilket är väldigt roligt.

– Tack vare att universitetet och jag och min forskargrupp har gott rykte får vi många duktiga studenter och forskare.

Slumpgrafer och splitträd

En graf består av noder och kanter mellan noderna. Noderna kan stå för webbplatser och kanterna representera länkar mellan dem, eller så kan noderna stå för individer och kanterna för kontakter mellan dem, som sexuella relationer eller handskakningar. Ett träd är en graf där det bara finns en väg av kanter mellan två noder. Man kan tänka på ett släktträd där noderna står för individer och det finns en kant mellan två individer om den ena är barn till den andra.

Slumpgrafer och slumpträd är grafer och träd som genereras av slumpprocesser. Vi kan skapa en kant mellan två noder med en viss sannolikhet. Om sannolikheten är hög nog är det troligt att hela grafen sitter ihop. Splitträd är slumpträd som konstrueras för att modellera olika sorteringsalgoritmer. Genom att studera motsvarande splitträd kan man analysera algoritmens egenskaper (exempelvis söktiden som ger ett mått på hur effektiv algoritmen är).

Ina Bergström

2021