Nieuwe methode zorgt voor revolutie in netwerkanalyse
Het toont het kortste pad, zelfs wanneer 90% van het netwerk verborgen is.
Hoe vind je de snelste route als je niet alle mogelijke links kunt zien? Zoals bij het 'routen' van internetverkeer – iets dat nu op blind vertrouwen gebeurt -- of eiwitroutes in het lichaam, wat tot compleet nieuwe inzichten in ziektes en medicijnen kan leiden? Al sinds de jaren vijftig breken wetenschappers zich hierover hun hoofd. Maksim Kitsak (TU Delft) zorgt met zijn nieuwe methode voor een revolutie in netwerkanalyse.
Een complex netwerk
“Onze capaciteit om veilige internetprotocollen te bouwen, complexe ziektes te genezen of pandemieën te voorspellen wordt begrensd door ons vermogen om die kortste route te vinden”, stelt Maksim Kitsak. Hij heeft een nieuwe methode ontwikkeld om snel de kortste afstand tussen twee knooppunten in een netwerk te berekenen, zelfs wanneer 90% van het netwerk verborgen is, of zelfs vervuild met valse links. Hij publiceert zijn resultaten deze week in Nature Communications.
Stel je voor dat ik je vertel dat ik een vriend heb die de yoga-instructeur is van Ivanka Trump, dochter van de welbekende voormalige president van de VS. Die op zijn beurt weer nauwe banden onderhoud met Vladimir Poetin. Als jij een bericht voor Poetin hebt, geef die dan maar aan mij, dan komt het via bovenstaande ketting wel bij hem terecht. Zou je hierop vertrouwen? Want zo werken, kort door de bocht, routers voor internetverkeer momenteel. Op goed vertrouwen.
Maksim Kitsak
Op basis van vertrouwen
Een belangrijke toepassing van de nieuwe methode is opsporen van netwerkanomalieën en routeringsonregelmatigheden. Idealiter neemt een router altijd de kortste route naar zijn doelrouter. Dit pad ontstaat dus op basis van vertrouwen, zonder systematische checks, tot stand. Met andere woorden: door een verkeerde configuratie, of juist door kwade opzet, kan internetverkeer gemakkelijk een omweg nemen, bijvoorbeeld door een land als Rusland of Iran. Vanwege het organische, gedistribueerde en daardoor onoverzichtelijke ontstaan van een internet, was een oplossing voor dit bekende probleem moeilijk te formuleren. De methode die Maksim samen met zijn collega's ontwikkelde legt nu de grondslag voor een oplossing. Zo kunnen onnodige afwijkingen in de toekomst snel worden opgespoord of zelfs worden voorkomen – met als resultaat een veiliger internet.
De doorbraak kan worden beschouwd als de volgende grote stap binnen het gebied sinds het pionierswerk van computerwetenschapper Edsger Dijkstra, die in de jaren vijftig voor het eerst een algoritme ontwikkelde voor het vinden van het kortste pad tussen twee knooppunten in een netwerk. Dit ouderwets algoritme werkt echter alleen in de veronderstelling dat het hele netwerk vooraf inzichtelijk is, iets wat in de werkelijkheid vrijwel nooit het geval is.
De nieuwe aanpak is natuurlijk geen "free lunch". Om een kortste pad te vinden in een onvolledig netwerk, is eerst een goede geometrische representatie nodig. Machine-learning biedt hierbij de uitkomst. Zelfs zonder toezicht, met een methode die 'network embedding' wordt genoemd, kan een netwerk geometrisch in kaart worden gebracht. En alhoewel deze Machine Learning-technieken voor ieder specifiek netwerk opnieuw aan het werk moeten, bestaan er voor het internet, sociale netwerken en netwerken van eiwit-interacties al wel goede 'embeddings', waardoor de geometrische methode al ieder van deze netwerksoorten snel toegepast kan worden.
Maksims nieuwe geometrische methode heeft namelijk ook toepassingen op andere gebieden waar netwerken moeten worden geanalyseerd, zoals dus het verkennen van eiwitroutes in het lichaam, waardoor een beter begrip ontstaat van zowel ziekten als de behandeling ervan. Het kan ook helpen bij het analyseren van de verspreiding van pandemieën, zoals bijvoorbeeld een nieuwe COVID-19-uitbraak. In deze analyses is vaak ook maar een klein deel van het netwerk inzichtelijk.
M.A. (Maksim) Kitsak
Digitale maatschappij
We werken aan een verantwoorde digitale samenleving, die ons welzijn vergroot en de wereld schoner maakt. Een digitale samenleving is er allang: van satellieten in de ruimte, je smartphone, verkeerslichten tot aan robots die plastic opruimen van de zeebodem. De vraag is hoe we deze samenleving zo goed en verantwoordelijk mogelijk ontwerpen en inrichten. Zodat we een digitale samenleving krijgen die menselijk blijft, gezond, rechtvaardig, inclusief en veilig. Maar ook schoon en duurzaam, en die de grote, complexe uitdagingen van deze tijd aankan. Bij de TU Delft bedenken en ontwerpen we zowel de digitale technologieën als hun maatschappelijke toepassingen.
Marc de Kool
Wetenschapsvoorlichter Digital Society
Aanwezig: maandag t/m donderdag.