Nieuwe methode toont kortste pad bij netwerkanalyse, 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) heeft nu een nieuwe methode gevonden. 

“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 in Nature Communications. 

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. 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.

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.