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. 

Tags:
Visualisatie van de kortste route
Visualisatie van de kortste route. Beeld: Maksim et al.

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

Tags:

Geef een reactie

Je e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *

Reacties (1)

  1. Ik vind dat dit stukje geen enkel inzicht geeft hoe e.e.a. dan wel in zijn werk zou gaan. Bovendien zitten er tendentieuze suggesties in:
    – “Trump onderhoud nauwe banden met Poetin”
    – “pandemieën bedreigen ons altijd en overal”
    – “een nieuwe Covid-19 uitbraak ligt al op de loer”
    etc.
    Geheel in lijn met het narratief van degenen die ons inmiddels al 3 jaar in de greep houden van allerlei onzinnige maatregelen en leugenachtige beschuldigingen.
    Trump is vrijgesproken van de zgn. ‘Russia-collusion’, maar dat schijnt voorbijgegaan te zijn aan degene die dit stukje schreef.
    Het is een fictie dat pandemieën ons voortdurend bedreigen, de angst daarvoor wordt kunstmatig aangewakkerd en in stand gehouden door spelers met andere belangen die oefeningen houden kort voordat de zgn. pandemie op wonderbaarlijke wijze hun script gaat volgen, vergelijk de ontwikkelingen rond Covid-19 maar eens met ‘Event 201’, de tabletop exercise die zich vooraf vooral richtte op het censureren van onwelgevallige kritiek door “desinformatie” als een zo mogelijk nog grotere bedreiging neer te zetten als het vermeende vleermuizenvirus.
    Is dit alles een gevolg van een subsidie van een NGO? Zo niet, doe dit soort dingen dan niet, het is bijna net zo erg als het vele ‘woke’-geleuter dat heden ten dage overal opduikt. Zo ja, weiger die subsidie dan in het vervolg of ga je daardoor niet gedragen als een slaafse hond die de baas naar zijn ogen kijkt.