Foto: Jordan Harrison

Het kortste pad, zelfs wanneer 90% van het netwerk verborgen is

Leestijd: < 1 minuten

De kortste afstand tussen twee knooppunten op het internet, is ook te berekenen als tot 90% van het netwerk verborgen is of zelfs vervuild met valse links. Dat heeft Maksim Kitsak, onderzoeker aan de TU Delft, aangetoond met een nieuwe methode van 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. Idealiter neemt een router altijd de kortste route naar zijn doelrouter, maar dit pad wordt gekozen op basis van vertrouwen, zonder systematische checks, tot stand. Onnodige afwijkingen kunnen door het werk van Kitsak snel worden opgespoord of zelfs worden voorkomen.

Kitsak bouwt voort op het pionierswerk van computerwetenschapper Edsgar Dijkstra. Hij ontwikkelde in de jaren vijftig een algoritme voor het vinden van het kortste pad tussen twee knooppunten in een vooraf inzichtelijk netwerk.

Om een kortste pad te vinden in een onvolledig netwerk, is wel 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.

Wel zullen de Machine Learning-technieken voor elk netwerk opnieuw ingezet moeten worden om het netwerk in kaart te brengen. Tenzij er goede embeddings bestaan, zoals voor het internet, sociale netwerken en netwerken van eiwit-interacties. Dan kan de geometrische methode snel toegepast kan worden. Kitsaks nieuwe geometrische methode kan ook worden ingezet op andere gebieden waar netwerken moeten worden geanalyseerd. Denk aan 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.

Lees ook

Nieuwsbrief
* indicates required