Hoe vind je het kortste pad in een netwerk waarvan niet alle verbindingen bekend zijn, zoals het internet of eiwitroutes in het lichaam? Naar het antwoord op die vraag zoeken wetenschappers al decennia. Onderzoekers van onder meer de TU Delft hebben nu voor bepaalde netwerken een oplossing gevonden.
Het vinden van de snelste route in een netwerk is een bekend probleem dat je kunt oplossen als je alle knooppunten en verbindingen kent. Een oplossing daarvoor kwam in 1959 in de vorm van het Dijkstra’s algoritme, ontwikkeld door de Nederlandse informaticus Edsger Dijkstra. Dat algoritme wordt bijvoorbeeld gebruikt in navigatiesystemen.
‘Maar zodra we niet alles van het netwerk weten, wordt het kortste-padprobleem al snel erg lastig’, vertelt netwerkwetenschapper Maksim Kitsak, van de TU Delft. Hij ontwikkelde met collega’s een nieuwe methode die het kortste pad tussen twee knooppunten in bepaalde netwerken kan berekenen. Dit blijkt zelfs mogelijk af 90 procent van de verbindingen in het netwerk verborgen zijn, of als het netwerk valse links bevat.
‘Einstein liep als theoreticus vast op de nieuwe bevindingen’
Toen de Nederlandse natuurkundige Heike Kamerlingh Onnes iets geks ontdekte over supergeleiding, was dit onder veel fysici het gesprek van de dag. Maa ...
Vertrouwen in het internet
Er is veel vraag naar deze methode. De meeste grootschalige netwerken zijn namelijk incompleet. Neem bijvoorbeeld sociale netwerken. Tijdens de coronacrisis probeerde de overheid de sociale contacten van mensen in kaart te brengen. Dat is een incompleet netwerk, want het is onmogelijk – en vanuit privacyoogpunt onwenselijk – om alle contacten van iedereen te kennen.
‘Een ander voorbeeld is het internet’, zegt Kitsak. ‘Het beheer daarvan is grotendeels in handen van bedrijven die allemaal over een deel van het netwerk gaan.’ Die bedrijven geven weinig informatie vrij. Bovendien vinden er elke paar minuten veranderingen plaats.
Op dit moment werkt het internet op basis van vertrouwen. Routers, de knooppunten van het internet, vertellen aan hun buren naar welke andere knooppunten ze korte lijntjes hebben. Die buren vertellen dat weer door en zo wordt het duidelijk via welke knooppunten je iemand kunt bereiken.
Kitzak: ‘Stel je voor: ik heb contact met een geweldige promovendus, en ik vertel dat aan jou. Jij kan die informatie dan met anderen delen en hun vertellen: als je een bericht hebt voor deze geweldige promovendus, laat mij dat dan weten, dan geef ik het door aan Maksim en die geeft het door aan die promovendus.’
In dit scenario moet je er wel op vertrouwen dat iedereen de waarheid vertelt, en dat niemand jouw vertrouwelijke email langs een inlichtingendienst of roddelblad stuurt.
Kortste pad in Manhattan
De methode die Kitsak en zijn collega’s hebben ontwikkeld, kan het internet veiliger maken, door frauduleuze communicatiepaden te detecteren en te verwijderen. Hierdoor kunnen we mogelijk situaties vermijden waarin internetverkeer ongewenst wordt omgeleid via bijvoorbeeld Rusland of China.
De methode werkt als volgt: de onderzoekers zoeken eerst een zogeheten geometrische representatie van het netwerk. Deze representatie verdeelt de knooppunten over een geometrische ruimte. Afhankelijk van het netwerk kan dat een gewoon (Euclidisch) vlak zijn of iets complex, zoals een hyperbolische Poincaré-schijf. De verdeling van de knooppunten in die ruimte verbeeldt hun onderlinge afstanden. Vervolgens trek je de kortste lijn tussen de twee knooppunten die je wilt verbinden – de zogeheten geodeet. Als de geometrische ruimte een vlak is, dan is dat een rechte lijn. De knooppunten die het dichtst bij die lijn liggen vormen dan zeer waarschijnlijk het kortste pad tussen de twee punten.
Deze methode blijkt goed te werken, zelfs als je veel verbindingen tussen de knooppunten niet kent. Kitsak en zijn collega’s konden de kortste paden op internet vinden, zelfs als tot 90 procent van de verbindingen willekeurig werd verwijderd.
‘Je kunt het vergelijken met de weg vinden naar een wolkenkrabber in Manhattan in New York’, zegt Kitsak. ‘De straten vormen daar een rasterpatroon. En als je bijvoorbeeld naar het Empire State Building wilt lopen, dan zie je dat boven de andere gebouwen uittorenen. Je kunt nu gemakkelijk naar dat gebouw lopen omdat je weet hoe de straten gerangschikt zijn. Je komt er door telkens een straat te kiezen die zoveel mogelijk in de richting van de wolkenkrabber loopt.’
Geen one-size-fits-all
‘Ons werk biedt geen one-size-fits-all oplossing voor alle incomplete netwerken’, zegt Kitsak. ‘We doen namelijk twee aannames over het netwerk. De eerste is dat je er een geometrische representatie van kunt maken.’ Dat is met het internet mogelijk, maar het is niet zeker dat dat met alle netwerken kan.
De tweede aanname is dat overal in het netwerk ongeveer evenveel verbindingen ontbreken, en dat het volledig willekeurig is of een verbinding ontbreekt of niet. Dat is werkelijkheid zelden het geval. Internetverbindingen kunnen bijvoorbeeld lokaal veranderen of verdwijnen door geopolitieke gebeurtenissen.
Kitsak: ‘We gaan nu uitzoeken wat de grenzen zijn van deze aannames. En we hopen dat de methode blijft werken als de verbindingen bijvoorbeeld niet volledig willekeurig en uniform verdeeld over het netwerk ontbreken.’
