Eva Rotenberg og hendes makker fra KU fandt en bagvej ind i et teoretisk maskinrum til at håndtere ændringer i et netværk. Arbejdsmetoden bidrager til hendes forskning fremover.
Forskere, der oplever et videnskabeligt gennembrud, beskriver ofte, hvordan de i tiden efter er fyldt med en blanding af lykkefølelse, energi og søvnløshed, fordi tankerne kværner rundt, og forskningsresultatet skal verificeres og publiceres.
Sådan var det også for datalog og lektor Eva Rotenberg fra sektionen Algoritmer, Logik og Grafer (AlgoLoG) på DTU Compute og hendes makker, datalog og adjunkt ved Københavns Universitet Jacob Holm. Ved at tænke utraditionelt løste de en af de mest fundamentale gåder inden for forskningsfeltet grafteori, hvor de udviklede en algoritme til hurtigt at besvare, hvad der sker, når en graf ændrer sig.
Forskningsresultatet blev kendt sidste år, og er så bemærkelsesværdigt, at Eva Rotenberg og Jacob Holm i næste uge skal fortælle om det på den prestigefyldte konference ’Highlights of Algorithms’. Konferencen inviterer kun forskere bag verdens allervigtigste resultater inden for algoritmik.
”Jeg håber, at vores resultat kan være en inspiration til andre forskere om at træde et skridt tilbage og stille de lidt mere teoretiske spørgsmål, som hvor meget en løsning skal ændre sig, når spørgsmålet ændrer sig en lille smule, fordi det kan føre til nogle effektive programmer. Det er en teknik, som jeg selv vil bruge fremadrettet,” siger Eva Rotenberg.
Ændringer i netværk
"Jeg håber, at vores resultat kan være en inspiration til andre forskere om at træde et skridt tilbage og stille de lidt mere teoretiske spørgsmål, som hvor meget en løsning skal ændre sig, når spørgsmålet ændrer sig en lille smule."
Eva Rotenberg, datalog og lektor i sektionen Algoritmer, Logik og Grafer (AlgoLoG) på DTU Compute
Grafteori spiller en grundlæggende rolle i datalogi, især i design og analyse af algoritmer. Grafer består af knuder (punkter), der er forbundet af kanter (forbindelseslinjer). For eksempel bruges grafer til modellering af netværk, modellering af strukturen i computersoftware samt visualisering af kommandostrømmen i et program. Men grafteori kan i princippet handle om alle slags netværk; vejnetværk, smittenetværk, transportnetværk, kommunikationsnetværk.
I den fysiske verden ændrer netværk sig over tid. Nogle steder kan det være ekstra vigtigt at vide, om forbindelser krydser hinanden. På printplader og i mikrochips vil det f.eks. føre til kortslutning.
Ændringer i sådanne dynamiske grafer har voldt matematikerne problemer i mange år. Man har forsøgt effektivt at opdatere, hvorvidt en graf stadigvæk kan tegnes uden, at stregerne krydser hinanden, når forbindelser forsvinder og nye opstår.
Eva Rotenberg og Jacob Holm har udviklet en algoritme til at håndtere ændringer i netværket, så man netop enten undgår, at forbindelseslinjerne krydser hinanden eller må konkludere, at grafen med udgangspunkt i de nuværende forhold ikke kan tegnes sådan.
”Man kan ikke nøjes med at beregne noget statisk på et netværk, men skal kunne inddrage dynamiske ændringer i beregningerne. Vi har fundet ud af, hvordan man på teoretisk plan hurtigt og effektivt kan håndtere en ændring i en graf, så punkterne om muligt kan forbindes, uden at forbindelseslinjerne krydser hinanden,” fortæller Eva Rotenberg.
"Udfordringen er at skelne mellem situationen, hvor grafen ikke længere kan tegnes uden kryds, og situationen hvor man blot skal ændre på tegningen for at få plads til den nye forbindelse.”
Træd et skridt tilbage
Forskerne valgte at gå mere teoretisk til opgaven end normalt. I stedet for at gå direkte ind på at løse selve det algoritmiske problem - om den opdaterede graf kan tegnes, uden at linjerne krydser - så studerede de egenskaber ved netværket. På den måde ville de undersøge, om der kunne findes en smart måde at tegne netværket på, så uanset hvilken ny forbindelseslinje, der kom, kunne man nøjes med at lave ganske små/få ændringer på tegningen.
”Måden at løse problemet på var faktisk at træde et skridt tilbage og være endnu mere nørdede og kun kigge på antallet af ændringer, der skulle til. Da vi svarede på dét spørgsmål først, fandt vi i svaret nøglen til at løse problemet med en hurtig effektiv algoritme nærmest ved et tilfælde, som ved at finde en bagvej ind,” uddyber Eva Rotenberg.
”Hvis du stiller et spørgsmål, og jeg svarer på det, og du så ændrer en lille smule i dit spørgsmål, hvor meget skal jeg så ændre mit svar? Tilsvarende i grafteorien, hvor man kan ændre sin løsning ganske lidt, når spørgsmålet ændrer sig ganske lidt. Den måde at tænke på tager jeg med mig videre, som et vigtigt spørgsmål.”
Mens selve arbejdsmetoden til at løse teoretiske matematiske problemstillinger kan bruges her og nu, er Eva Rotenberg mindre optaget af, hvordan resultatet kan bruges.
”Jeg specialiserer mig ikke i at få de teoretiske resultater ud at gøre gavn for verden. Det er der andre, der gør. Jeg tager mig af grundforskningen – det teoretiske. Vi har et netværk, og vi ved ikke, om det er en transportnetværk eller et netværk mellem personer. Vi ved bare, at der er knuder og kanter. Og så laver vi vores algoritmer, så de virker helt generelt for netværk.”
I januar 2021 fik Eva Rotenberg et Villum Young Investigators grant på seks millioner danske kroner, så hun kan ansætte to ph.d.-studerende og en postdoc i projektet Efficient Recomputations for Changeful Problems, hvor de netop skal forske i dynamiske grafer.
Et kendt eksempel med grafteori ’The Three Utilities Problem’ er tilbage fra 1913. Magasinet The Strand Magazine’ præsenterede læserne for en opgave, hvor tre hytter skulle have tilført vand, gas og elektricitet, men ingen ’forsyningslinjer’ mellem husene måtte krydse hinanden. På papir (2D) er det umuligt at løse opgaven. Kilde: Wikipedia CC BY-SA 4.0