In zes stappen de wereld rond
Informaticadeskundige Frank Takes onderzocht efficiëntere manieren om in sociale netwerken van A naar F te komen. Daarvoor presenteert hij algoritmen die anderhalf jaar rekenen kunnen terugbrengen tot slechts een paar seconden. Promotie op woensdag 19 november.
Takes onderzocht de onderlinge afstanden binnen online sociale netwerken als Facebook en het inmiddels niet meer bestaande Hyves. Mede gebaseerd op het vermoeden dat twee willekeurige personen doorgaans slechts zes handdrukken van elkaar verwijderd zijn. Ook keek hij naar welke patronen hij in deze en soortgelijke netwerken kon herkennen. De bestaande algoritmen die wiskundigen en informatici hiervoor gebruiken, kunnen weliswaar honderd procent zekerheid bieden dat de onderzoeker van een specifiek netwerk vindt waarnaar hij op zoek is, maar dat kost soms wel anderhalf jaar aan rekentijd.
Enorme tijdwinst
Takes: ‘Door de steeds weer overeenkomende structuur kun je berekeningen die met traditionele algoritmen erg gecompliceerd waren, nu veel sneller en veel efficiënter uitvoeren.’ De nieuwe algoritmen die Takes voorstelt, bieden soms misschien niet de honderd procent correctheid van de traditionele algoritmen, maar: ‘Een benadering van 99,99 en nog wat procent is in de meeste gevallen genoeg.’ En het levert dus een enorme tijdwinst op.
Beter door netwerken navigeren
‘Sociologen bekijken al tientallen jaren netwerken’, vertelt Takes. ‘Tegenwoordig zijn er ook online sociale netwerken. Die zijn digitaal opgeslagen, waardoor je veel grotere hoeveelheden data kunt onderzoeken.’ Allerlei verschillende netwerken – of het nu gaat om een netwerk van samenwerkende eiwitten, een sociaal netwerk als Facebook of een online encyclopedie als Wikipedia – hebben grofweg dezelfde structuur, ondanks dat de data volstrekt verschillend zijn. Het navigeren door die verschillende netwerken verloopt dan ook volgens dezelfde principes.
Een korter zoekpad door Wikipedia
De tijdwinst die dankzij Takes’ algoritmen is te boeken, is van belang voor bijvoorbeeld een marketingafdeling. Daar willen ze graag weten hoe lang het duurt voor een campagne alle leden van een netwerk heeft bereikt. ‘En biologen vinden het interessant om te weten welke eiwitten wel of niet op elkaar van invloed zijn,’ zegt Takes. ‘Als ze op korte afstand van elkaar liggen is er een grotere kans dat ze samenwerken.’ Takes heeft ook gekeken naar de netwerkstructuur van Wikipedia. In Wikipedia kan de gebruiker constant doorklikken op steeds weer nieuwe links naar andere Wikipedia-artikelen. De klikpaden die mensen hiermee maken, zijn echter niet zo efficiënt als die van een zoekmachine.
Van hub naar hub
Volgens Takes is het daarom nuttig om te kijken naar zogenoemde hubs of knooppunten. De hubs zorgen ervoor dat de gemiddelde afstand tussen twee knopen klein is ten opzichte van het totale aantal knopen. Door gebruik te maken van hubs, kan je sneller van A naar F komen. Takes vergelijkt het met een reis van Leiden naar Pompeï. ‘Je kunt met de auto het hele eind ingewikkeld navigeren, maar ook naar Schiphol rijden, naar Rome vliegen en daar weer een auto pakken.’
Links
