3 Een kleine wereld

In 1967 deed de beroemde socioloog Stanley Milgram onderzoek naar het zogeheten Small World fenomeen. Je hebt vast wel eens een situatie als de volgende meegemaakt. Je bent op een feestje en raakt aan de praat met iemand die je niet eerder hebt ontmoet. Na een tijdje met deze persoon in gesprek te zijn geweest kom je erachter dat jullie een gemeenschappelijke kennis hebben en merken jullie op wat het toch een kleine wereld is. Stanley Milgram wilde achterhalen hoeveel kennissen er gemiddeld nodig zijn om twee willekeurige Amerikanen met elkaar te verbinden via kennissen.

Om dit te achterhalen voerde hij het volgende experiment uit. Hij stuurde een groep mensen een informatiepakket met daarin een uitleg van de studie, een omschrijving van een persoon in Boston, kaartjes geadresseerd aan Harvard, een namenlijst en de volgende opdracht. De ontvanger moest haar naam aan de lijst toevoegen, een kaartje naar Harvard sturen en vervolgens het informatiepakket doorsturen. Als zij de persoon in Boston persoonlijk kent, dan stuurt zij het pakket direct naar deze persoon. Als dit niet het geval is dan stuurt zij het pakket naar een persoonlijke kennis waarvan ze denkt dat deze `dichterbij’ de persoon in Boston is. Een groot aantal van de pakketen kwam nooit aan, maar de pakketen die de bestemming wel bereikten hadden gemiddeld 5.9 stappen nodig om bij de persoon in Boston te worden bezorgd. Het onderzoek van Milgram heeft bijgedragen aan de acceptatie van het populaire idee 6 degrees of seperation: dat alle personen ter wereld verbonden zijn via 6 stappen van “vriend van vriend” relaties.

Opgave 3.1 The WikiGame is een spel waarbij je probeert via een zo kort mogelijk pad van een artikel naar een andere artikel te navigeren op Wikipedia. Wat zijn de knopen en de verbinding in dit netwerk? Wat valt je op aan de padlengtes die je op deze manier vind?

In zowel de WikiGame als het experiment van Milgram zoek je een pad zonder kennis te hebben van het gehele netwerk. Je hebt waarschijnlijk opgemerkt dat dit resulteert in paden die langer zijn dan het kortste pad tussen twee knopen. De volgende opgaven gaan over de kortste paden in netwerken.

Opgave 3.2 Binnen de wiskunde gemeenschap kun je indruk maken met een laag Erdős nummer. Paul Erdős was een Hongaarse wiskundige, die onder andere onderzoek deed naar random netwerken (zie vorig hoofdstuk). Zoek uit wat een Erdős nummer is. Welke relatie tussen personen wordt hier gebruikt? Verwacht je dat deze relatie in langere of kortere paden resulteerd dan vriendschap relaties?

Opgave 3.3 Vind acteurs met Bacon nummer twee en drie. Je kunt hiervoor deze website gebruiken.

3.1 Clusters en pad lengte

In het vorige hoofdstuk hebben we onder andere Erdős-Rényi random netwerken bestudeerd. In deze netwerken zijn knopen willekeurig met elkaar verbonden. In de volgende opgave zullen we zien dat het voor Erdős-Rényi netwerken niet zo vreemd is om korte paden te vinden.

Opgave 3.4 Laat $G(n,p)$ een Erdős-Rényi random netwerk zijn met $n$ knopen en elk paar knopen $u$ en $v$ heeft kans $p$ om met elkaar verbonden te zijn.

Laat $v$ een willekeurige knoop in het netwerk zijn. Hoeveel buren verwacht je dat $v$ heeft? (Druk dit uit in $n$ en $p$).
Als we mogen aannemen dat $p$ dusdanig klein is dat er geen overlap is tussen de buren van de buren van $v$, hoeveel verschillende buren van buren verwacht je dat $v$ in totaal heeft? (Druk dit uit in $n$ en $p$)
Hoeveel knopen kan $v$ bereiken in maximaal twee stappen?
Laat n=1000 en p=0.01, gebruik je antwoorden voor vraag (a) en (b) om een schatting te geven van het aantal knopen dat in 1 stap kan worden bereikt en in 2 stappen.

De vorige opgave laat zien dat het aantal knopen dat we kunnen bereiken in een Erdős-Rényi random netwerk snel groeit met het aantal stappen dat we nemen. Voor deze netwerken is het dus niet zo verrassend dat er sprake is van korte afstanden tussen elk paar punten. Hier namen we steeds aan dat er geen overlap bestond tussen de buren van een knoop en de buren van de buren van een knoop. In een sociaal netwerk betekent dit dat we aan zouden nemen dat voor iedereen, dus bijvoorbeeld voor jou, geldt dat de vrienden van jouw vrienden geen vrienden zijn van jou.

De aanname in Opgave 3.4 dat er geen overlap is tussen de buren van een knoop en de buren van de buren van een knoop lijkt voor een sociaal netwerk niet te kloppen. In feite verwacht je juist veel overlap tussen jouw vrienden en de vrienden van jouw vrienden, aangezien mensen vaak vriendengroepen vormen.

Opgave 3.5 Met hoeveel van jouw vrienden, deel je geen enkele vriend? Wat gebeurt er met het aantal verschillende buren van buren van $v$ in Opgave 3.4 in een sociaal netwerk?

Het Erdős-Rényi random netwerk model heeft net als veel echte netwerken korte kortste paden tussen alle knopen, maar mist een andere belangrijke eigenschap van reële netwerken: alle lijnen zijn willekeurig geplaatst, maar in een echt netwerk vormen lijnen vaak clusters. Hiermee bedoelen we precies dat er vaak verbindingen zijn tussen de buren van een knoop. Om deze netwerkeigenschappen te kwantificeren introduceren we de volgende twee definities: diameter en de cluster coëfficiënt.

Definitie 3.1 Laat $G=(V,E)$ een netwerk zijn met knopen $u, v \in V$. We definiëren $l(u,v)$ als de lengte van het korste pad tussen $u$ en $v$. Met andere woorden, als $P$ de verzameling van paden tussen $u$ en $v$ is, dan is $l(u,v)$ als volgt gedefiniëerd: $l(u,v) = \min_{p \in P} |p|$. Als er geen pad bestaat tussen knoop $u$ en $v$, dan zeggen we dat de $l(u,v)$ oneindig is.

Opgave 3.6 Welke eigenschap van een netwerk $G=(V,E)$ garandeert dat voor alle paren van knopen $u,v \in V$ geldt dat $l(u, v) < \infty$ (Hint: kijk nog eens naar Hoofdstuk 1).

Definitie 3.2 De diameter $d$ van een netwerk $G=(V,E)$ is de gemiddelde lengte van het kortste pad tussen twee knopen, genomen over alle paren van knopen in het netwerk. Met andere woorden $d = \frac{2}{n(n-1)}$ $\sum_{v_i \neq v_j}^{} l(v_i, v_j)$.

Opgave 3.7 In de definitie van de diameter delen we door $\frac{n(n-1)}{2}$, waar $n$ zoals gebruikelijk staat voor het aantal knopen in $G$. Leg uit waar $\frac{n(n-1)}{2}$ voor staat in deze definitie (Definitie 3.2).

Afbeelding 3.1: Drie grafen.

Opgave 3.8 Reken de diameter uit van de grafen in Afbeelding 3.1.

De volgende definitie die we introduceren zegt iets over de mate waarin buren verbonden zijn.

Definitie 3.3 Laat $v$ een knoop in een netwerk zijn met graad $k_v$. Er zijn maximaal $\frac{k_v(k_v-1)}{2}$ lijnen tussen de buren van $v$. We definiëren de lokale cluster coëfficiënt $C_v$ van een knoop $v$ als de fractie van lijnen tussen de buren van $v$ die aanwezig zijn. De cluster coëfficiënt $C$ is het gemiddelde van $C_v$ voor alle knopen $v$ in het netwerk. Wanneer een knoop slechts één buur heeft, m.a.w. als $k_v = 1$, dan zeggen we dat $C_v$ gelijk is aan 1.

Afbeelding 3.2: Een graaf met cluster coëfficiënt $C = 0.772$

Voorbeeld 3.1 De graaf in Afbeelding 3.2 heeft cluster coëfficiënt $C = 0.772$. Knoop $v_1$ heeft graad $5$ en er zijn precies drie lijnen tussen de buren van $v_1$. Dus de lokale cluster coëfficiënt $C_{v_1}$ is gelijk aan $\frac{3}{10}$ en knoop $v_1$ draagt $\frac{1}{6} \frac{3}{10} = 0.05$ bij aan $C$.

Opgave 3.9 Reken de overige lokale cluster coëfficiënten uit voor de knopen $v_2, \dots, v_6$ van de graaf in Afbeelding 3.2. Ga na dat $C$ inderdaad gelijk is aan $0.772$.

3.2 Het small-world model

In 1998 introduceerden Duncan J. Watts en Steven H. Strogatz een nieuw netwerk model, het zogenaamde small-world netwerk model. De vraag die zij met dit model wilden beantwoorden was de volgende: hebben grafen met een korte padlengte, dat wil zeggen met een lage waarde voor $d$, altijd een lage waarde voor $C$ zoals het geval is voor Erdős-Rényi grafen?

Tegelijkertijd kenden zij al een klasse grafen met lange kortste paden en veel clusters, de ring roosters. Oftewel met hoge waarde voor $d$ en hoge waarde voor $C$. Zijn de waarde voor $d$ en $C$ altijd allebei laag of allebei hoog, of zijn er ook grafen waarvoor dit niet het geval is.

Om deze vraag te beantwoorden bekijken we eerst de klasse van ring rooster grafen. Vervolgens zullen we het small-world netwerk model bespreken. Dit model levert netwerken op die qua structuur ergens tussen ring roosters en Erdős-Rényi netwerken leven.

Definitie 3.4 Een ring rooster met $n$ knopen met graad $k = 2l$ en $l > 0$ is een graaf waarin de knopen op een ring gepositioneerd zijn zodat elke knoop graad $k$ heeft en verbonden is met zijn $k$ dichtsbijzijnste buren.

Afbeelding 3.3: Vier ring roosters met van links naar rechts $(n,k)$ gelijk aan $(7,2)$, $(7,4)$, $(9,4)$ en $(13,6)$.

Opgave 3.10 a. Reken de clustering coëfficiënt $C$ uit van de ring roosters in Afbeelding 3.3.

Wat valt je op?
Geef een formule voor de clustering coëfficiënt van ring roosters met willekeurige $n$ en $k = 4$. Geldt dit voor alle $n$? (Hint: kijk ook eens naar $n=8$ en $n=10$).
Geef een algemene formule voor de clustering coëfficiënt van ring roosters met willekeurige $n$ en willekeurige $k$. Je mag aannemen dat $n > 3l$.

Opgave 3.11 a. Reken de diameter $d$ uit voor de ring roosters in Afbeelding 3.3.

Geef een formule voor $d$ van ring roosters met willekeurige $n$ en $k = 2$.

Het small-world netwerk model van Watts en Strogatz creëert grafen gebaseerd op een ring rooster voor een parameter $0 \leq p \leq 1$. Wanneer $p$ gelijk is aan $0$ dan is de graaf een rooster ring, en wanneer $p$ gelijk is aan $1$ dan lijkt de graaf erg op een Erdős-Rényi graaf.

Definitie 3.5 Laat $n$ een geheel getal zijn en $k$ een even getal zijn kleiner dan $n$. Laat $p$ een reëel getal zijn tussen $0$ en $1$. We definiëren de small-world graaf $G_{SW}(n,k,p)$ als de graaf verkregen via het volgende proces:

Construeer het ring rooster met $n$ knopen met ieder graad $k$.
Herverbind elke lijn met kans $p$.

Bovenstaande definitie is niet helemaal compleet, aangezien het niet duidelijk is wat we met herverbinden bedoelen. Het idee is dat we een gegeven lijn met kans $p$ verwijderen uit het netwerk en op een andere plek toevoegen. Dit kan op verschillende manieren worden gedaan. Voor het vervolg van dit hoofdstuk is het niet belangrijk om te weten hoe dit precies wordt gedaan.

$Deze grafiek laat zien hoe de diameter en de cluster coëfficient van het ring rooster met $n=1000$ en $k=10$ veranderen als we lijnen met kans $p$ herverbinden. De witte cirkels geven de waarde van $\frac{C(p)}{C(0)}$ weer, waar $C(0)$ de cluster coëfficiënt van het ring rooster is. De zwarte vierkanten geven de waarde van $\frac{d(p)}{d(0)}$, met $d(0)$ de diameter van het ring rooster.$

Afbeelding 3.4: Deze grafiek laat zien hoe de diameter en de cluster coëfficient van het ring rooster met $n=1000$ en $k=10$ veranderen als we lijnen met kans $p$ herverbinden. De witte cirkels geven de waarde van $\frac{C(p)}{C(0)}$ weer, waar $C(0)$ de cluster coëfficiënt van het ring rooster is. De zwarte vierkanten geven de waarde van $\frac{d(p)}{d(0)}$, met $d(0)$ de diameter van het ring rooster.

De grafiek in Afbeelding 3.4 laat zien dat bij het herverbinden van slechts een kleine fractie van de lijnen, de diameter $d(p)$ snel afneemt. De clustercoëfficiënt daarentegen verandert in het begin nagenoeg niet.

Dit model mag dus met recht een small-world model heten, de term wordt sinds de introductie van dit model geassocieerd met netwerken die zowel een hoge clustercoëfficiënt hebben als een korte padlengte. Naast sociale netwerken blijken veel andere netwerken ook de small-world eigenschap te hebben. Zo lieten Watts en Strogatz al zien dat het neurale netwerk van C. Elegans (zie ook Hoofdstuk 1) en ook de graaf van het elektriciteitsnetwerk van het westen van de Verenigde Staten de small-world eigenschap hebben. Dit blijkt een hele algemene eigenschap voor netwerken. Het simpele model van Watts en Strogatz kan worden gebruikt om bepaald gedrag van processen op netwerken te bestuderen en in het bijzonder hoe dit gedrag verandert wanneer de diameter kleiner wordt.

Bonusopgave 3.1 (technische uitdaging van de week)

Bepaal het kortste pad van knoop 1 naar knoop 15 in de graaf in Afbeelding 3.5. Houdt hierbij rekening met de afstand van elke lijn. Het kortste pad tussen knoop 3 en knoop 7 is bijvoorbeeld via knoop 4 en heeft afstand 8.
Schrijf een programma dat het kortste pad kan vinden in een gewogen graaf (een graaf waarbij elke lijn een gewicht/afstand heeft). Test dit programma voor het netwerk in Afbeelding 3.5. Hint: zoek eens naar het Dijkstra algoritme.
Stel een postbezorger moet langs iedere knoop in de graaf in Afbeelding 3.5 om post te bezorgen. Wat is hiervoor kortste route die begint en eindigt in knoop 1?

Afbeelding 3.5: Een gewogen graaf, elke lijn heeft een lengte.

Bonusopgave 3.2 (creatieve uitdaging van de week)

Maak een animatie van het small-world model. Gebruik hiervoor de volgende strategie om lijnen te herverbinden.

Kies twee willekeurige lijnen in het netwerk: $\{x,y\}$ en $\{u,v\}$. Als de lijnen $\{x,v\}$ en $\{u,y\}$ nog niet bestaan, doe dan het volgende. Verwijder de lijnen $\{x,y\}$ en $\{u,v\}$ en voeg de lijnen $\{x,v\}$ en $\{u,y\}$ toe. Als de lijnen al wel bestaan doe dan niks. Herhaal deze stap.