Zelfs als niet alle knooppunten en verbindingen bekend zijn, is het mogelijk de kortste of bijna kortste route over een netwerk te berekenen, schrijft een team wetenschappers in Nature Communications. Dat kan internet veiliger en pandemieën beter voorspelbaar maken.
De kortste route van A naar B is vaak handig om te weten. Niet alleen voor wie op reis moet, maar ook voor wie wil weten hoe informatie zich door het internet beweegt, neuronen in het lichaam signalen doorgeven of een besmettelijke ziekte zich door de wereldbevolking verspreidt.
Voor de reiziger is die kortste route vaak makkelijk te vinden. Er bestaan allerlei algoritmen die dit kunnen berekenen, gebruikmakend van wegenkaarten.
Van het internet, neurale netwerken in het menselijk lichaam en sociale netwerken van wereldburgers bestaan die wegenkaarten echter niet omdat die routes continu veranderen en te ingewikkeld of te duur zijn om in kaart te brengen.
Geometrische regels
Voor dit kortste-route-vraagstuk op een grotendeels onbekend wegennet heeft een internationale groep onderzoekers nu een oplossing gevonden.
In een artikel in het wetenschappelijke tijdschrift Nature Communications presenteerden zij deze week de geometrische regels waarmee de kortste – of bijna kortste – route van het ene naar het andere knooppunt kan worden gevonden, zelfs als maar 10 procent van het netwerk bekend is.
Dat is belangrijke informatie, zegt de hoofdauteur van het artikel, elektrotechnisch ingenieur en netwerkdeskundige Maksim Kitsak van de TU Delft, in een nieuwsbericht op de website van zijn universiteit.
‘Onze capaciteit om veilige internetprotocollen te bouwen, complexe ziekten te genezen of pandemieën te voorspellen werd tot nu toe begrensd door ons vermogen om die kortste route te vinden.’
Machine learning
Om de kortste route van A naar B te bepalen maakten de onderzoekers eerst een kaart die het netwerk zo goed mogelijk benadert.
‘Om verschillende redenen, waaronder de privacy en zijn organische groei, is de exacte structuur van het internet onbekend’, legt Kitsak desgevraagd uit. ‘Maar dat geldt niet voor het geraamte van internet, dat uit de grote service- en contentproviders zoals KPN en Google bestaat.’
Dit geraamte vormde de basis voor de geometrische representatie, waarbij met behulp van machine learning schattingen van de dichtheid en graad van knooppunten in de rest van het gebied werden gemaakt. De graad is daarbij het aantal vertakkingen van een knooppunt – is het bijvoorbeeld een simpel kruispunt of een zevensprong?
Kortste lijn
Deze benadering van het netwerk werd weergegeven in een ‘hyperbolisch vlak’ (een representatie met gebogen assen, zie figuur onderaan). Als je daarop de kortste lijn van A naar B trekt, vervolgens vanuit A vertrekt en zorgt dat je zo dicht mogelijk bij die lijn blijft, levert dat een van de kortst mogelijke routes op, constateerden de onderzoekers.
Kitsak: ‘Het is vergelijkbaar met het vinden van de weg naar een hoge toren in een onbekende stad, zonder plattegrond.’ Ook daarbij kiezen mensen bij elk kruispunt voor de weg die de rechte lijn naar de toren het dichtst benadert.
Toepassing
Een belangrijke toepassing van de methode is het veiliger maken van internet. Als de kortste route die informatie over internet kan afleggen onbekend is, kan internetverkeer immers gemakkelijk een omweg nemen – ofwel door een verkeerde configuratie, ofwel door kwade opzet.
‘Onderzoek naar deze route-afwijkingen is dan ook hot’, zegt Kitsak. ‘Wij zijn zeker niet de enigen die hier mee bezig zijn. Maar onze kortste-weg-analyse is wel een heel nieuwe invalshoek om dit probleem mee op te lossen.’
zoals in dit geval bij de houtdruk ''Circle Limit III' van M.C. Escher (1959)
Openingsbeeld: Depositphotos
Nieuwsbrief
Vond je dit een interessant artikel, abonneer je dan gratis op onze wekelijkse nieuwsbrief.