10 oktober 2017

Orde in de chaos

Netwerken op social media zijn vaak ongelooflijk groot. Hoe vind je hier toch nog structuur in terug?

Hieronder is een plaatje te zien van mijn LinkedIn-netwerk. Mijn LinkedIn-contacten zijn de punten in het netwerk, en twee LinkedIn-contacten zijn verbonden ze bevriend zijn met elkaar op LinkedIn.

Linkedinrandom
Mijn LinkedIn-contacten zijn de punten in het netwerk, en twee LinkedIn-contacten zijn verbonden ze bevriend zijn met elkaar op LinkedIn. Op het eerste gezicht geeft dit plaatje een ongelooflijke chaos weer.
Clara Stegehuis voor NEMO Kennislink

Op het eerste gezicht geeft dit plaatje een ongelooflijke chaos weer. Alle lijnen lopen kriskras door elkaar heen, en ik kan er geen enkele structuur in ontdekken. En dit is dan alleen nog maar mijn eigen sociale netwerk. Als we alle gebruikers van LinkedIn in één netwerk zouden weergeven, wordt de chaos alleen nog maar groter.

Linkedinclara
Mijn LinkedIn-netwerk. Ik sta in het midden en ben verbonden met al mijn vrienden. Mijn vrienden zijn op hun beurt in groepen verdeeld. Minder chaos!
Clara Stegehuis voor NEMO Kennislink

Toch zijn er in dit soort netwerken vaak structuren te vinden als je goed zoekt. Dit is te zien in het tweede plaatje van mijn LinkedIn-netwerk, waar de punten net iets anders geordend zijn. Nu is het meteen duidelijk dat ik in het midden sta, ik ben namelijk zelf verbonden met al mijn vrienden. Mijn vrienden zijn op hun beurt in groepen verdeeld, net als in mijn Facebooknetwerk. Sportvrienden vormen bijvoorbeeld een groep omdat die elkaar goed kennen, net als mijn familie.

Springveren en magneten

Maar hoe kunnen we deze mooie structuren die we in het tweede plaatje zien terugvinden uit het eerste plaatje? Handmatig is dit niet te doen. Om het tweede plaatje te tekenen gebruikte ik een computerprogramma dat iedere lijn in het netwerk als een springveer ziet. Punten die met elkaar verbonden zijn, worden dus tot elkaar aangetrokken door de springveer.

Tegelijkertijd stoten de punten in het netwerk elkaar juist af als tegenpolen van een magneet. Hierdoor worden punten die niet verbonden zijn met elkaar ver van elkaar vandaan getekend. De springveer over de lijnen zorgt er ondertussen voor dat punten die juist wel met elkaar verbonden zijn dicht bij elkaar getekend worden. Het begin van het onderstaande filmpje laat zien hoe dit gaat.

Het netwerk wordt dus stap voor stap steeds iets mooier getekend. Dit werkt heel goed voor mijn LinkedIn-netwerk, en voor het netwerk dat we in het filmpje zien. Deze netwerken hebben allebei ongeveer tweehonderd punten. Helaas zijn netwerken die we normaal gesproken tegenkomen veel groter. Het netwerk met alle Facebookgebruikers bestaat bijvoorbeeld uit ongeveer twee miljard punten, en is dus ongeveer tien miljoen keer zo groot als de netwerken die we hierboven zagen! Je kunt je voorstellen dat een soortgelijk filmpje om zo’n groot netwerk te ordenen heel lang gaat duren. Voor deze grote netwerken hebben we dus slimmere methoden nodig.

Groepen zoeken

We zouden voor dit soort netwerken graag in één keer willen weten waar de groepen zich bevinden, zonder eerst een heel filmpje met springveren te hoeven doorlopen. Dit probleem wordt in de wiskunde community detection genoemd. Hier hou ik me op dit moment in Parijs ook mee bezig. Kunnen we een wiskundige vergelijking vinden die voor een groot netwerk in één keer vertelt waar de groepen zitten?

Dit blijkt een erg moeilijk probleem te zijn. Er zijn namelijk ontzettend veel verschillende manieren om een netwerk op te delen in groepen. Een netwerk van twintig punten kun je bijvoorbeeld al op honderd miljard verschillende manieren in groepen opdelen! Het is dus een moeilijk probleem, maar er zijn gelukkig een hoop wiskundigen die al wat orde in de netwerkchaos gebracht hebben. Ik hoop hier in Parijs ook een beetje aan bij te dragen!

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

LEES EN DRAAG BIJ AAN DE DISCUSSIE