1 Introductie
Een netwerk is eigenlijk niets meer dan een collectie van punten die verbonden is door lijnen, zoals in Afbeelding 1.1. Wiskundigen noemen netwerken meestal grafen. In principe zijn deze begrippen equivalent, maar vaak wordt het woord netwerk gebruikt als wetenschappers specifieke toepassingen bestuderen, en graaf in een meer theoretische (wiskundige) context.
In dit hoofdstuk bespreken we het begin van de wiskundige studie van grafen en introduceren we enkele wiskundige definities die ons later zullen helpen bij het beschrijven van netwerken. Vervolgens bespreken we een aantal voorbeelden van systemen die door wetenschappers als netwerk worden bestudeerd. Ondanks het feit dat deze systemen uiteenlopen van technologische tot sociale en biologische netwerken blijken de corresponderende netwerken gemeenschappelijke eigenschappen te hebben. We zullen later in deze webklas meer aandacht besteden aan deze eigenschappen.
Afbeelding 1.1: Een voorbeeld van een netwerk/graaf: een collectie van punten verbonden door lijnen.
In de wiskunde werken we met precieze definities om ambiguïteit te voorkomen. De eerste definitie die we in deze webklas introduceren is die van een graaf.
In deze definitie gebruiken we het begrip verzameling. Een verzameling is een collectie van verschillende objecten. Een voorbeeld van een verzameling is de verzameling van de getallen \(1,3\) en \(7\). We gebruiken de notatie \(\{1,3,7\}\). De accolades { } worden gebruikt voor een ongeordende verzameling, een verzameling waarbij de volgorde van de objecten niet uitmaakt. Oftewel \(\{1,3,7\} = \{3,1,7\} = \{7,1,3\}\). Voor een geordende verzameling worden de haakjes ( ) gebruikt. In dit geval zijn de verzamelingen \((1,3,7)\) en \((1,7,3)\) niet hetzelfde: \((1,3,7) \neq (1,7,3)\).
Opgave 1.2 Geef voor elk van de volgende uitspraken aan of deze waar is of niet waar.
\(\{x,y,z\} = \{y,z,x\}\).
\((x,y,z) = (y,z,x)\).
\((1,2,3,4,5) \neq (1,2,4,5)\).
\((1,3,5)\) is een ongeordende verzameling.
\(\{1,3,5\}\) is een ongeordende verzameling.
- \((5,3,1)\) is een geordende verzameling.
Het is misschien niet meteen duidelijk dat definitie 1.1 inderdaad een netwerk beschrijft. De verzameling \(V\) representeert de knopen (vertices) in het netwerk en de verzameling \(E\) representeert de lijnen (edges) van het netwerk. Het aantal knopen in een netwerk zullen we altijd aanduiden met \(n\), oftewel \(n=|V|\) waar \(|V|\) de grootte van de verzameling \(V\) aanduidt. Voor het aantal lijnen in een netwerk gebruiken we altijd \(m = |E|\). Het volgende voorbeeld zal de definitie verduidelijken.
We noemen punten die verbonden zijn door een lijn buren.
Opgave 1.3 Teken de volgende grafen
\(G=(V,E)\), \(V=\{v_1,v_2,v_3,v_4\}\) en \(E=\{\{v_1,v_2\}, \{v_2,v_3\}, \{v_3,v_4\}\}\).
\(G=(V,E)\), \(V=\{v_1,v_2,v_3,v_4\}\) en \(E=\{\{v_1,v_2\}, \{v_2,v_3\}, \{v_3,v_4\}, \{v_1, v_4\}\}\).
- \(G=(V,E)\), \(V=\{v_1,v_2,v_3,v_4,v_5\}\) en \(E=\{\{v_1,v_2\}, \{v_1,v_3\}, \{v_1, v_4\}\}\).
Afbeelding 1.2: Drie kleine grafen.
In het vervolg zullen we de volgende begrippen regelmatig tegenkomen. Met het symbool \(\in\) duiden we aan dat een object een element van een verzameling is. Met andere woorden \(1 \in \{1,3,7\}\), maar \(2 \notin \{1, 3, 7\}\).
Opgave 1.7 Laat \(G=(V,E)\) een graaf zijn met \(n\) knopen, oftewel \(V=\{v_1, v_2, ..., v_n\}\). Motiveer bij ieder onderdeel je antwoord.
Gegeven is dat knoop \(v_i\) graad \(k_i\) heeft, voor \(i=1,\dots,n\). Hoeveel lijnen heeft deze graaf?
Een graaf heet volledig als elk paar knopen in \(V\) verbonden is. Hoeveel lijnen heeft een volledige graaf met \(n\) knopen?
Hoeveel lijnen zijn er minstens nodig om te garanderen dat \(G\) samenhangend is? Hint: het antwoord is niet \(n-1\).
- Hoeveel verschillende grafen bestaan er met \(n\) knopen?
1.1 De zeven bruggen van Königsberg
Het probleem van de zeven bruggen van Königsberg wordt gezien als het begin van de wiskundige studie van grafen. Dit probleem dateert uit 1736 en werd opgelost door de beroemde wiskundige Leonhard Euler. Königsberg (nu Kaliningrad) is een stad die wordt verdeeld door een rivier (zie Afbeelding 1.3) en waarvan de verschillende delen zijn verbonden door zeven bruggen. De inwoners van Königsberg wilden een optocht organiseren zodat elke brug precies één keer werd overgestoken. Euler bewees dat dit onmogelijk is. Om het probleem rigoreus aan te pakken, beschreef hij het probleem op een multi-graaf: een graaf waarbij punten door meer dan één lijn verbonden kunnen zijn. Afbeelding 1.3 toont de kaart van de stad Königsberg en de multigraaf die Euler introduceerde om het probleem op een abstracter niveau te bestuderen.
Afbeelding 1.3: De kaart van de stad Königsberg getekend door Bering in 1613 (boven) en de multi-graaf die Euler gebruikte om het probleem wiskundig te formuleren (beneden).
Het probleem van de bewoners van Königsberg luidt nu, is er een pad dat elke lijn van de multi-graaf exact één keer bezoekt? Tegenwoordig worden zulke paden Euler paden genoemd. Euler bewees de volgende stelling.
Opgave 1.8 Leg uit hoe Stelling 1.1 laat zien dat er geen route voor een optocht bestaat die voldoet aan de eisen van de bewoners van Königsberg.
Stel dat je één brug mag overslaan, is het dan wél mogelijk om een Euler pad te vinden? Zo ja, welke brug zou je overslaan en wat is de route?
Afbeelding 1.4: De vijf Platonische lichamen, een mobile gemaakt door Jacobien (eerste wiskunde les voor haar dochter).
1.2 De wiskunde van netwerken
We kunnen een netwerk \(G=(V,E)\) niet alleen beschrijven aan de hand van de verzamelingen \(V\) en \(E\), maar ook op andere manieren. We introduceren nu een andere manier om een netwerk te beschrijven.
Voor een netwerk met drie knopen ziet de adjacency matrix er als volgt uit.
\[ A = \left(\matrix{A_{11} & A_{12} & A_{13} \\ A_{21} & A_{22} & A_{23} \\ A_{31} & A_{32} & A_{33} \\ } \right) \]
Het netwerk in de linker graaf in Afbeelding 1.2 heeft de volgende adjacency matrix.
\[A = \left(\matrix{ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ }\right) \]
In de grafen die we tot nu toe hebben gezien zijn er geen lijnen tussen een knoop en zichzelf. In de adjacency matrix betekent dit dat er nullen op de diagonaal staan, oftewel de waarde van alle plekken \(A_{ii}\) is gelijk aan nul.
De hoofdletter sigma, \(\Sigma\), in bovenstaande opgave wordt gebruikt om op een compacte en effectieve manier een sommatie aan te geven. Een sommatie ziet er dus zo uit: \[ \sum_{i=m}^n x_i = x_m + x_{m+1} + x_{m+2} + \dots + x_{n-2} + x_{n-1} + x_n. \] De letter \(i\) duidt de index aan. De letter \(m\) is de ondergrens van de sommatie en de letter \(n\) de bovengrens van de sommatie. Zo is bijvoorbeeld \(\sum_{i=1}^{4} i^2 = 1^2 + 2^2 + 3^2 + 4^2 = 30\).
Opgave 1.13 In deze opgave berekenen we het aantal mogelijke paden van een gegeven lengte tussen twee punten in een graaf aan de hand van zijn adjacency matrix.
Leg uit waarom \([A^2]_{ij} := \sum_{k=1}^{n} A_{ik} A_{kj}\) het aantal paden van lengte 2 tussen de knopen \(v_i\) en \(v_j\) voorstelt.
Leg uit waarom \([A^3]_{ij} := \sum_{k,l=1}^{n} A_{ik} A_{kl} A_{lj} = \sum_{k=1}^{n} \sum_{l=1}^{n} A_{ik} A_{kl} A_{lj}\) het aantal paden van lengte 3 tussen \(v_i\) en \(v_j\) voorstelt.
Leg uit waarom \(\frac{1}{6}\sum_{i=1}^{n} [A^3]_{ii}\) het aantal driehoeken in de graaf voorstelt.
Geef een formule \([A^r]_{ij}\) voor het aantal paden van lengte \(r\) tussen \(v_i\) en \(v_j\) en verklaar deze formule.
1.3 Netwerken
Het bruggenprobleem van Königsberg wordt gezien als het begin van de wiskundige studie van grafen en de eerste toepassing van grafentheorie. De afgelopen vijftien à twintig jaar is de studie van netwerken ontzettend populair geworden. Door de opkomst van grote datasets en snelle computers kunnen wetenschappers tegenwoordig hele grote netwerken onderzoeken. We bespreken nu een aantal voorbeelden van systemen die als netwerk bestudeerd worden.
1.3.1 De hersenen
Onze hersenen bestaan uit neuronen die met elkaar verbonden zijn via axonen en dendrieten. De output van een neuron is de input voor een ander neuron. Helaas is het erg moeilijk om een hersennetwerk in kaart te brengen. Om dit te doen wordt voornamelijk gebruik gemaakt van de volgende techniek: de hersenen van een overleden dier of persoon worden in dunne plakjes gesneden en met een microscoop bekeken. Elk plakje geeft een klein deel van het netwerk, en vervolgens worden deze delen bij elkaar gevoegd en de verbinding tussen de neuronen in verschillende plakjes zo goed mogelijk toegevoegd. Wetenschappers schatten dat het menselijk brein ongeveer 100 miljard neuronen bevat, dit maakt het in kaart brengen van het menselijk brein via bovenstaande techniek een onbegonnen werk. Een groep wetenschappers van Princeton University probeert dit in beeld te krijgen in de vorm van een spel waar spelers (handmatig) neuronen verbinden, zie Eyewire. Wetenschappers hebben de hersenen van de zogeheten C. Elegans worm wel geheel in kaart weten te brengen. Deze worm is erg veel bestudeerd en Open Worm is een open source project met als doel een virtuele versie van deze worm te maken.
1.3.2 Het Internet
Het Internet is een technologisch netwerk dat bestaat uit computers en data verbindingen tussen deze computers. Ondanks dat dit netwerk door mensen gebouwd is, weet niemand precies hoeveel computers er aangesloten zijn en hoe alle verbindingen lopen, aangezien er geen centrale organisatie is die het aansluiten van computers reguleert. Het Internet Mapping Project is een project van Bell Labs om een deel van het Internet in kaart te brengen. Wetenschappers zijn geïnteresseerd in de structuur van het Internet om verschillende redenen. De functie van het Internet is om data te transporteren tussen computers, dit gebeurt door de data in pakketen op te delen en deze van knoop naar knoop (computer) te sturen in het netwerk. De structuur van het netwerk speelt een rol in hoe efficiënt dit gedaan kan worden. Als we deze structuur kennen, kunnen we veel praktische vragen van te voren beantwoorden. Bijvoorbeeld hoe we pakketen op de slimste manier door het netwerk kunnen routen of wat er gebeurt als een verbinding uitvalt. Die laatste vraag bestuderen we in Hoofdstuk 4.
Opgave 1.14 Stel dat je een data pakket wilt versturen in een netwerk met vijf knopen \(v_1, v_2, \dots, v_5\). Kun je een netwerk verzinnen (teken deze) dat minstens vier lijnen (en maximaal 1 tussen elk paar knopen) bevat en zodanig dat:
Het onmogelijk is om een pakket van \(v_1\) naar \(v_5\) te bezorgen.
Je minstens vier lijnen moet doorlopen om een pakket van \(v_1\) naar \(v_5\) te bezorgen.
Je voor elke knoop precies twee andere knopen in één stap kunt bereiken, en twee knopen in twee stappen kunt bereiken.
- Je voor elk paar knopen \(v_i\) en \(v_j\) maximaal twee lijnen nodig hebt om een pakket tussen de knopen te versturen. Doe dit met zo min mogelijk lijnen.
1.3.4 Contact netwerken
Contact netwerken zijn netwerken tussen personen of dieren waarbij twee knopen verbonden zijn als de personen (of dieren) contact hebben gehad of op de zelfde plaats zijn geweest. Deze netwerken zijn erg belangrijk bij het bestuderen van de verspreiding van besmettelijke ziekten. Afhankelijk van de ziekte en hoe besmetting wordt overgebracht zijn verschillende definities van `contact’ nodig. Zo worden sommige besmettelijke ziektes alleen door direct contact overgebracht terwijl andere via vochtdruppels (hoesten en niezen) worden overgebracht. De studie van contact netwerken is een belangrijk onderwerp in het begrijpen en voorkomen van grote epidemiën.
1.4 Universele eigenschappen
Een van de redenen dat network science een erg populair onderzoeksgebied is geworden is dat ondanks het feit dat de netwerken die bestudeerd worden heel divers zijn, ze toch gemeenschappelijke eigenschappen hebben.
We zullen zien dat veel netwerken een groot aantal driehoeken bevatten, en ondanks deze eigenschap nog steeds een kleine wereld vormen. Dit betekend dat alle knopen met relatief weinig tussenstappen verbonden zijn in vergelijking met de grootte van het netwerk.
Bovendien zullen we zien dat de verdeling van het aantal buren voor de knopen in een netwerk vaak een scheve verdeling is. Er zijn meestal veel knopen met weinig buren, maar ook een paar met heel erg veel buren.
Bonusopgave 1.1 (technische uitdaging van de week)
Download netwerk1.txt, netwerk2.txt en dolfijnen.txt hier. In deze tekstdocumenten vind je gegevens van drie verschillend netwerken.
De netwerken wordt beschreven door een lijst van lijnen. Op iedere regel vind je de namen (getallen) van twee knopen. Dit betekent dat de lijn tussen deze twee knopen aanwezig is in het netwerk. De knopen worden gescheiden door een tab.
Het bestand netwerk1.txt komt overeen met het netwerk in Figuur 1.5.
Schrijf een programma dat het netwerk in netwerk1.txt laad en de adjacency matrix weergeeft.
Schrijf een programma dat het netwerk in netwerk1.txt laad en de graden van de knopen uitrekend. Gebruik hetzelfde programma om de graden van de knopen in netwerk2.txt en dolfijnen.txt uit te rekenen.
Schrijf een programma dat controleert of een netwerk samenhangend is of niet. Gebruik dit programma om te kijken of netwerk2.txt en dolfijnen.txt samenhangend zijn of niet.
TIPS: je kunt een groot aantal verschillende programmeer talen en software pakketen kiezen om deze opgave te maken.
In sommige bibliotheken zijn bovenstaande functies al geïmplementeerd. Zoals bijvoorbeeld in igraph: http://igraph.org of networkx https://networkx.github.io.
Probeer echter zelf code te schrijven om vraag a, b en c te beantwoorden.
Gebruik het forum om met andere leerlingen te overleggen!Bonusopgave 1.2 (creatieve uitdaging van de week)
Visualiseer (een deel van) een netwerk naar keuze. Kijk bijvoorbeeld eens op http://konect.uni-koblenz.de/networks/ voor netwerk data. Of construeer zelf een netwerk zoals bijvoorbeeld je Facebook ego-netwerk (het netwerk van vriendschappen tussen je vrienden).
Ter inspiratie voor degenen die dit willen programmeren:
https://www.openprocessing.org/sketch/392394
https://christophergandrud.github.io/networkD3/
https://gephi.org
1.3.3 Sociale netwerken
Tegenwoordig denken we bij sociale netwerken voornamelijk aan online sociale netwerken zoals Facebook, Twitter en LinkedIn. Sociologen bestuderen al veel langer hoe de relaties tussen personen bijvoorbeeld hun positie in de maatschappij beïnvloed. Een sociaal netwerk bestaat uit personen en relaties tussen deze personen. Voordat online sociale netwerken bestonden werden sociale netwerken geconstrueerd door observatie, bijvoorbeeld van spelende kinderen of door het uitdelen van vragenlijsten waarin de personen zelf aangeven met wie zij bevriend zijn of graag samenwerken.
Opgave 1.15 Stel je voor dat je een feest hebt georganiseerd waar sommige van de gasten elkaar al kennen. Beantwoord de volgende vragen over het netwerk met als knopen de gasten en lijnen tussen gasten die elkaar reeds kennen.
Stel er zijn 5 gasten, oftwel \(n=5\). Is de volgende situatie mogelijk? Er zijn twee mensen in het gezelschap die precies één vriend hebben die aanwezig is op het feest, twee gasten hebben precies twee vrienden aanwezig en één heeft drie vrienden aanwezig. Hint: Bewijs dat elke graaf een even aantal knopen heeft van oneven graad.
Is het mogelijk om een feest te organiseren met een willekeurig aantal gasten en waarbij er niet twee mensen zijn die evenveel vrienden hebben? Hint: Maak onderscheid tussen een samenhangende graaf en een niet-samenhangende graaf.
Stel je er zijn \(n=10\) mensen aanwezig op het feest en iedere aanwezige gast heeft minstens één vriend die aanwezig is op het feest. Als jij aan de overige negen gasten vraagt hoeveel vrienden er van ze op het feest zijn, dan geven ze allemaal een ander antwoord. Hoeveel vrienden van jou moeten er dan aanwezig zijn?
Heb je wel eens het gevoel dat jouw vrienden populairder zijn dan jijzelf? Dat kan zijn omdat het waar is, voor bijna iedereen dan. Dit opmerkelijke resultaat, genaamd de vriendschapsparadox, zien we bijvoorbeeld terug op social media. In 2011 had de gemiddelde Facebookgebruiker 245 vrienden, terwijl de gemiddelde vriend op Facebook 359 vrienden had. Met andere woorden, de gemiddelde persoon op Facebook heeft minder vrienden dan zijn vrienden.
Dit fenomeen zie je ook bijvoorbeeld terug in de sportschool, waar het lijkt alsof iedereen om je heen beter in vorm is dan jijzelf. Dit is niet geheel verassend als je een doorsnee lid van de sportschool bent, omdat de mensen die het meest waarschijnlijk aan om te treffen in de sportschool ook de personen zijn die daar ook veel tijd doorbrengen.
Hoe het gemiddeld aantal vrienden van vrienden wordt geteld verdient enige uitleg. Stel dat een docent twee vakken geeft: één is een groot vak met 90 leerlingen en de ander is een klein vak met 10 leerlingen. Het is intuïtief om te zeggen dat de gemiddelde groepsgrootte gelijk is aan 50, namelijk \((90 + 10) / 2 = 50\). Dit is logisch vanuit het perspectief van de docent, maar ook enigszins misleidend. Als we kijken uit het oogpunt van de leerlingen, dan zit het overgrote deel van de studenten (90 van de 100) in een groep van 90, terwijl maar 10 leerlingen een groepgrootte van 10 ervaren. Vragen we dus aan iedere leerling hoe groot zijn klas is en tellen we al deze reacties bij elkaar op, dan is dat gelijk aan \((90 \times 90) + (1+ \times 10) = 8200\). Delen we dit door het totaal aantal studenten, dan is de groepgrootte die de studenten ervaren gemiddeld \(82\). Voor het gemiddeld aantal vrienden van vrienden gaan we op een vergelijkbare manier te werk. Aan elke persoon vragen we om van ieder van zijn of haar vrienden steeds de ‘score’ door te geven van hoeveel vrienden die heeft. Al deze getallen tellen we bij elkaar op en het gemiddeld aantal vrienden van vrienden verkrijgen we dan door dit aantal te delen door het totaal aantal ‘scores’ dat is doorgegeven. Dit levert een andere waarde op dan wanneer voor ieder individu het gemiddelde aantal vrienden van vrienden zou bepalen en daar vervolgens het gemiddelde over alle individuen van zou nemen.
Afbeelding 1.5: Een graaf van vrienden.
Een verklaring voor de vriendschapsparadox is dat iemand die veel vrienden heeft, vaak een vriend van iemand is. Dus in de berekening van het gemiddelde aantal vrienden van vrienden krikt deze populaire persoon het gemiddelde omhoog. De volledig wiskundige verklaring hiervoor is als volgt.
Stel we hebben een groep van \(n\) mensen en laten we zeggen dat persoon \(i\) precies \(k_i\) vrienden heeft. Het gemiddelde aantal vrienden in het gehele netwerken rekenen we eenvoudig uit met de formule \[\mu := \frac{1}{n} \sum_{i=1}^{n} k_i.\]
Het gemiddeld aantal vrienden van een vriend kunnen we modelleren door een willekeurige lijn uit de graaf te pakken (die een vriendschap voorstelt) en één van de eindpunten van de lijn (één van de vrienden), en daarvan de graad te berekenen. Het gemiddelde aantal vrienden van vrienden is dan gewoon het totaal aantal vrienden van vrienden gedeeld door het totaal aantal vrienden. Het totaal aantal vrienden van vrienden wordt gegeven door \[\sum_{i} (k_i)^2.\]
Het totaal aantal vrienden (in de noemer) is simpelweg \(\sum_{i=1}^n k_i,\) waardoor het gemiddelde aantal vrienden van vrienden gelijk is aan \[\frac{\sum_{i=1}^{n} (k_i)^2}{\sum_{i=1}^{n} k_i}.\]
We definiëren de variantie als \[\sigma^2 := \frac{1}{n}\sum_{i=1}^{n}(k_i - \mu)^2.\]
Manipuleren we bovenstaande vergelijking nu een beetje, dan zien we dat \[\sum_{i=1}^{n} (k_i)^2 = (\mu^2 + \sigma^2)n.\] Substitueren we deze uitdrukking in het gemiddelde aantal vrienden van vrienden, dan krijgen we \[\frac{\sum_{i=1}^{n} (k_i)^2}{\sum_{i=1}^{n} k_i} = \frac{(\mu^2 + \sigma^2)n}{\mu n} = \mu + \frac{\sigma^2}{\mu}.\] Merk op dat \(\frac{\sigma^2}{\mu} \geq 0\), waardoor we concluderen dat \[\text{gemiddeld aantal vrienden} = \mu \leq \mu + \frac{\sigma^2}{\mu} = \text{gemiddeld aantal vrienden van vrienden}.\]
Deze wiskundige analyse kan slim worden toegepast. Tijdens de uitbraak van de varkensgriep in 2009 hielden wetenschappers een groep willekeurig gekozen studenten in de gaten. Daarnaast controleerden ze ook de mensen die door deze deelnemers van het onderzoek werden gezien als vrienden. Opmerkelijk, de aangewezen vrienden werden ongeveer twee weken eerder ziek dan de willekeurig gekozen personen, waarschijnlijk omdat ze gemiddeld beter verbonden zijn. Dus voor diegenen die zich slecht voelen vanwege de grote populairiteit van hun vrienden, troost jezelf met de gedachte dat je vrienden sneller ziek zullen worden dan jij.