4 Scheve verdelingen en de rijken worden rijker

De netwerk modellen die we tot dusver hebben bekeken, de Erdős-Rényi grafen en het small-world model, hebben de volgende gemeenschappelijke eigenschap. Alle knopen in de netwerken hebben ongeveer evenveel buren. In echte netwerken is dit vaak niet het geval. In tegendeel, het aantal buren van knopen varieert ontzettend. Uit een commerciële studie uit 2012 over de demografie van Twitter gebruikers bleek bijvoorbeeld dat 81% van de Twitter gebruikers minder dan 50 volgers had, maar de twee meest gevolgde twitteraars, Katy Perry en Justin Bieber hebben beide meer dan 100 miljoen volgers! Op nummer drie volgt Barack Obama met 94 miljoen volgers. Dit is een voorbeeld van een scheve verdeling van het aantal buren van knopen, waar een klein aantal knopen een heel groot aantal buren heeft, terwijl de meeste knopen een klein aantal buren heeft.

Veel netwerken die door wetenschappers bestudeerd worden blijken deze eigenschap te hebben. Een heel ander voorbeeld is het route netwerk van vluchten tussen vliegvelden. Vanaf grote vliegvelden zoals Schiphol, London Heathrow, Chicago O’hare en Dubai International Airport kun je naar ontzettend veel verschillende bestemming vliegen, terwijl kleinere vliegvelden veel minder vluchten en bestemmingen aanbieden. In Afbeelding 4.1 zie je een kaart van een deel van het wereldwijde vliegverkeer.

Afbeelding 4.1: Een visualisatie van 54317 wereldwijde vliegroutes. Afbeelding via Wikipedia.

Andere voorbeelden van netwerken waarbij de verdeling van het aantal buren scheef is zijn onder andere eiwit interactie netwerken, het world Wide Web en citatie netwerken van wetenschappelijke artikelen. In dit hoofdstuk zullen we een netwerk model introduceren dat netwerken oplevert met een scheve verdeling voor de graad van de knopen. Vervolgens bekijken we hoe deze eigenschap de kwetsbaarheid van een netwerk beïnvloed.

4.1 Gerichte grafen

In de vorige hoofdstukken hebben we steeds grafen bestudeerd waarbij de relatie tussen knopen symmetrisch is. Oftewel als knoop A een relatie met knoop B heeft, dan heeft knoop B ook een relatie met knoop A. Voorbeelden van relaties met deze eigenschap zijn bijvoorbeeld vriendschap (hopelijk) in een sociaal netwerk, contact tussen dieren, de chemische reactie tussen eiwitten en kabel/wireless verbindingen tussen computers.

Niet alle netwerken hebben symmetrische relaties. In sommige netwerken zijn de relaties juist asymmetrisch. Bijvoorbeeld online sociale netwerken zoals Twitter en Instagram, waar gebruiker A een andere gebruiker B kan volgen zonder dat B gebruiker A volgt. Ook het World Wide Web, het netwerk van HTML pagina’s en hyperlinks, heeft asymmetrische relaties. Een website linkt naar een andere website, maar dit wil niet zeggen dat er ook een hyperlink terug bestaat. Tot slot is ook het netwerk van wetenschappelijke artikelen en citaties niet symmetrisch, een artikel verwijst naar eerder gepubliceerd werk. In dit speciale geval is het in principe onmogelijk om zowel een verbinding van artikel A naar B en van artikel B naar A te vinden, precies vanwege dit tijdsaspect.

Netwerken waar de relaties tussen knopen asymmetrisch zijn worden beschreven door gerichte grafen.

Definitie 4.1 Een gerichte graaf, \(G = (V,E)\), is een geordend paar van verzamelingen \(V\) en \(E\), waarbij \(V\) een eindige verzameling is en \(E\) een verzameling van geordende paren in \(V\).

In Afbeelding 4.2 zie je een voorbeeld van een gerichte graaf en de bijbehorende verzamelingen \(V\) en \(E\).

Afbeelding 4.2: Een gerichte graaf met knopen \(V = \{v_1, v_2, v_3, v_4, v_5\}\) en verbindingen \(E = \{(v_1,v_2), (v_1,v_3), (v_2,v_4), (v_3,v_4), (v_4, v_1), (v_4,v_5), (v_5, v_4)\}\).

Opgave 4.1 Een gerichte graaf heet samenhangend als de onderliggende graaf (waarbij je de richting van de lijnen vergeet) samenhangend is. Een gerichte graaf heet sterk samenhangend wanneer geldt dat er voor elk paar knopen \(x\) en \(y\) een gericht pad (een pad waarbij je de richting van de lijnen volgt) van \(x\) naar \(y\) bestaat en ook een gericht pad van \(y\) naar \(x\) bestaat.

1. Geef een voorbeeld van een gerichte graaf die samenhangend is maar niet sterk samenhangend.

2. Bewijs dat elke sterk samenhangende gerichte graaf ook samenhangend is.

Opgave 4.2 Knopen in gerichte grafen hebben een in-graad \(k^{in}_i\), het aantal inkomende lijnen, en een uit-graad, \(k^{uit}_i\), het aantal uitgaande lijnen. Geef de in-graad en uit-graad voor alle knopen in Afbeelding 4.2

Opgave 4.3 Laat \(G=(V,E)\) een gerichte graaf zijn. Een gerichte cykel is een pad \((v_1, v_2, \dots, v_l)\) waarbij \(v_l = v_1\) en \((v_i, v_{i+1}) \in E\) voor alle \(i\) met \(1 \leq i \leq l-1\). Een gerichte graaf heet acyclisch wanneer het geen gerichte cykels bevat. Welk van de hierboven besproken voorbeelden van gerichte netwerken is acyclisch en waarom?

4.2 De rijken worden rijker

In 1965 werd het artikel “Networks of Scientific Papers” gepubliceerd. In dit artikel wordt voor het eerst gesproken over de scheve verdeling van het aantal buren in een netwerk. Het netwerk dat bestudeerd werd is dat van wetenschappelijke artikelen en hun citaties. In deze gerichte graaf wijst een artikel naar alle artikelen die het citeert in voetnoten of de bibliografie. De auteur, Price, observeerde dat het aantal citaties dat een artikel krijgt een scheve verdeling volgt. Ongeveer 35% van alle wetenschappelijke artikelen wordt nooit geciteerd en 49% ontvangt slechts een enkele citatie. Slechts 1% van alle artikelen wordt vaker dan vijf keer geciteerd. Price vroeg zich af of een artikel dat reeds vaak geciteerd is, een grotere kans heeft om in de toekomst wederom geciteerd te worden. Dit is een voorbeeld van het fenomeen “de rijken worden rijker” wat eerder door de econoom Herbert Simon was gebruikt als een verklaring voor de scheve verdeling van rijkdom. Rijke mensen verdienen geld door het geld dat zij al hebben te investeren en de winst die zij hierdoor maken is evenredig met het bedrag dat zij investeren.

Dit principe lijkt inderdaad ook op te gaan voor wetenschappelijke artikelen. Hoe meer citaties een artikel heeft hoe zichtbaarder het is en hoe groter de kans dat het wederom geciteerd wordt. Price vermoedde dat de verdeling van het aantal citaties dat een artikel ontvangt wellicht een machtfunctie volgt van de vorm \(y \propto x^{-\alpha}\).

Afbeelding 4.3: Links een verdeling waarbij de meeste knopen ongeveer dezelfde graad hebben en waar geen knopen met hele hoge graad voorkomen. Rechts een machtsverdeling waarbij de meeste knopen weinig buren hebben, maar ook een aantal zeer hoge graad hebben.

Het volgende netwerk model dat we bespreken is geïnspireerd door het “de rijken worden rijker” principe en we zullen zien dat de verdeling van graden in de netwerken die dit oplevert een machtsfunctie volgt. Het is een voorbeeld van een evoluerend netwerk model: het netwerk verandert in discrete stappen. Voor netwerken is het “de rijken worden rijker” principe bekend als voorkeursverbinding (preferential attachment); knopen hebben een voorkeur om verbindingen te maken met knopen van hoge graad. Let op, we bespreken hier de ongerichte versie van het Barabási-Albert model aangezien dit de analyse vereenvoudigt.

Definitie 4.2 Het preferential attachment model van Barabási en Albert creëert een groeiende graaf \(G(t)\) op basis van een geheel getal \(m\) en een graaf \(G=(V,E)\) met \(|V| \geq m\). Op tijdstip \(t=0\) beginnen we met het netwerk \(G(0)=G\).

Groei: Op elk tijdstip \(t \geq 1\) wordt een nieuwe knoop aan het netwerk toegevoegd. Deze knoop krijgt exact \(m\) buren aan de hand van de volgende procedure.

Voorkeurs verbinding: De nieuwe knoop wordt verbonden met een bestaande knoop \(v\) met graad \(k\) in het netwerk waarmee het nog geen verbinding heeft met kans \[\Pi(k) = \frac{k}{\sum_i k_i}.\]

Dit gebeurt achtereenvolgens \(m\) keer, waarbij tussendoor steeds de graden worden geüpdatet. De sommatie in de noemer loopt hier dus over alle knopen in de graaf op tijdstip \(t-1\) waar de nieuwe knoop nog geen verbinding mee is aangegaan. Het herhaaldelijk toepassen van deze regels levert een graaf \(G(t)\) op voor iedere \(t > 0\).

Opgave 4.4 Laat \(G\) de graaf zijn met drie knopen \(v_1, v_2, v_3\) en drie lijnen \(\{v_1, v_2\}, \{v_1, v_3\}, \{v_2, v_3\}\).

1. Welke graaf ontstaat op tijdstip \(t=1\) wanneer we het Barabási-Albert model voor \(m=3\) en de bovenstaande graaf gebruiken.

2. En op t=2? (hier mag je de labels van de knopen even vergeten, en alleen naar de structuur van de graaf kijken)

3. Welke verschillende graaf structuren kunnen op t=3 ontstaan? Met welke kansen?

Opgave 4.5 De bovenstaande definitie is in feite niet helemaal correct.

1. Wat gebeurt er met knopen \(v \in V\) die op tijdstip \(t\) geen buren hebben?

2. Wat is het probleem met bovenstaande definitie?

Een manier om het probleem uit Opgave 4.5 op te lossen is door een positieve kans te introduceren dat een knoop met graad nul een connectie krijgt. We introduceren een constante \(a\) zodat verbindingen worden gemaakt met kans \(\Pi(k) = \frac{k + a}{\sum_i (k_i + a)}\). We kunnen deze kans interpreteren als een intrinsieke waarde van elke knoop; niet alleen knopen met buren hebben een kans om nieuwe verbindingen te maken, maar ook alle knopen zonder buren.

Afbeelding 4.4: Een graaf met 8 knopen.

Opgave 4.6 Laat \(G(0)\) de graaf zijn in Afbeelding 4.4. Reken voor iedere knoop de kans uit om een nieuwe buur te hebben op tijdstip \(t = 1\) voor \(m=1\), voor zowel \(a=0\) als \(a=1\).

Als we met het preferential attachment model een groot netwerk creëren, dus wanneer we een groot aantal stappen \(t \gg 0\) doen, dan kunnen we de verdeling van het aantal buren per knoop schatten. Er zijn verschillende manieren om deze schatting te maken. We gebruiken hier de master equation aanpak voor het model met \(a\) gelijk aan \(0\) en we nemen aan dat \(t\) dusdanig groot is dat alle knopen in \(G(t)\) ten minste \(m\) buren hebben. Eenzelfde redenatie kan worden gebruikt wanneer \(a > 0\), maar dit maakt de benodigde wiskunde iets ingewikkelder.

Opgave 4.7 Hoe kunnen we garanderen dat alle knopen minimaal graad \(m\) hebben voor alle \(t \geq 1\)?

Laat \(N_k(t)\) het verwachte aantal knopen zijn dat precies \(k\) buren heeft op tijdstip \(t\). Wat gebeurt er met \(N_k(t)\) wanneer we een nieuwe knoop introduceren op tijdstip \(t+1\)? The kans dat de nieuwe knoop een verbinding maakt met een bestaande knoop met graad \(k'\) is gelijk aan \(m \Pi(k') = m\frac{k'}{\sum_i k_i}\). De volgende vergelijking geeft het verwachte aantal knopen met precies \(k\) buren op tijdstip \(t+1\) wanneer \(k > m\), \[N_k(t+1) = N_k(t) + m \frac{k-1}{\sum_j k_j} N_{k-1}(t) - m \frac{k}{\sum_j k_j} N_{k}(t) \;\;\; \text{voor } k > m. \] We verwachten dat dit het aantal knopen is dat op tijdstip \(t\) graad \(k\) had, plus alle knopen die op tijdstip \(t\) graad \(k-1\) hebben en nu een verbinding hebben met de nieuwe knoop, min alle knopen die op tijdstip \(t\) graad \(k\) hadden en nu een verbinding hebben met de nieuw toegevoegde knoop.

Voor \(m=k\) krijgen we een net andere vergelijking: \[N_k(t+1) = N_k(t) + 1 - m \frac{k}{\sum_j k_j} N_{k}(t) \;\;\; \text{voor } k = m. \]

Opgave 4.8 Leg uit waarom we de bovenstaande vergelijking krijgen voor \(m=k\).

Om nu een schatting te maken van de graad verdeling voor \(t \gg 0\) gebruiken we de volgende schatting voor \(\Pi(k)\): \[\Pi(k) = \frac{k}{\sum_i k_i} \approx \frac{k}{2mt},\] want \[\sum_i k_i = 2(mt + m_0) \approx 2mt,\] waar \(m_0\) het aantal lijnen is in de graaf \(G=(V,E)\) waar we mee begonnen.

Opgave 4.9 In de bovenstaande schatting wordt gebruik gemaakt van het feit dat de som van de graden van knopen in een netwerk, gelijk is aan twee maal het aantal lijnen in een netwerk. Leg uit waarom dit het geval is.

Met de bovenstaande schatting kunnen we de master equations versimpelen, we vinden:

\[N_k(t+1) = N_k(t) + \frac{k-1}{2t} N_{k-1}(t) - \frac{k}{2t} N_{k}(t) \;\;\; \text{voor } k > m, \] \[N_k(t+1) = N_k(t) + 1 - \frac{k}{2t} N_{k}(t) \;\;\; \text{voor } k = m. \]

Als \(t\) groot genoeg is dan geldt \(N_k(t) \approx tP(k)\) waar \(P(k)\) de graadverdeling van het netwerk is. Verder geldt dat het aantal knopen in het netwerk gelijk is aan \(n = n_0 + t \approx t\), waar \(n_0\) het aantal knopen is in de graaf \(G=(V,E)\) waar we mee begonnen.

We vinden de volgende vergelijkingen:

\[(t+1)P(k) = tP(k) + \frac{k-1}{2} P(k-1) - \frac{k}{2} P(k) \;\;\; \text{for } k > m, \] \[(t+1)P(k) = tP(k) + 1 - \frac{k}{2} P(k) \;\;\; \text{for } k = m. \]

Opgave 4.10 (a) Laat zien dat we voor \(k > m\) de volgende vergelijking krijgen \[P(k) = \frac{k-1}{k+2} P(k-1).\]

2. Laat zien dat we voor \(k=m\) de volgende vergelijking krijgen \[ P(m) = \frac{2}{m+2} .\]

Door deze recursieve vergelijking herhaaldelijk toe te passen vinden we

\[P(k) = \frac{(k-1)}{(k+2)} P(k-1) = \frac{(k-1)(k-2)}{(k+2)(k+2)} P(k-2) \dots \] \[= \frac{(k-1)(k-2)\dots(m)}{(k+2)(k+1)\dots(m+3)} P(m)\] \[= \frac{(m+2)(m+1)m}{(k+2)(k+1)k} P(m)\] \[= \frac{2m(m+1)}{(k+2)(k+1)k}.\]

Voor grote waarden van \(k\) vinden we de machtsfunctie \(P(k) \propto k^{-3}\). Dit model van Barabási en Albert is erg beroemd geworden omdat het voor het eerst netwerken kon maken die net als reële netwerken een scheve verdeling van buren oplevert. Het model is net als het Erdös-Rényi model en het small-world model een benadering van echte netwerken en heeft niet exact dezelfde complexiteit als een echt netwerk. Maar met dit simpele model kunnen we bepaalde eigenschappen van echte netwerken verder onderzoeken. In de rest van dit hoofdstuk bekijken we de invloed van de graadverdeling op de kwetsbaarheid van een netwerk.

4.3 Grafen met gegeven graden

Het Barabási-Albert model dat we net besproken hebben levert grafen waarvan de graadverdeling voldoet aan een machtsverdeling. We kunnen echter van te voren niet precies bepalen welke graden met welke frequentie voorkomen in de resulterende graaf. We kunnen ook proberen om gegeven een rij van gehele getallen \((k_1, \dots, k_n)\), een netwerk te maken met \(n\) knopen zodat de knoop \(v_i\) precies graad \(k_i\) heeft.

Opgave 4.11 Teken een graaf met graden \((6,4,3,3,3,2,2,2,1)\).

Het is niet voor alle rijen gehele getallen \((k_1, \dots, k_n)\) mogelijk om een graaf te vinden met deze graden. Een rij gehele getallen heet grafisch wanneer dit wel mogelijk is. Zo is het bijvoorbeeld duidelijk dat de som \(\sum_i k_i\) van een grafische rij even moet zijn, aangezien de som van graden gelijk is aan twee keer het aantal lijnen in de graaf. De volgende stelling geeft een voorwaarde voor het grafisch zijn van een rij gehele getallen.

Stelling 4.1 Laat \(k_1 \geq k_2 \geq \dots \geq k_n\) een rij niet-negatieve gehele getallen zijn. Deze rij is grafisch dan en slecht dan als de som \(\sum_i k_i\) even is en \[\begin{equation} \sum_{i=1}^l k_i \leq l(l-1) + \sum_{i=l+1}^n \min(k_i,l) \tag{4.1} \end{equation}\] geldt voor alle \(l\) zodat \(1 \leq l \leq n\).

Opgave 4.12 In deze opgaven laten we zien dat de voorwaarde (4.1) in Stelling 4.1 nodig is voor een grafische rij.

1. Laat zien dat voor \(l=1\) de voorwaarde (4.1) versimpelt tot \(k_1 \leq n-1\) en leg uit waarom deze voorwaarde nodig is voor een grafische rij.

2. Versimpel de voorwaarde (4.1) voor \(l=n\) en leg uit waarom deze nodig is voor een grafische rij.

3. Laat nu zien waarom voorwaarde (4.1) nodig is voor elke \(l\). Hint: we tellen het aantal lijnen dat aan een knoop met hoge graad grenst dubbel. Deze lijnen grenzen aan twee knopen, ofwel beide met hoge graad, ofwel één met hoge graad en één met lage graad.
   

Het is moeilijker om te bewijzen dat de twee voorwaarden in Stelling 4.1 garanderen dat een rij grafisch is - het oorspronkelijke bewijs van Erdös en Gallai uit 1960 was lang en ingewikkeld. Inmiddels zijn er kortere bewijzen, maar daar gaan we verder niet op in.

We beschrijven nu het Havel-Hakimi algoritme. Dit algoritme maakt, gegeven een grafische rij, een netwerk met deze graden. Dit algoritme kan ook worden gebruikt om een constructief bewijs van Stelling 4.1 te geven.

Definitie 4.3 Laat \((k_1, k_2, \dots, k_n)\) een grafische rij zijn.

Begin met een graaf met \(n\) knopen en \(0\) lijnen.

1. Verbind knoop \(v_1\) met knoop \(v_2, \dots, v_{k_1 + 1}\).

2. Laat \(k'_i\) het aantal lijnen zijn wat knoop \(v_i\) nog mist. Oftewel \(k'_1 = 0\) en \(k'_i = k_i - 1\) voor \(2 \leq i \leq {k_1 + 1}\).

3. Sorteer de rij \(k'_i\) in aflopende volgorde en herhaal stappen 1 en 2 voor de nieuwe rij getallen \(k_i = k'_i\).

Stop zodra \(k_i = 0\) voor alle \(i\).

Afbeelding 4.5 geeft een klein voorbeeld voor dit algoritme.

Afbeelding 4.5: Het Havel-Hakimi algoritme voor de grafische rij (4,3,2,2,1,1,1).

Opgave 4.13 Gebruik het Havel-Hakimi algoritme om Opgave 4.11 te maken. Krijg je dezelfde graaf?

Dit algoritme resulteert altijd in dezelfde graaf. Wanneer we een ander netwerk met deze graden willen maken, kunnen we net als in het small-world model van Watts-Strogatz lijnen herverbinden. Als we genoeg lijnen herverbinden, dan vinden we uiteindelijk een willekeurig netwerk met de gegeven graden.

Opgave 4.14 Laat zien dat wanneer we lijnen \(\{x,y\}\) en \(\{u,v\}\) in een graaf verwijderen en vervangen door \(\{x,v\}\) en \(\{u,y\}\) (wanneer deze lijnen nog niet aanwezig zijn, en wanneer \(x \neq v\) en \(u \neq y\)), dat de graden van knopen \(x,y,u\) en \(v\) niet veranderen.

Afbeelding 4.6: Twee grafen met dezelfde rij graden.

Opgave 4.15 Bekijk de twee grafen in Afbeelding 4.6.

1. Geef een voorbeeld van een serie herverbindingen van lijnen zodat we de linker graaf veranderen in de rechter graaf.

2. Wat is het minimale aantal paren lijnen dat we moeten herverbinden om de linker graaf te veranderen in de rechter graaf?

4.4 Kwetsbaarheid van netwerken

Veel onmisbare onderdelen van onze maatschappij kunnen worden gezien als complexe netwerken: het Internet, telecommunicatie netwerken en het elektriciteitsnetwerk zijn een paar voorbeelden. In deze netwerken kan het gebeuren dat een knoop `uitvalt’: een computer die offline gaat, een zendmast die niet functioneert of een onderstation dat kapot is. Het is belangrijk dat het uitvallen van een klein deel van de knopen in deze netwerken geen groot effect heeft op het functioneren van het gehele netwerk.

Gelukkig zijn veel complexe netwerken verrassend tolerant als het gaat om het uitvallen van kleine onderdelen door fouten. De scheve verdeling van graden is door wetenschappers aangedragen als verklaring voor deze eigenschap. Netwerken met deze eigenschap zijn onverwacht robuust; knopen kunnen goed communiceren zelfs wanneer een onrealistisch groot deel van de knopen faalt. Deze fout tolerantie heeft echter wel een keerzijde. Deze netwerken zijn namelijk extreem kwetsbaar voor gerichte aanvallen. Afbeelding 4.7 laat zien hoe de grootte van de grootste samenhangende component van twee verschillende netwerken (één met homogene graadverdeling en één met scheve graadverdeling) verandert onder random falen van knopen en onder het verwijderen van knopen op volgorde van hoogste naar laagste graad (aanval).

Afbeelding 4.7: In beide plots zie je hoe de fractie van knopen die deel uitmaken van de grootste component verandert wanneer een groot deel van de knopen wordt verwijderd. De zwarte cirkels laten zien wat er gebeurt wanneer de knopen op willekeurige volgorde worden verwijderd, terwijl de rode cirkels overeenkomen met een aanval waar steeds de knoop met hoogste graad wordt verwijderd. Links een netwerk met homogene graadverdeling, rechts een netwerk met een machtsverdeling als graadverdeling.

Opgave 4.16 Leg uit hoe je uit Afbeelding 4.7 kan concluderen dat het netwerk met de scheve graadverdeling een hoge fout tolerantie heeft, maar gevoelig is voor gerichte aanvallen.

Is dit ook het geval voor het netwerk waar alle knopen ongeveer evenveel buren hebben?

Opgave 4.17 In week 2 hebben we gekeken naar het fenomeen percolatie. Om precies te zijn naar ‘lijn percolatie’. Het is ook mogelijk om ‘knoop percolatie’ te onderzoeken. Beschrijf `knoop percolatie’ en leg uit hoe dit gerelateerd is aan de bovenstaande resultaten over netwerk kwetsbaarheid. (Kijk nog eens naar week 2, onderdeel 2.4)

Bonusopgave 4.1 (technische uitdaging van de week) Een topologische sortering van een gerichte graaf \(G\) is een sortering van de knopen \(v_1, \dots, v_n\) zodanig dat voor alle gerichte lijnen \((v_i, v_j) \in E\) geldt dat \(i > j\). Laat \(G\) een gerichte graaf zijn met \(n\) knopen en met topologische sortering \(v_1, \dots, v_n\).

1. Laat zien dat \(G\) een acyclische graaf is. Zie Opgave 4.3 voor de definitie van een acylcische graaf.

2. Teken een acyclische graaf met 10 knopen en label de knopen met een topologische sortering. Hint: teken de knopen zodanig dat alle gerichte lijnen in dezelfde richting wijzen.

3. Schrijf een programma dat een topologische ordering vind voor een gerichte acyclische graaf.

4. Test je programma op een paar zelfgemaakte netwerken.

Bonusopgave 4.2 (creatieve uitdaging van de week) Knoop percolatie (zie Opgave 4.17) kan worden gebruikt om een bosbrand te simuleren. Maak een animatie van een bosbrand, waarbij de knopen bomen zijn, en de lijnen overeenkomen met bomen waartussen brand kan overspringen.