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.
“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.”
Doorbraak
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 Edsgar 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.
Moeilijke en simpele problemen
“Dit is zo’n problem wat makkelijk te formuleren is, maar extreme moeilijk op te lossen”, aldus Maksim. “Het basisidee is als volgt: we zien dat het kortste pad in veel echte netwerken lokaal zijn. Als je tussenstations in een netwerk kan verbeelden als punten in een toepasbare geometrische ruimte, dan is het kortste pad geometrisch dicht bij de geodetische curve die eindpunten op de kortste manier verbindt. Daarmee hoef je niet alle tussenstations in het netwerk te weten om die kortste route te vinden, je tekent een geodetische curve in de ruimte van A naar B en de stations het dichtst bij de curve vormen met zeer hoge waarschijnlijkheid de kortste route.”
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.
Sleutel tot nieuwe toepassingen
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.