De Statistische Analyse van Netwerken

De Statistische Analyse van Netwerken Rodel van Rooijen 15 juli 2014 Bachelorscriptie Begeleiding: prof. dr. J.H. (Harry) van Zanten

Korteweg-De Vries Instituut voor Wiskunde Faculteit der Natuurwetenschappen, Wiskunde en Informatica Universiteit van Amsterdam

Samenvatting Het modelleren van netwerken zorgt voor het beter begrijpen van veel dingen in ons hedendaags leven. Zonder er vaak kennis van te hebben bevinden dit soort netwerken zich overal om ons heen. Het bestuderen van netwerken verbreedt bijvoorbeeld ons begrip van het internet, transportnetwerken, sociale netwerken en de verspreiding van ziektes. In deze scriptie worden daarom een aantal statistische netwerkmodellen behandeld en zal in het bijzonder gefocust worden op één netwerkmodel namelijk het exponentiële random graaf model. Verder zullen er statistische methoden gebruikt worden om het model toe te kunnen passen in de praktijk. Een van deze methoden gebruikt een zogenaamd Monte Carlo Markovketen algoritme dat zelfs in de meest gecompliceerde gevallen een benadering kan geven van de ware parameters van het model. Na het behandelen van deze methoden voor het algemene model zal er nog een praktische toepassing gegeven worden.

Titel: De Statistische Analyse van Netwerken Auteur: Rodel van Rooijen, [email protected], 10184023 Begeleiding: prof. dr. J.H. (Harry) van Zanten Einddatum: 15 juli 2014 Korteweg-De Vries Instituut voor Wiskunde Universiteit van Amsterdam Science Park 904, 1098 XH Amsterdam http://www.science.uva.nl/math

2

Inhoudsopgave 1. Inleiding

4

2. Een introductie tot netwerken 2.1. Wat is een netwerk? . . . . . . . . 2.1.1. Sociale netwerken . . . . . . 2.1.2. Informatienetwerken . . . . 2.2. Waarom bestuderen we netwerken?

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

6 6 6 8 10

3. Grafentheorie en de exponenti¨ ele familie van verdelingen 12 3.1. Grafentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2. De exponentiële familie van verdelingen . . . . . . . . . . . . . . . . . . . 13 3.2.1. De meest aannemelijke schatter . . . . . . . . . . . . . . . . . . . . 14 4. Netwerk modellen 4.1. Het Erd˝ os-Rényi-Gilbert random graaf 4.2. Het stochastische blokmodel . . . . . . 4.2.1. Gegroepeerde netwerken . . . . 4.3. Het exponentiële random graaf model

model . . . . . . . . . . . .

. . . .

. . . .

. . . .

5. Maximum likelihood op het exponenti¨ ele random 5.1. De Monte Carlo Markovketen . . . . . . . . . . . . 5.2. De benadering van de meest aannemelijke schatter 5.2.1. Het benaderen van de log-likelihood functie 5.2.2. Het genereren van een steekproef . . . . . . 5.2.3. De normalisatiefactor . . . . . . . . . . . . 5.3. Convergentie naar evenwicht . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

graaf . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

17 17 17 18 20

model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

22 22 23 23 25 27 27

. . . .

. . . .

. . . .

. . . .

6. Een toepassing van het exponenti¨ ele random graaf model 29 6.1. Het complexe hersennetwerk model . . . . . . . . . . . . . . . . . . . . . . 29 7. Conclusie

32

Bibliografie

33

A. Appendix

35

B. Populaire samenvatting

38

3

1. Inleiding Sinds ik begonnen ben aan mijn studie wiskunde aan de Universiteit van Amsterdam (UvA) ligt mijn interesse vooral bij de stochastiek (kansrekening en statistiek). In het eerste jaar was er tevens een vak dat ging over grafentheorie dat mij erg aansprak. Toen ik een scriptie onderwerp moest kiezen wilde ik allereerst gaan kijken of ik iets met toegepaste stochastiek kon doen. Al snel werd ik in de richting van prof. dr. Harry van Zanten gestuurd en niet zonder succes, al snel stelde hij mij een onderwerp voor dat ging over netwerken. In dit onderwerp zou ik de stochastiek en de grafentheorie perfect kunnen combineren en zelfs in toegepaste zin, daarmee was mijn keuze snel gemaakt. Niet alleen dit maakt het een heel interessant onderwerp, want er valt namelijk veel over te zeggen. Netwerken liggen aan het fundament van de hedendaagse samenleving, bijvoorbeeld het sociale netwerk Facebook en het internet in de vorm van het World Wide Web hebben een prominente positie ingenomen. Allereerst zullen we in het kort de volgende vraag beantwoorden: ”Wat is een netwerk?”. In hoofstuk 2 zal deze vraag in detail beantwoordt worden, kort gezegd is een netwerk een verbonden geheel waar vaak mensen of dingen centraal staan. Voorbeelden van netwerken die onmisbaar zijn in ons dagelijks leven zijn bijvoorbeeld de sociale netwerken waarbij vriendschapsrelaties centraal zijn, maar ook een informatienetwerk zoals het internet is een kenmerkend voorbeeld. Het bestuderen van dit soort netwerken zou dus kunnen helpen bij het beter begrijpen van veel aspecten die deel uitmaken van ons dagelijks leven. Maar niet alleen netwerken die we vaak tegenkomen zijn interessant om te bestuderen. Netwerken van de verspreiding van ziektes en marketingmodellen zijn andere voorbeelden die tevens interessant zijn om te bekijken. In hoofdstuk 2 en 3 zullen we zien dat in het algemeen netwerken weergegeven kunnen worden als grafen. Bij het bekijken van netwerken bekijken we dus eigenlijk de achterliggende netwerkgraaf. In een netwerkgraaf representeren de punten entiteiten of dingen in een netwerk en zijn de relaties tussen punten gegeven door de lijnen van de graaf. Als we netwerken bestuderen bekijken dus eigenlijk de achterliggende grafen. Een manier om deze netwerken te bestuderen is door gebruik te maken van statistische modellen. In een statistisch model zoeken we een formele representatie van een onderliggend stochastisch proces. Dit wordt vaak gedaan door een model te selecteren in de vorm van een kansverdeling en dan door middel van observaties de parameter(s) in het model schatten. Deze methode van modelleren geeft de mogelijkheid om algemene eigenschappen te bekijken van netwerken zoals de verbondenheid en clustering van een netwerk.

4

Een andere reden waarom het voor de hand ligt om voor een statistische benadering te kiezen is, omdat al bestaande statistische methoden en technieken dan toegepast kunnen worden. De modellen die bekeken gaan worden liggen op het grensgebied van de grafentheorie en de stochastiek en worden vaak random graaf modellen genoemd. Het random aan deze grafen is dat deze afhankelijk zijn van een kansverdeling. In hoofdstuk 3 zal er allereerst een stuk theorie behandeld worden dat nodig is om in hoofdstuk 4 voorbeelden te geven van dit soort statistische netwerkmodellen. In deze scriptie zullen we één netwerkmodel in detail gaan behandelen namelijk het exponentiële random graaf model. De benadering van de ware parameter(s) in het model is niet in alle gevallen even makkelijk en daarom zal er in hoofstuk 5 een methode gegeven worden om deze toch in alle gevallen te kunnen benaderen. In de praktijk wordt dit model veel toegepast en daarom zal er een praktische toepassing van het model behandeld worden in hoofdstuk 6. Deze scriptie wordt daarna afgesloten met een terugblik en eventueel verdere onderzoeksmogelijkheden. Verder wil ik nog mijn begeleider Harry van Zanten hartelijk bedanken voor het voorstellen van dit interessante onderwerp en zijn inbreng in deze scriptie. Rodel van Rooijen juli 2014

5

2. Een introductie tot netwerken Ter introductie zullen we in dit hoofdstuk een paar kernvragen rond netwerken behandelen zoals: ”Wat is een netwerk?”, ”Welke soorten netwerken zijn er?” en ”Waarom bestuderen we netwerken?”. Voordat we namelijk kunnen beginnen met het analyseren van netwerken zullen we eerst moeten bekijken wat het begrip netwerk precies inhoudt. Om daarna een beter begrip te krijgen waar deze netwerken voorkomen zullen we deze in categoriën verdelen en zullen er voorbeelden gegeven worden. We beantwoorden tevens de vraag waarom het bekijken van deze netwerken zo interessant is.

2.1. Wat is een netwerk? Een netwerk is een geheel van verbonden punten waarbij deze punten opgevat kunnen worden als entiteiten of dingen. In een netwerk zijn twee punten verbonden met elkaar als er een connectie bestaat tussen deze punten. Deze connecties hebben vaak verschillende betekenissen, bij mensen zijn bijvoorbeeld de connecties vaak van sociale aard. Indien er gekeken word naar bijvoorbeeld webpagina’s zijn de connecties vaak van informatieve aard, daarom zullen we in het vervolg onderscheid gaan maken tussen verschillende soorten connecties. In het bijzonder kunnen netwerken in verschillende categoriën worden opgedeeld aan de hand van de betekenis van de connecties in een netwerk. In dit hoofdstuk worden in het bijzonder twee categoriën bekeken en worden deze met voorbeelden ge¨ıllustreerd. Toch zijn deze categoriën niet bindend en kunnen netwerken in verschillende categoriën simultaan voorkomen.

2.1.1. Sociale netwerken Een interessante voor de hand liggende categorie van netwerken om te bekijken zijn de sociale netwerken, deze bevinden zich namelijk overal om ons heen. In een sociaal netwerk gaat het vooral om de sociale interactie tussen mensen en soms tussen dieren. Een eenvoudig voorbeeld van een sociaal netwerk is een vriendschapsnetwerk, waarbij mensen in een netwerk verbonden zijn als er een vriendschapsrelatie bestaat. Andere voorbeelden van sociale netwerken naast vriendschapsrelaties zijn bijvoorbeeld handelsverdragen, co-auteurschap in wetenschappelijke artikelen en de alliantie tussen bedrijven. Onderzoek naar sociale netwerken wordt al sinds omstreeks 1930 [8] gedaan en de ontwikkeling van de sociogram wordt vaak gezien als het startpunt. Een sociogram is een

6

visuele weergave van een sociaal netwerk in de vorm van een graaf. Uiteraard zijn niet alleen deze netwerken weer te geven als graaf en daarom zullen we later zien dat dit voor elk netwerk mogelijk is. Een klassiek voorbeeld van een onderzoek dat gedaan is naar sociale netwerken is het Small-World Problem [9]. In dit experiment moest een brief verzonden worden naar een specifiek persoon onder de regel dat de brief alleen doorgestuurd mocht worden naar kennissen. Als resultaat werd bevonden dat de keten van kennissen tussen twee mensen een mediaan heeft van zes. Dit onderzoek is in 2011 herhaald met de beschikbare data van het online sociale netwerk Facebook [10] en leverde een gemiddelde op van 3.74 vrienden tussen twee mensen op het netwerk. Netwerken hoeven uiteraard niet altijd een grote omvang te hebben, er bestaan ook kleinschaligere netwerken die bestudeerd zijn daarom bekijken we nu het volgende voorbeeld. Voorbeeld 2.1 (Zachary’s ’karate club’ netwerk [11]). Aangezien een netwerk bestaat uit een verzameling van punten en connecties kan een netwerk weergegeven worden als een graaf, connecties kunnen gezien worden als lijnen tussen punten. In dit voorbeeld worden de vriendschappen in kaart gebracht binnen een karate club en weergegeven als graaf.

Figuur 2.1.: Het karatenetwerk weergegeven als graaf. De verschillende vormen van de punten staan voor de subgroepen die zich vormen rond

7

persoon a1 en persoon a34. De connecties binnen de graaf staan voor vriendschappen tussen twee personen. De kleuren blauw en rood geven respectievelijk de connecties aan binnen de bovenste en onderste subgroep en de kleur geel geeft de connectie aan tussen personen van verschillende subgroepen. In volgende hoofdstukken zullen methodes bekeken worden om grafen van netwerken te modelleren. Wellicht een bekender voorbeeld in de wetenschappelijke wereld is het volgende voorbeeld. Voorbeeld 2.2 (Erd˝ osgetal). Een bekender voorbeeld van een sociaal netwerk is het netwerk gebaseerd op het Erd˝ osgetal. Dit Erd˝osgetal geeft de samenwerkingsafstand in wetenschappelijke artikelen tussen een auteur en Erd˝os en is gedefiniëerd als volgt • Paul Erd˝ os zelf heeft Erd˝ osgetal 0, • Het Erd˝ osgetal van elke andere auteur X is 1 hoger dan het kleinste Erd˝osgetal van alle auteurs met wie X ooit een artikel heeft gepubliceerd, • Indien geen van de auteurs met wie X ooit een artikel heeft gepubliceerd, een eindig Erd˝ osgetal heeft, heeft het Erd˝osgetal van X een waarde van oneindig. Door middel van dit Erd˝ osgetal en het netwerk dat zich hierdoor vormt wordt dus als ware het netwerk van co-auteurschap vastgelegd met als startpunt Paul Erd˝os zelf.

2.1.2. Informatienetwerken We leven in een tijd waarbij het verkrijgen van informatie een belangrijke rol speelt. Een van de belangrijkste en meest gebruikte bronnen van informatie is het internet, iets preciezer benoemd is dit het World Wide Web (WWW). In het netwerk dat ontstaan is door het WWW zijn de punten gegeven door webpagina’s en de connecties door referentie’s tussen deze pagina’s. In zijn geheel is het WWW een zéér groot informatienetwerk en wel een van de grootste informatienetwerken dat vandaag de dag bestaat. Toch is dit niet het enige informatienetwerk dat interessant is om te bekijken en zijn deze net als de sociale netwerken overal te vinden. Vooral na de komst van het internet zijn er veel andere nieuwe informatienetwerken in het leven geroepen. Zoals eerder gezegd zijn de informatienetwerken voortgekomen uit het internet niet de enige netwerken in deze categorie. Andere voorbeelden zijn netwerken die semantische relatie’s tussen woorden aangeven (synoniemen, antonumen, etc.), netwerken van citatie’s tussen wetenschappelijke artikelen en ook behoren de netwerken van co-auteurschap van wetenschappelijke artikelen tot deze categorie. We zien dus dat deze categoriën niet strict zijn aangezien het laatste voorbeeld ook in de categorie sociale netwerken geplaatst kon worden. Onderzoeken die gedaan zijn naar informatienetwerken gaan vaak over de structuur van het netwerk, zoals welk punt verbonden is door het meeste aantal lijnen. Bijbehorende vragen zijn bijvoorbeeld: ”Welke webpagina heeft wordt het meest gerefereerd?”

8

of ”Welke wiskundige artikel is het meest geciteert?”. Andere onderzoeken gaan vaak over het in kaart brengen van informatienetwerken, wat in de meeste gevallen een niet gemakkelijke taak is gezien de omvang van sommige netwerken. Voorbeeld 2.3 (Peer-to-peernetwerken). Een peer-to-peernetwerk is een informatienetwerk waarin computers direct met elkaar verbonden zijn zonder dat een centrale server hiervoor nodig is. Belangrijke voorbeelden van peer-to-peernetwerken zijn de uitwisselingsnetwerken waarbij gratis en anoniem bestanden gedeeld kunnen worden over het internet. Een van de grootste en meest gebruikte uitwisselingsnetwerken ontstaan door het internet is BitTorrent. In 2009 was BitTorrent verantwoordelijk voor ongeveer 43% tot 70% [12] van al het internetverkeer afhankelijk van geografische locatie. Een ander voorbeeld van een peer-to-peernetwerk is het netwerk ontstaan door het computervirus ZeuS. In dit netwerk werden computers voornamelijk onvrijwillig ge¨ınfecteerd met het virus dat ervoor zorgde dat die computers op afstand overgenomen konden worden. In een onderzoek [13] dat gedaan is naar dit niet meer bestaande netwerk is een graaf gegenereerd die het netwerk weergeeft.

Figuur 2.2.: De graaf van het ZeuSnetwerk. De blauwe punten staan voor ge¨ınfecteerde computers en de groene lijnen geven een peer-to-peer connectie aan tussen twee punten.

9

Overige categoriën van netwerken zijn de biologische netwerken en de technologische netwerken. Met voorbeelden zoals het netwerk van de verspreiding van een virus in een populatie als biologisch netwerk en een elektriciteitsnetwerk als technologisch netwerk. In het laatste hoofdstuk zal een toepassing behandeld worden van een model waarbij het netwerk valt binnen de biologische netwerken.

2.2. Waarom bestuderen we netwerken? De interessante vraag is nu: ”Waarom willen we netwerken bekijken?”. Voordat we netwerken gaan modelleren zullen we eerst deze vraag beantwoorden. Om een beter inzicht te krijgen in welke context netwerken zo interessant zijn zullen we wederom verschillende deelgebieden bekijken. De sociale wetenschappen zijn vaak ge¨ınteresseerd in de interpretatie van de connecties binnen een sociaal netwerk. Wat achterhaald wilt worden is of deze ontstaan uit vriendschap, strategische overwegingen, gedwongen of wellicht een andere relatie? Een groot deel van de literatuur in sociale wetenschappen is daarom gewijd aan het modelleren van de sociale netwerken en het testen van hypotheses om netwerk structuur te achterhalen. In de zogenaamde machine learning community worden netwerken vaak gebruikt om nog niet acherhaalde informatie te voorspellen zoals ontbrekende connecties binnen een netwerk. Andere toepassingen zijn het vinden van een missende connectie in een bedrijf of terroristisch netwerk en bijvoorbeeld het berekenen van de kans dat een klant een product koopt gegeven de aankopen van zijn vrienden. Het laatste voorbeeld kan breder opgevat worden en is te zien als het voorspellen van de voorkeuren van een individu aan de hand van gegevens van vrienden van dit individu. Een recente toepassing van deze vorm van netwerk analyse is onder de aandacht gebracht door het bedrijf Netflix [14] dat online films en series aanbiedt. Het bedrijf heeft namelijk een prijs van één miljoen dollar uitgekeerd aan een groep onderzoekers die konden voorspellen hoe films beoordeeld gingen worden meer dan 10% nauwkeuriger hun eigen systemen zelf konden. Niet alleen in deze vakgebied worden netwerken gebruikt om dingen te voorspellen. In de computationele biologie worden netwerken bijvoorbeeld gebruikt om HIV infecties binnen een populatie te voorspellen en de verspreiding van virussen te modelleren. Waar netwerken ook een belangrijke rol hebben is in het vinden van verborgen groepen. Dit soort worden netwerken worden bestudeerd om bijvoorbeeld terroristische cellen te vinden in een samenleving. Netwerken worden dus in veel vakgebieden bekeken en hebben een belangrijke rol in het voorspellen en beantwoorden van vragen die opkomen als groepen mensen of dingen bekeken worden. Toch is niet alleen de link van netwerken met de werkelijkheid interessant. Netwerken zijn ook wiskundig interessant, namelijk ”Wat gebeurd er met een netwerk als het aantal punten naar oneindig gaat?” is een wiskundig interessante vraag. En ”Wat is de beste

10

manier om een netwerk te modelleren?” is nog zo’n vraag. Er zijn dus genoeg toepassingen, maar in elk van deze vakgebieden is het analyseren van netwerken niet mogelijk zonder de wiskundige modellen. In de volgende hoofdstukken moet dus eerst allereerst het wiskundig fundament gelegd voordat er naar toepassingen gekeken kan worden.

11

3. Grafentheorie en de exponenti¨ ele familie van verdelingen Voordat er een begin gemaakt kan worden met behandelen van netwerkmodellen moet er eerst een stuk theorie opgebouwd worden. In dit hoofdstuk zal daarom de benodigde voorkennis gegeven worden. Er zal terminologie en notatie ingevoerd worden om de graaf van een netwerk precies te definiëren en ook zullen eigenschappen behandeld worden van de exponentiële familie van verdelingen die nodig zijn voor het model dat behandeld zal worden in sectie 4.3.

3.1. Grafentheorie Een netwerk kan zoals eerder genoemd weergegeven worden als een graaf, daarom zal notatie en terminologie worden ingevoerd om dit precies te maken. In de grafentheorie bestaat een graaf (netwerk) G uit punten en lijnen G ≡ G (N , E), waarbij N de verzameling van punten voorstelt en E de verzameling van lijnen. Het aantal punten is dan gegeven door N = |N | en h““tal lijnen is E = |E|. In het algemeen wordt G vaak gedefinieerd in termen van de connecties tussen paren punten. De verzameling van connecties Y 0 wordt vaak uitgedrukt in een matrix Y van grootte N × N . Deze matrix wordt ook wel de verbindingsmatrix genoemd en is gedefinieerd als volgt. Definitie 3.1 (De verbindingsmatrix). Stel we bekijken de graaf G ≡ G (N , E) van deze graaf labelen we de punten uit N met de nummers 1, 2, . . . , N . Dan is het element (entry) op de i-de rij en j-de kolom van de verbindingsmatrix gegeven door 1 als de punten i en j verbonden zijn Yij = 0 anders. In het vervolg van deze scriptie beschouwen we alleen niet-gerichte grafen, waarbij het niet-gerichte aanduidt dat de lijnen geen oriëntatie hebben dat wil zeggen dat de lijn vanuit het punt i naar j precies hetzelfde voorstelt als de lijn vanuit j naar i. Als dan in een graaf i een connectie heeft met j geeft dit aan dat j ook een connectie heeft met i. Het aantal lijnen van eenP niet-gerichte graaf kan dus worden berekend aan de hand van de volgende uitdrukking i<j Yij en volgt uit de symmetrie van de verbindingsmatrix. Immers in een niet-gerichte graaf heeft de entry Yij dezelfde waarde als de entry Yji .

12

Voorbeeld 3.2 (Gelabelde graaf met verbindingsmatrix). Een eenvoudig voorbeeld om de voorgaande definitie te illustreren is met de volgende graaf.

Figuur 3.1.: Een voorbeeld graaf met bijbehorende verbindingsmatrix. Naast de graaf is de bijbehorende verbindingsmatrix gegeven. Alle diagonaalelementen van de verbindingsmatrix zijn nul, omdat er in een netwerk geen connectie tot zichzelf bestaat.

3.2. De exponenti¨ ele familie van verdelingen Definitie 3.3. Laat X een random variabele zijn met verdeling uit de parametrische familie van verdelingen {Pθ | θ ∈ Θ} waarbij Θ ⊆ R. Waarbij de parameterverzameling komt uit R = R ∪ {±∞} en is het dus ook mogelijk dat de parameter de waarde ±∞ aanneemt. De familie van verdelingen {Pθ | θ ∈ Θ} behoort dan tot de één-parameter exponentiële familie als de dichtheden p(x | θ) = pθ (x) voldoen aan pθ (x) = eη(θ)T (x)−ψ(η(θ)) h(x), waarbij T (x), η(θ), ψ (η (θ)) en h(x) ≥ 0 allen reëelwaardige functies zijn. Voorbeeld 3.4 (De Bernoulli verdeling). Stel X is Bernoulli(α) (alternatief) verdeeld met α ∈ (0, 1). Om nu te laten zien dat de Bernoulli(α) verdeling behoort tot de familie van exponentiële verdelingen zullen we de dichtheid omschrijven. Er geldt nu dat pα (x) = αx (1 − α)1−x = exp log αx (1 − α)1−x = exp {x log (α) + (1 − x) log (1 − α)} α = exp x log + log (1 − α) 1−α n o = exp xη(α) − log 1 + eη(α) . α Volgens de voorgaande definitie geldt nu met T (x) = x, η(α) = log 1−α , ψ(η(α)) = η(α) log 1 + e en h(x) = 1 dat er aan alle voorwaarden voldaan is. Dus behoort deze verdeling tot de één-parameter exponentiële familie met parameter θ = α.

13

Definitie 3.5 (De s-parameter exponentiële familie). Stel wederom dat X een random s variabele is met verdeling uit {Pθ | θ ∈ Θ} waarbij Θ ⊆ R . Zij θ nu een vector van parameters θ = (θ1 , θ2 , . . . , θs )t . Dan behoort de familie van verdelingen {Pθ | θ ∈ Θ} tot de s-parameter exponentiële familie als de dichtheden voldoen aan ( s ) X pθ (x) = exp ηi (θ)Ti (x) − ψ(η(θ)) h(x) i=1

= exp η(θ)t T (x) − ψ(η(θ)) h(x) waarbij T (x) = (T1 (x), . . . , Ts (x))t en η(θ) = (η1 (θ), . . . , ηs (θ))t . En waarbij Ti (x), ηi (θ), ψ(η(θ)) en h(x) ≥ 0 met i ∈ {1, 2, . . . , s} allen reëelwaardige functies zijn. Definitie 3.6 (De kanonieke exponentiële familie). Als de random variabele X een verdeling heeft uit de exponentiële familie van verdelingen en er geldt verder dat η(θ) = θ. Dan komt deze verdeling uit de zogenaamde kanonieke exponentiële familie van verdelingen. Voorbeeld 3.7 (De normale verdeling). Stel X is normaal verdeeld dat wil zeggen X ∼ N (µ, σ 2 ). Dan onder de veronderstelling dat θt = (µ, σ 2 ) onbekend is, is de dichtheid gegeven door 1 (x − µ)2 pµ,σ2 = √ exp − 2σ 2 2πσ 2 µx µ2 1 x2 = √ exp − log(σ) − 2 + 2 − 2 2σ σ 2σ 2π 2 1 µ = √ exp η(θ)T (x) − log(σ) − 2 , 2σ 2π t t waarbij T (x) = (T1 (x), T2 (x)) t = x, x2 , η(θ) = (η1 (θ), η2 (θ))t = σµ2 , − 2σ1 2 , ψ(η(θ)) = 1 η12 µ2 1 √1 + log(σ) = − 2 4η2 + 2 log 2η2 en h(x) = 2π . En dus behoort de normale verdeling 2σ tot de 2-parameter exponentiële familie van verdelingen. In het volgende hoofdstuk zullen we zien dat een belangrijk netwerkmodel behoort tot deze familie van verdelingen.

3.2.1. De meest aannemelijke schatter Een veel gebruikte methode in de statistiek om de parameter θ te achterhalen van een statistisch geparametriseerd model is de meest aannemelijke schatter θˆ vinden. Gegeven geobserveerde data en een model kan de meest aannemelijke schatter een schatting geven van de ware parameters van het model. De manier waarop dit gebeurd heet maximum likelihood hierbij wordt de zogenaamde log-likelihood functie gemaximaliseerd om zo de kans op de geobserveerde data te maximaliseren. Allereerst zullen we beginnen met wat definities.

14

Definitie 3.8 (De likelihood functie). Zij X een random variabele met verdeling uit {Pθ | θ ∈ Θ}. Als X discreet verdeeld is, dan is de likelihood van θ gegeven een observatie x gedefinieerd als L(θ) = L(θ | x) = pθ (x) = Pθ (X = x). Als X continu verdeeld is dan is de likelihood van θ gegeven een observatie gedefinieerd als L(θ) = L(θ | x) = pθ (x), waarbij pθ (x) de dichtheidsfunctie voorstelt. De log-likelihood functie ` is dan gegeven door het natuurlijk logaritme van de likelihood functie. Definitie 3.9 (De meest aannemelijke schatter). We definiëren de meest aannemelijke schatter nu als de waarde θˆ van θ dat een globaal maximum is van de log-likelihood functie en dus ook van de likelihood. Voor een model uit de kanonieke s-parameter exponentiële familie van verdelingen ges parametriseerd door θ ∈ Θ ⊆ R geldt dat de dichtheid geven is door: pθ (x) = exp θt T (x) − ψ(θ) h(x). Om nu de meest aannemelijke schatter θˆ van θ te vinden gebaseerd op een observatie x schrijven we `(θ) = log L(θ) = θt T (x) − ψ(θ) + log (h(x)) s X = θj Tj (x) − ψ(θ) + log (h(x)) . j=1

Om nu het maximum te bepalen moeten er van deze uitdrukking de partiële afgeleiden gelijk aan 0 gesteld worden met andere woorden er moet gelden ∂ `(θ) = 0 ⇔ Tr (x) = Eθ [Tr (X)] , ∂θr

(3.1)

voor alle r ∈ {1, . . . , s}. Waarbij de waarde r de r-de entry van de respectievelijke vectoren aangeeft. De bovenstaande uitdrukking is een direct gevolg als we opmerken dat ∂θ∂ r ψ(θ) = Eθ [Tr (X)]1 . Als we dan nu de tweede afgeleide nemen krijgen we dat ∂2 `(θ) = −ir,q (θ) = −Covθ [Tr (X), Tq (X)] , ∂θr θq waarbij r, q ∈ {1, . . . , s} en ir,q de r, q-de entry is van de Hessian van de log-likelihood functie die onder regulariteitsvoorwaarden correspondeert met de covariantiematrix van T die altijd symmetrisch is aangezien de covariantie in zijn argumenten symmetrisch is. 1

Voor afleiding zie appendix stelling A.1.

15

We zullen nu laten zien dat deze symmetrische matrix negatief definiet1 is. Namelijk eerst nemen we een willekeurige v ∈ Rs en stellen we dat H(θ) de Hessian voorstelt van de log-likelihood functie dan geldt v t H(θ)v = −v t Var [T1 (X), T2 (X), . . . , Ts (X)] v = −v t E (T (X) − E (T (X))) (T (X) − E (T (X)))t v = −E v t (T (X) − E (T (X))) (T (X) − E (T (X)))t v h t i = −E (T (X) − E (T (X)))t v ((T (X) − E (T (X)))t v = −E W t W ≤ 0, waarbij W = ((T (X) − E (T (X))) v). Er geldt nu dus dat de uitdrukkingen een negatief definiete matrix vormen en dus is elk stabiel punt een maximum en is er ten hoogste één maximum. Voor de meest aannemelijke schatter θˆ voorgekomen uit (3.1) geldt dus dat Eθˆ [Tr (X)] = Tr (x).

(3.2)

Een soortgelijke afleiding is mogelijk waarbij we stellen dat θ = η(θ), maar zal hier niet worden afgeleid.

1

Een matrix H is negatief definiet als voor alle vectoren v, er geldt v t Hv < 0. Voor symmetrische matrices is dit equivalent aan dat alle eigenwaarden negatief zijn.

16

4. Netwerk modellen In dit hoofdstuk zullen er een aantal netwerkmodellen behandeld worden. Het eerste model dat we zullen bekijken is het Erd˝os-Rényi-Gilbert model en is een klassiek voorbeeld van een random graaf model. Andere modellen die behandeld zullen worden zijn de blokmodellen waarbij het onderscheiden van groepen gemakkelijker gaat en het meer algemene exponentiële random graaf model. Vooral het exponentiële random graaf model zal in het volgend hoofdstuk in detail uitgewerkt worden.

4.1. Het Erd˝ os-R´ enyi-Gilbert random graaf model Dit netwerk model bedacht door Erd˝os en Rényi wordt ook wel het G(N, p) model genoemd. In dit model voor een netwerk met N punten wordt er een lijn getrokken tussen paren punten met kans p onafhankelijk van wat er eerder gebeurd is. Een andere formulering van dit model is geformuleerd door Gilbert en is het G(N, E) model, waarbij het aantal lijnen E in het model vaststaat en deze willekeurig gekozen worden uit de N2 mogelijke lijnen. Het G(N, p) model heeft een binomiale likelihood-functie voor het aantal lijnen en is gegeven door N L(G(N, p) heeft E lijnen | p) = pE (1 − p)( 2 )−E . Een equivalente formulering in termen van de N × N verbindingsmatrix Y is Y L(Y | p) = pYij (1 − p)1−Yij . i6=j

Een probleem met dit model is dat elke lijn dezelfde kans gegeven wordt, in het bijzonder wordt elke graaf met hetzelfde aantal lijnen dezelfde kans gegeven. In de realiteit hoeft dit echter niet het geval te zijn en daarom bekijken we nu wat specifiekere modellen.

4.2. Het stochastische blokmodel Een probleem dat zich voordoet bij het Erd˝os-Rényi-Gilbert random graaf model is dat er geen onderscheid gemaakt kan worden tussen verschillende groepen in een netwerk. In een blokmodel kan er wel onderscheid gemaakt worden tussen verschillende groepen

17

punten. In dit model wordt de verzameling van punten N onderverdeeld in verschillende partities of groepen. Op deze manier kan er een specifieke kans gegeven worden voor het bestaan van connecties tussen punten van verschillende partities of binnen een partitie zelf. Allereerst zullen we nu het model gaan definiëren. Definitie 4.1 (Het stochastische blokmodel). Een stochastisch blokmodel is voor N genummerde punten gedefinieerd aan de hand van de volgende drie keuzes: • k: Een scalere waarde die aangeeft hoeveel partities of groepen er in het netwerk zijn, • z: Een N × 1 vector waar z(l) de groepindex geeft van het genummerde punt l ∈ {1, 2, . . . , N }, • M : Een k × k stochastische blokmatrix, met entries Mij die de kans geven dat een punt uit groep i verbonden is met een punt uit groep j. Allereerst moet er in dit model een keuze voor k gemaakt worden die het aantal verschillende groepen aangeeft in het netwerk. Daarna moeten de punten onderverdeeld worden tussen deze groepen en zo ontstaat de vector z. Het enige wat dan nog resteert is de keuze van de kansen tussen verschillende groepen dat resulteert in de stochastische blokmatrix M . De likelihood-functie van dit model is dan gegeven door Y L(G | M, z) = P (Er is een lijn tussen u en v | M, z), u,v

waarbij de vector z de punten u en v verdeeld in de respectievelijke groepen en de matrix M de kans tussen deze punten geeft. In deze scriptie zal deze likelihood niet verder uitgewerkt worden omdat dit model niet in detail behandeld zal worden. Om wel een overzicht te geven in welke gevallen het gebruik van een blokmodel voor de hand ligt zullen hier een paar voorbeeldnetwerken gegeven worden.

4.2.1. Gegroepeerde netwerken Een voorbeeld van een gegroepeerd netwerk dat voor de hand ligt is een assortatief netwerk. In een assortatief netwerk hebben punten die uit dezelfde groep komen een grotere kans om met elkaar verbonden te zijn. In een groep zullen er dus relatief meer connecties voorkomen dan tussen groepen onderling. Voor de matrix M betekent dit dat de diagonaalblokken een grotere waarde hebben dan de overige blokken. Om dit te illustreren volgt nu een voorbeeld.

18

Voorbeeld 4.2 (Een assortatief netwerk). Hieronder is aan de linkerkant een stochastische blokmatrix gegeven en aan de rechterkant een gegenereerd1 voorbeeld netwerk aan de hand van deze blokmatrix. De verschillende kleuren van de punten staan voor de groepen waartoe zij behoren.

Figuur 4.1.: Een assortatief netwerk met blokmatrix en gegenereerd voorbeeld. Het tegenovergestelde van een assortatief netwerk is een disassortatief netwerk. In een disassortatief netwerk hebben punten binnen dezelfde groep juist een lagere kans om met elkaar verbonden te zijn dan met punten uit andere groepen. Voorbeeld 4.3 (Een disassortatief netwerk). Hieronder is wederom een stochastische blokmatrix gegeven met een voorbeeld netwerk.

Figuur 4.2.: Een disassortatief netwerk met blokmatrix en gegenereerd voorbeeld. Andere voorbeelden van gegroepeerde netwerken zijn bijvoorbeeld de gecentreerde netwerken waarbij de groep met de laagste groepsindex de meeste kans op connecties heeft en naarmate de groepsindex toeneemt dat de kans op connecties toeneemt en de geordende netwerken waarbij de blokken onder en boven de diagonaal van de blokmatrix 1

Plaatjes van netwerken kunnen gegenereerd worden met behulp van de package Statnet in de programmeertaal R.

19

dezelfde kans krijgen. En zo zijn er nog veel andere soorten netwerken waar blokmodellen op toegepast zouden kunnen worden.

4.3. Het exponenti¨ ele random graaf model Het exponentiële random graaf model (ERG model) is een veel toegepast model in het onderzoek naar netwerken en wordt ook wel het p∗ -model genoemd. De naam van dit model is afkomstig van zijn specificatie namelijk het model behoort tot de in hoofdstuk 2 gedefinieerde familie van exponentiële verdelingen. Om dit te laten zien zullen we nu eerst het model gaan definiëren. Definitie 4.4 (Het exponentiële random graaf model (ERG model)). In dit model is de klasse van modellen gedefinieerd als random graaf modellen voor een vast N aantal punten door de volgende verdeling: exp θt s(y) Pθ (Y = y) = . κ(θ, Y) voor y ∈ Y waarbij: • Y is een random graaf die een bijbehorende verbindingsmatrix heeft, • Y is de verzameling van alle mogelijke netwerkconfiguraties en kan ge¨ıdentificeerd worden met {0, 1}N , • θ = (θ1 , . . . , θs )t is een s-vector van parameters, • s(y) is een gegeven s-vector met de netwerk informatie van y, • κ(θ, Y) is de normalisatiefactor die ervoor zorgt dat het t definieert P een kansmaat en is gegeven door de volgende uitdrukking κ(θ, Y) = z∈Y exp θ s(z) . Dat deze klasse van modellen behoort tot de familie van exponentiële verdelingen is gemakkelijk in te zien immers aangezien de verdeling discreet is geldt exp θt s(y) pθ (y) = Pθ (Y = y) = κ(θ, Y) = exp θt s(y) − log (κ (θ, Y)) = exp θt T (y) − ψ (θ, Y) ( s ) X = exp θi Ti (y) − ψ (θ, Y) i=1

Dus geldt met T (y) = s(y), η(θ)t = θt , ψ(θ, Y) = log κ(θ, Y) en h(y) = 1 dat deze klasse van modellen behoort tot de s-parameter exponentiële familie van verdelingen.

20

Voorbeeld 4.5. In dit voorbeeld zullen we afleiden dat het G(N, p) model behoort tot de ERG modellen. In dit model is de enige revalante netwerkinformatie het aantal P lijnen. Voor een y ∈ Y kiezen we dus als netwerkinformatie s(y) = i<j Yij0 waarbij Y 0 de verbindingsmatrix is van de graaf y en dus het aantal lijnen geeft. In dit model is er dus alleen één parameter θ aangezien de netwerkinformatie één-dimensionaal is. We zullen nu de normalisatiefactor gaan afleiden. Er geldt nu dat    X  X X κ(θ, Y) = exp {θs(z)} = exp θ Yij   z∈Y

=

Y

{Yij }∈Y

1 X

exp {θYij } =

i<j Yij =0

Y

i<j

N (1 + eθ ) = (1 + eθ )( 2 )

i<j N

en dus is de normalisatiefactor gegeven door κ(θ, Y) = (1 + eθ )( 2 ) . Schrijven we dan nu het ERG model uit met de bijbehorende normalisatiefactor dan volgt: exp θt s(y) exp θt s(y) = Pθ (Y = y) = N κ(θ, Y) (1 + eθ )( 2 ) s(y) (N )−s(y) 2 1 1 = 1 − e−θ + 1 e−θ + 1 N = ps(y) (1 − p)( 2 )−s(y) N

= pEy (1 − p)( 2 )−Ey met p = e−θ1+1 en Ey het aantal lijnen van de graaf y is. En dus zien we dat het G(N, p) model een ERG model is. In de praktijk is het niet zo gemakkelijk om een algemeen ERG model uit te rekenen. Daarom bespreken we in het volgende hoofdstuk een manier om deze toch te benaderen.

21

5. Maximum likelihood op het exponenti¨ ele random graaf model In het algemeen is het niet makkelijk om een exacte oplossing te vinden voor de meest aannemelijke schatter van een ERG model. Het probleem dat zich voordoet zit in de normalisatiefactor. Deze is in sommige gevallen nog makkelijk uit te rekenen, maar bij een toename van het aantal punten N wordt deze al snel lastig om uit te rekenen. Als bijvoorbeeld gekeken wordt naar een netwerkgraaf met N punten dan moet er gesomN meerd worden over 2( 2 ) termen. In het geval van N = 10 zijn dit al zo’n 1013 termen en bij N = 20 zijn het er ongeveer 1057 en dit neemt snel toe. Daarom is er een alternatief gevonden onder de naam Monte Carlo Markov Chain (MCMC). In dit hoofdstuk zullen we behandelen hoe deze manier gebruikt wordt om de meest aannemelijk schatter te bepalen van een ERG model.

5.1. De Monte Carlo Markovketen Een Markovketen1 (Markov Chain) is een proces dat alleen afhankelijk is van wat er op het tijdstip daarvoor gebeurd is. Iets preciezer als {Xt }t∈N een Markovketen is dan is de Markovketen op tijdstip t + 1 gedefinieerd als Xt+1 alleen afhankelijk van Xt op tijdstip ´ en van de belangrijke eigenschappen van een Markovketen is dat deze onder de t. E´ juiste voorwaarden convergeert naar een evenwichtsverdeling π dit zal in detail worden besproken in sectie 5.3. Een Monte Carlo Markovketen (MCMC) algoritme is een algoritme waarbij de uitkomst Xt+1 op tijdstip t+1 alleen afhangt van wat er op tijdstip t is gebeurd. In een MCMC algoritme genereerd het Monte Carlo proces een willekeurige waarde dat daarna vergeleken word met de huidige situatie en zo een volgende stap zet.

1

Een precieze definitie is gegeven in de appendix.

22

5.2. De benadering van de meest aannemelijke schatter Om een algemene benadering te geven van een ERG model willen we nu de meest aannemelijke schatter bepalen. Om deze te bepalen moeten we eerst de log-likelihood functie ` bepalen. Deze is voor een algemeen s-parameter ERG model gegeven door `(θ) = log L(θ) = θt s(y) − κ(θ, Y). Als we direct de meest aannemelijke schatter willen bepalen moeten nu de partiële afgeleiden genomen worden. In sectie 3.2.1 hebben we gezien dat dit leidt tot de volgende vergelijking Eθˆ [sr (Y )] = sr (y), (5.1) waarbij

∂ ∂θr κ(θ, Y)

= Eθ [sr (Y )].

Het probleem hierbij is echter dat de normalisatiefactor zoals eerder genoemd in de meeste gevallen moeilijk te berekenen is en toch voorkomt in vergelijking (5.1). We zullen nu een alternatieve methode bekijken dat gebruik maakt van een MCMC algoritme om dit op te lossen.

5.2.1. Het benaderen van de log-likelihood functie We veronderstellen nu wederom dat we een ERG model Pθ (Y = y) hebben met bijbehorende eigenschappen. Laat dan nu θ0 een willekeurig gekozen vaste vector van parameters zijn. Voor iedere y ∈ Y geldt dan nu dat X Eθ0 exp (θ − θ0 )t s(y) = exp (θ − θ0 )t s(y) Pθ0 (Y = y) y∈Y

=

X y∈Y

=

exp θ0t s(y) t exp (θ − θ0 ) s(y) κ(θ0 , Y)

X 1 κ(θ, Y) exp θt s(y) = , κ(θ0 , Y) κ(θ0 , Y) y∈Y

volgens de eigenschappen van een ERG model en de definitie van een discrete verwachting. κ(θ,Y) Uit het bovenstaande zien we nu in dat κ(θ een verwachting is ten opzichte van 0 ,Y) de vaste parameters θ0 . Als deze verwachting te bepalen is dan weten we ook wat de normalisatiefactor is. In een ideale situatie is nu de algemene wet van de grote aantallen toe te passen om deze verwachting te benaderen, echter is het probleem dat hier een onafhankelijke steekproef voor nodig is die niet zomaar te verkrijgen is. Toch is hier een oplossing voor namelijk met een aangepaste versie van de wet van de grote

23

aantallen1 kunnen we deze verwachting benaderen met een gemiddelde van een steekproef die voldoet de Markov eigenschap en dus is onafhankelijkheid niet nodig. In de volgende sectie zal behandeld worden hoe met een MCMC algoritme deze steekproef bepaald kan worden. Als er nu even vanuit wordt gegaan dat we een random steekproef y1 , y2 , . . . , yn gegeven hebben die voldoet aan de Markov eigenschap. Dan kunnen we met behulp van deze wet van de grote aantallen en dat de e-macht een reële niet-negatieve functie zeggen dat κ(θ, Y) = Eθ0 exp (θ − θ0 )t s(y) , κ(θ0 , Y)

(5.2)

benaderd kan worden met een gemiddelde namelijk n

1X exp (θ − θ0 )t s(yi ) . n i=1

in subsectie 5.2.2 wordt behandeld hoe er random steekproef gegenereerd kan worden uit de kansmaat Pθ0 . In het bijzonder geldt er dus dat P

! n 1X t t lim exp (θ − θ0 ) s(yi ) = Eθ0 exp (θ − θ0 ) s(y) = 1, n→∞ n i=1

we kunnen dus zeggen dat dit steekproef gemiddelde bijna zeker 1 naar deze verwachting gaat. Dus nu gegeven de steekproef y1 , y2 , . . . , yn van grafen en als we ervanuit gaan dat we een observatie y obs hebben kunnen we de log-likelihood functie `(θ) volgens de definities in hoofdstuk 3 bepalen. Deze is dan gegeven door t obs ! exp θ s(y ) = log . (5.3) `(θ) = log(L(θ)) = log Pθ Y = y obs κ(θ, Y) Om de bovenstaande resultaten te gebruiken zullen we nu de loglikelihood omschrijven met behulp van `(θ0 ). Met wat omschrijfwerk krijgen we dan dat !! exp θt s y obs exp θ0t s y obs `(θ) − `(θ0 ) = log − log κ(θ, Y) κ(θ, Y) n o κ(θ, Y) = − log exp (θ0 − θ)t s y obs . κ(θ0 , Y) 1

Zie appendix stelling A.4 voor de algemene wet van de grote aantallen en stelling A.8 voor de aangepaste wet. 1 Zie appendix definitie A.2

24

κ(θ,Y) Uit het voorgaande zien we dus dat de term κ(θ terugkomt. Omdat we nu ook weten 0 ,Y) deze term benaderd kan worden met een gemiddelde geldt ! n n o 1 X t obs t `(θ) − `(θ0 ) ≈ − log exp (θ0 − θ) s y × exp (θ − θ0 ) s(yi ) n i=1 ! n n o X 1 t obs t = − log exp (θ − θ0 ) × −s y × exp (θ − θ0 ) s(yi ) n i=1 ! n n o 1X . = − log exp (θ − θ0 )t s(yi ) − s y obs n i=1

Als nu de laatste uitdrukking gemaximaliseerd word als functie van θ dan maximaliseren we (ongeveer) `(θ) − `(θ0 ). Maar aangezien we verondersteld hebben dat θ0 vast gekozen is en dus niet variabel is geldt nu dat we `(θ) maximaliseren. Door de bovenstaande uitdrukking te maximaliseren kunnen we dus de meeste aannemelijke schatter θˆ vinden. Vaak wordt dit maximalisatie probleem numeriek opgelost, een manier om dit iteratief te doen is bijvoorbeeld met de Newton-Raphson methode.

5.2.2. Het genereren van een steekproef De vraag is die nu over is gebleven is hoe we een steekproef van grafen y1 , y2 , . . . , yn met de Markov eigenschap kunnen genereren uit de kansmaat Pθ0 . Om deze steekproef te verkrijgen zullen we een MCMC algoritme gaan gebruiken waarmee ook meteen aan de Markov eigenschap voldaan is. Namelijk veronderstel dat we beginnen met een geobserveerde graaf y obs als we op deze graaf een MCMC algoritme toepassen dan zal deze convergeren naar een gegeven verdeling. Als dan elke graaf die gegenereerd is opgeslagen word verkrijgen we zo een steekproef van grafen. We zullen nu twee verschillende MCMC algoritmes bekijken die dit voor elkaar kunnen krijgen. Definitie 5.1 (De Gibbs Sampler). Stel we hebben een vaste willekeurig gekozen svector van parameters θ0 en een geobserveerd netwerk y obs (N , E) met verbindingsmatrix Y 0 waar we mee beginnen. Het algoritme is dan gedefinieerd als volgt • Allereerst selecteren we willekeurig twee punten u, v ∈ N met u 6= v. + • Als er een lijn loopt tussen de twee punten dan definiëren we yij als y obs en de − graaf waar alleen deze lijn weggelaten wordt noemen we yij . + • Als er geen lijn loopt dan definiëren we yij als y obs waarbij de lijn tussen u en v − toegevoegd wordt en yij als y obs zelf.

• We genereren dan de nieuwe graaf ynieuw gegeven y obs op de volgende manier: Ongeacht of y obs al een lijn tussen u en v heeft zal er in de nieuwe graaf een lijn

25

tussen u en v lopen met kans: n o + − exp θ0t s yij − s yij n o . + − 1 + exp θ0t s yij − s yij • Als we deze stappen steeds herhalen op de nieuwe graaf ynieuw en ook de verkregen graaf opgeslaan dan verkrijgen we hieruit een steekproef van grafen. Met andere woorden als de bovenstaande waarde (kans) groter is dan een willekeurige gegenereerde waarde tussen 0 en 1 (het Monte Carlo sample) dan wordt er in die stap een lijn getekend of toegestaan tussen u en v. Als de waarde (kans) kleiner of gelijk is aan de waarde gegenereerd door het Monte Carlo proces dan zal er geen lijn tussen u en v lopen in de nieuwe graaf ynieuw . Definitie 5.2 (Metropolis-Hastings). Een andere algoritme dat in essentie hetzelfde doet als de Gibbs Sampler is het Metropolis-Hastings algoritme. Het enige verschil is dat er bij Metropolis-Hastings gekeken wordt of er een lijn toegevoegd moet worden of als hij er al is verwijderd moet worden. De eerste stappen gaan analoog met het + − eerste algoritme tot het nieuwe netwerk gegenereerd moet worden namelijk na yij en yij gedefinieerd te hebben wordt ynieuw op de volgende manier gegenereerd • Als er in de gegeven graaf geen lijn bestaat tussen u en v dan wordt er met kans: n o + − min(1, π1 ) = min 1, exp θ0t s yij − s yij , een lijn tussen u en v toegevoegd. • Als er in de gegeven graaf wel een lijn bestaat tussen u en v dan wordt met kans: n o + − min(1, π2 ) = min 1, exp −θ0t s yij − s yij , de lijn verwijderd uit de graaf. De verkregen nieuwe graaf ynieuw wordt dan wederom opgeslagen om zo een steekproef te genereren. Op de dan verkregen nieuwe graaf ynieuw wordt dit algoritme herhaald analoog aan het Gibbs Sampler algoritme. Aan de hand van deze algoritmes kan er dus een steekproef verkregen worden. De steekproef voldoet aan de eisen, want aan de Markov eigenschap is per definitie voldaan en aan de andere eis van irreducibiliteit is ook voldaan aangezien het model gedefinieerd is voor een eindig aantal punten. In sectie 5.3 zal ook de detailed balance vergelijking voor deze algoritmes nagegaan worden zodat de aangepaste wet van de grote aantallen toe te passen is.

26

5.2.3. De normalisatiefactor Uit de voorgaande secties hebben we nu een methode verkregen om de vector van parameters te schatten. Het enige wat nog resteert is de normalisatiefactor onder θ0 te bepalen. Door vergelijking (5.1) weten we dat n

κ(θ, Y) 1X ≈ exp (θ − θ0 )t s(yi ) , κ(θ0 , Y) n

(5.4)

i=1

met y1 , y2 , . . . , yn de eerder genoemde random steekproef. Als we nu stellen θ0 = 0 kunnen we de definitie van een ERG model gebruiken om te verkrijgen dat X X κ(θ, Y) = κ(0, Y) = e0 = 1, y∈Y

y∈Y

en is in dit geval de normalisatiefactor dus precies het aantal grafen in Y en is dus alle N grafen met N punten en geldt er κ(0, Y) = 2( 2 ) . Dus kunnen we vergelijking (5.4) omschrijven tot !−1 n t 1X N κ(θ0 , Y) ≈ exp −θ0 s(yi ) 2 n i=1 ! n n o 1 X n o −1 N ≈ exp −θ0t s y obs exp −θ0t s(yi ) − s y obs . n 2 i=1

Hiermee hebben we een uitdrukking gevonden voor de normalisatiefactor onder θ0 .

5.3. Convergentie naar evenwicht Een probleem dat zich kan voordoen bij het gebruik van MCMC algoritmes is dat er geen convergentie optreedt en dus zo de wet van de grote aantallen niet toe te passen is. Aangezien er willekeurig twee punten geselecteerd worden in beide algoritmes kunnen we er van uitgaan dat elke mogelijke netwerkconfiguratie bereikt kan worden in een eindig aantal stappen. Met deze eigenschap en de zogenaamde detailed balance vergelijking van de Markovketen in het algoritme kan convergentie aangetoond worden. We definiëren eerst de overgangskans Pt (yα , yβ ) die de kans aangeeft dat de graaf yα veranderd in de graaf yβ op tijdstip t in het algoritme. Als er dan nu een verdeling π bestaat zodanig dat voor alle yα , yβ ∈ Y de volgende vergelijking stand houdt: π (yα ) Pt (yα , yβ ) = π (yβ ) Pt (yβ , yα ) ,

(5.5)

dan geldt er dat P en π in zogenaamde detailed balance zijn en dat π de stationaire verdeling is van de Markovketen met overgangskansen Pt (yα , yβ ).

27

We zullen nu aantonen dat deze detailed balance vergelijking geldt voor het Gibbs Sampler algoritme. We definiëren allereerst de overgangskansen van de onderliggende Markovketen voor een zekere θ ∈ Θ als: exp θt (s (yβ ) − s (yα )) Pt (yα , yβ ) = . 1 + exp {θt (s (yβ ) − s (yα ))} Als detailed balance verdeling π definiëren we π(y) = vergelijking (5.5) omschrijven naar de volgende vorm Pt (yα , yβ ) π(yβ ) = . Pt (yβ , yα ) π(yα )

exp{θt s(y)} κ(θ,Y) .

We kunnen dan nu

(5.6)

Als we dan nu eerst de linkerkant van de bovenstaande vergelijking uitschrijven dan krijgen we dat   exp θt s y −s(y ) { ( ( β) α )} Pt (yα , yβ )  1+exp{θt (s(yβ )−s(yα ))}  log = log   exp{θt (s(yα )−s(yβ ))} Pt (yβ , yα ) 1+exp{θt (s(yα )−s(yβ ))} exp{θt (s(yβ ) − s(yα ) − s(yα ) + s(yβ )) 1 + exp{θt (s(yα − s(yβ )) = log 1 + exp{θt (s(yβ ) − s(yα ))} = log exp{θt (s(yβ ) − s(yα ))} = θt (s(yβ ) − s(yα )). Schrijven we dan nu de rechterkant van de vergelijking uit en zien we in dat er hetzelfde uitkomt namelijk:   exp{θt s(yβ ) π(yβ ) κ(θ,Y) log = log  exp{θt s(y )  α π(yα ) κ(θ,Y) = log exp{θt (s(yβ ) − s(yα ))} = θt (s(yβ ) − s(yα )). En zo zien we dat er aan de detailed balance vergelijking is voldaan en dat er in het algoritme convergentie optreedt dus is er aan alle voorwaarden voldaan. Zo hebben we een manier gevonden om de meest aannemelijke schatter te benaderen voor ERG modellen.

28

6. Een toepassing van het exponenti¨ ele random graaf model In dit hoofdstuk zal een toepassing van het exponentiële random graaf model behandeld worden. Namelijk we zullen een model gaan bekijken dat gebruikt is bij het modelleren van complexe hersen netwerken.

6.1. Het complexe hersennetwerk model In de neurowetenschappen speelt het onderzoeken naar de verbondenheid van verschillende hersendelen een belangrijke rol. Een van de manieren om dit te bestuderen is door netwerkmodellen toe te passen op een aantal geselecteerde punten binnen de hersenen. We zullen een model gaan definiëren dat bij een onderzoek [15] opgesteld is om een netwerkmodel te maken van de hersenen. In dit onderzoek zijn er 90 vaste punten genomen in de hersenen van proefpersonen en tijdens experimenten werd de verbondenheid tussen deze punten bestudeerd. Na deze experimenten en observaties zijn de verschillende hersennetwerken vertaald in 90 × 90 verbindingsmatrices zoals gedefinieerd in hoofdstuk 2. In dit hoofdstuk zullen we een model gaan opstellen dat als algemeen hersennetwerk model kan dienen. Voorbeeld 6.1 (Grafische weergave van een hersennetwerk). Hieronder is een grafische weergave van het hersennetwerk van een van de proefpersonen gegeven.

Figuur 6.1.: Een grafische weergave van een hersennetwerk. De groene lijnen geven verbindingen aan tussen verschillende gebieden in de hersenen van de proefpersoon.

29

Definitie 6.2 (De verklarende variabelen binnen hersennetwerken). Om het model verder toe te kunnen lichten zullen er eerst verklarende variabelen gedefinieerd worden. Stel we hebben een gegeven decay parameter τ dan definiëren we nu de volgende variabelen: • De geometrically weighted degree variabele (GWD) als; de gewogen som van het aantal punten dat verbonden is met precies i andere punten (partners) met als gewicht de geometrische reeks (1 − exp{−τ })i . • De geometrically weighted edge-wise shared partner variabele (GWESP) als; de gewogen som van het aantal punten met precies i gedeelde partners met als gewicht de geometrische reeks (1 − exp{−τ })i . • De geometrically weighted non-edge-wise shared partner variabele (GWNSP) als; de gewogen som van het aantal niet verbonden punten met precies i gedeelde partners met gewicht de geometrische reeks (1 − exp{−τ })i . De eerste verklarende variabele geeft de verbondenheid aan binnen een hersennetwerk, de tweede variabele geeft de lokale clustering binnen het netwerk aan waarbij dit de lokale dichtheid van de punten aangeeft en de derde variabele geeft de global efficiency dat de gemiddelde lengte van het kortste pad tussen twee punten aangeeft. Voorbeeld 6.3. Om de bovenstaande begrippen te illustreren zal een voorbeeld gegeven worden. Beschouw de volgende netwerkgraaf op 6 punten: 3 1

4

2 6

5

Definieer dan ESPi en NSPi als respectievelijk de niet gewogen som van de GWESP en GWNSP zoals eerder gedefinieerd. Dan geldt er dat (ESP0 , ESP1 , . . . , ESP4 ) = (1, 5, 1, 0, 0). Immers alleen het paar (1, 2) heeft geen gedeelde partners. De paren punten met 1 gedeelde partners zijn (2, 4), (2, 3), (2, 6), (4, 5) en (5, 6) en het enige paar punten met 2 gedeelte partners is (4, 6). Zo kan ook afgeleidt worden dat (NSP0 , NSP1 , . . . , NSP4 ) = (1, 4, 2, 0, 0). Er geldt namelijk dat alleen het niet verbonden paar (1, 5) geen gedeelde partners heeft, de paren (1, 4), (1, 3), (1, 6) en (3, 5) van niet verbonden punten hebben 1 gedeelde partner en de paren (2, 5) en (3, 6) hebben 2 gedeelde partners.

30

Nu alle verklarende variabelen gedefinieerd en ge¨ıllusteerd zijn zal het ERG model gedefinieerd worden. Definitie 6.4 (Het ERG model voor hersennetwerken). Het ERG model dat gebruikt wordt bij het modelleren van hersennetwerken is dan gedefinieerd als volgt exp (θt s(y) Pθ (Y = y) = κ(θ, Y) exp ((θ1 , θ2 , θ3 )t × (E, GWESP, GWNSP) = κ(θ, Y) exp {θ1 × E + θ2 × GWESP + θ3 × GWNSP} = , κ(θ, Y) met E het aantal lijnen van y en de GWESP en GWNSP de verklarende variabelen van de graaf y. Hiermee hebben we het model gedefinieerd waarbij de parameters geschat kunnen worden met de methoden gegeven in hoofdstuk 5.

31

7. Conclusie In deze scriptie hebben we nu opgebouwd wat netwerken zijn en waarom deze zo interessant zijn. Verder is belangrijke theorie behandeld dat nodig was bij het opstellen van netwerkmodellen. In het bijzonder hebben we een aantal netwerkmodellen behandeld en het exponentiële random graaf model uitgewerkt en een methode gegeven om deze te gebruiken in de praktijk. Hierna is nog een toepassing van het model aan bod gekomen. In vervolgonderzoeken kunnen veel verschillende dingen die netwerkmodellen betreffen bestudeerd worden. In deze scriptie zijn namelijk modellen bekeken voor niet-gerichte netwerkgrafen, in een vervolgonderzoek kan er gekeken worden naar modellen voor gerichte grafen of grafen met lijnen die een bepaald gewicht hebben. Er kan ook gekeken worden naar het toepassen van een netwerkmodel in een zelf gecreërde situatie of wellicht het toepassen van een model in andere contexten. Het zelf maken van een netwerk model is natuurlijk ook interessant, maar wellicht niet al te eenvoudig. Een andere optie voor vervolgonderzoek is het bekijken van andere netwerkmodellen en daarvoor methoden uit te werken. Zo zijn er vele mogelijkheden voor vervolgonderzoeken bovendien is het onderzoeksgebied dat netwerken betreft relatief nieuw en daarom blijven veel nieuwe mogelijkheden over.

32

Bibliografie [1] Eric D. Kolaczyk, Statistical Analysis of Network Data, Springer, 2009. [2] Stanley Wasserman, Katherine Faust, Social Network Analysis: Methods and Applications, Cambridge Press, November 2001. [3] Christian Robert, The Bayesian Choice, 2nd edition, Springer, 2001. [4] Francesco Palumbo, Carlo Natale Lauro, Michael J. Greenacre, Data Analysis and Classification, Proceedings of the 6th Conference of the Classification and Data Analysis Group of the Societ Italiana di Statistica, Springer, 2010. [5] J.R. Norris, Markov Chains, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 1997. [6] Bert van Es, Syllabus Mathematische Statistiek, Korteweg-de Vries Instituut, Universiteit van Amsterdam, 5 Februari 2007. [7] Anna Goldenberg, Stephen E. Fienberg, Alice X. Zheng. Edoardo M. Airoldi, A Survery of Statistical Network Models, December 2009. [8] Jacob L. Moreno, Who Shall Survive?, N.Y.: Beacon House, New York, 1934. [9] Stanley Milgram, The Small-World Problem, Psychology Today, vol. 1, no. 1, pp6167, Mei 1967. [10] BBC News, http://www.bbc.co.uk/news/technology-15844230 November 2011. [11] W.W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33, pp452-473, 1977. [12] Hendrik Schulze, Klaus Mochalski, Peer-to-peer file sharing (P2P) still generates by far the most traffic in all monitored regions ranging from 43 percent in Northern Africa to 70 percent in Eastern Europe. Internet Study 2008/2009, Leipzig, Duitsland, 2009. [13] Brett Stone-Gross, The Lifecycle of Peer-to-Peer (Gameover) ZeuS, Dell SecureWorks Counter Threat Unit(TM) Threat Intelligence, 23 Juli 2012. [14] Netflix, Netflix one million dollar contest, http://www.netflixprize.com/ [15] Sean Simpson, Satoru Hayasaka, Paul Laurienti, Exponential Graph Modeling for Complex Brain Networks, PLoS ONE 6(5): doi:10.1371/journal.pone.0020039, 2011.

33

Random e20039.

[16] Tom Snijders, Markov Chain Monte Carlo Estimation of Exponential Random Graph Models, ICS, Department of Statistics and Measurement Theory, University of Groningen, 19 April 2002. [17] Alan Terry, Exponential random graphs, Complex Research Group, BT, Martlesham, 22 Augustus 2005. [18] Aaron Clauset, Network Analysis and Modeling, CSCI 5352, Lecture 16, 5 November 2013. [19] David Hunter, Estimation in ERGMs, Department of Statistics, Penn State University, Sunbelt, 2006. [20] Guy Lebanon, The Exponential Family of Distributions and Logistic Regression, College of Computing (CSE), Georgia Institute of Technology. [21] Steffan Lauritzen, Maximum Likelihood in Exponential Families, BS2 Statistical Inference, Lecture 6, University of Oxford, 7 November 2004.

34

A. Appendix Stelling A.1. Zij X is een random variabele met verdeling uit de exponentiële familie. Uit de definitie weten we dan dat pθ (x) = eη(θ)T (x)−ψ(η) h(x). Er geldt dan dat ∂ψ(η) . ∂η En als verder geldt dat X uit de kanonieke exponentiële familie komt dan zelfs Eθ [T (x)] =

Eθ [T (x)] =

∂ψ(θ) . ∂θ

Bewijs. We doen dit bewijs onder regulariteitsvoorwaarden. Als we dan nu definiëren g(η) = e−ψ(η) dan geldt dat de dichtheid kan omgeschreven worden tot pθ (x) = eη(θ)T (x) g(η)h(x). Aangezien dit genormaliseerd moet zijn geldt er dat Z Z Z 1 = pθ (x)dx = eη(θ)T (x) g(η)h(x)dx = g(η) eη(θ)T (x) h(x)dx. x

x

x

Als we dan nu aan beide kanten de afgeleide nemen naar η krijgen we Z Z d 0 = g(η) h(x)eη(θ)T (x) dx + g 0 (η) h(x)eη(θ)T (x) dx dη x x Z Z d η(θ)T (x) 0 = g(η) h(x) e dx + g (η) h(x)eη(θ)T (x) dx dη x Z Z x = g(η) h(x)eη(θ)T (x) T (x)dx + g 0 (η) h(x)eη(θ)T (x) dx x Z Zx 0 g (η) = g(η)h(x)eη(θ)T (x) T (x)dx + g(η)h(x)eη(θ)T (x) dx g(η) x Zx Z g 0 (η) = pθ (x)T (x)dx + pθ (x)dx g(η) x x g 0 (η) = Eθ [T (x)] + g(η) d = Eθ [T (x)] + log(g(η)). dη

35

En dus moet er gelden Eθ [T (x)] = −

d d log(g(η)) = ψ(η) dη dη

Als dan nu X uit de kanonieke exponentiële verdeling komt dus η(θ) = θ dan geldt Eθ [T (x)] = −

d d log(g(θ)) = ψ(θ) dθ dθ

Dit bewijs is gedaan voor het 1-dimensionale geval maar kan analoog worden uitgebreid naar het s-dimensionale geval. Definitie A.2 (Convergentie van kansmaten). Een rij {Xn }n∈N van random variabelen convergeert in kans (zwakke convergentie) naar X als voor alle > 0 er geldt lim P (|Xn − X| ≥ ) = 0.

n→∞

Een rij {Xn }n∈N van random variabelen convergeert bijna zeker (sterke convergentie) naar X als er geldt P lim Xn = X = 1. n→∞

Op nulverzamelingen (verzamelingen met kans 0 onder P ) na convergeert de rij dus naar X. Stelling A.3 (De (zwakke) wet van de grote aantallen). Laat {Xn }n∈N een rij van onafhankelijke identiek verdeelde random variabelen zijn met elk verwachting E[Xi ] = µ voor alle i ∈ N en eindige variantie σ. Definieer dan het steekproefgemiddelde als: n

1X X¯n = Xi . n i=1

Als nu n → ∞ dan geldt lim P X¯n − µ ≥ = 0,

n→∞

voor alle > 0. Stelling A.4 (De (sterke) wet van de grote aantallen). Laat wederom {Xn }n∈N een rij van onafhankelijke identiek verdeelde random variabelen zijn met elk verwachting E[Xi ] = µ voor alle i ∈ N en eindige variantie σ. Definieer analoog het steekproefgemiddelde als in de vorige stelling. Dan geldt er dat P

lim X¯n = µ = 1.

n→∞

Met andere woorden het steekproefgemiddelde convergeert bijna zeker naar de verwachting.

36

Definitie A.5 (Markovketen). Een Markovketen is een rij van random variabelen {Xt }t∈N dat voldoet aan de Markov eigenschap waarbij t de tijdsindex aangeeft. Een informele formulering van deze eigenschap is dat alleen de huidige staat van de keten de toekomstige staat bepaald waarbij het verleden hier dus geen invloed op heeft. Een formele definitie van de Markov eigenschap is, P (Xt+1 = x | X1 = x1 , X2 = x2 , . . . , Xt = xt ) = P (Xt+1 = x | Xt = xt ) . Definitie A.6 (Eigenschappen van Markovketens). Stel dat {Xt }t∈N een Markovketen is en dat U de verzameling is van alle mogelijke staten van deze keten. Een Markovketen heet irreducibel als elke staat door tijdsverloop bereikt kan worden vanuit elke andere (t) staat. Formeel zegt dit dat voor alle i, j ∈ U de overgangskansen Pij voor een zeker tijdstip t ≥ 0 strict groter dan 0 is. Een Markov keten heet recurrent als er in elke staat van de keten teruggekomen kan worden. Formeel moet dan gelden P (Xt = i voor oneindig veel t ) = 1. In een positief recurrente Markovketen gebeurd dit in eindige tijd. Stelling A.7. Als {Xt }t∈N een irreducibele Markovketen is die voldoet aan de detailed balance vergelijking(zoals in sectie 5.3) dan is de Markovketen positief recurrent. Stelling A.8 (Wet van de grote aantallen voor Markovketens (Ergodiciteit)). Zij {Xt }t∈N een positief recurrente Markovketen. Dan als f een begrensde reële functie is met E |f (X1 )| < ∞ dan geldt ! n 1X P lim f (Xi ) = E [f (X1 )] = 1. n→∞ n i=1

Voor bewijzen van deze stellingen en precieze formeleringen verwijs ik naar het boek Markov Chains geschreven door J.R. Norris [5].

37

B. Populaire samenvatting In ons hedendaags leven zijn netwerken eigenlijk niet meer weg te denken. Netwerken zoals Facebook, Twitter en het internet (World Wide Web) zijn voorbeelden van netwerken die een prominente positie hebben ingenomen. Niet alleen deze netwerken zijn netwerken waarmee mensen in contact staan andere voorbeelden zijn marketingnetwerken van bedrijven, netwerken van de verspreiding van ziektes en zo zijn er nog veel meer voorbeelden. Hoe meer we dus over netwerken te weten komen hoe meer we over ons dagelijks leven weten. Een misschien niet meteen voor de hand liggende manier om dit te doen is met wiskunde. Namelijk de wiskunde geeft ons de mogelijkheid om netwerkmodellen te maken om zo netwerken te kunnen modelleren. Een voor de hand liggende vraag is nu natuurlijk ”Wat is modelleren?”. Als we iets willen modelleren dan willen we meestal een wiskundig model maken van iets dat we tegenkomen. Om zo’n wiskundig model maken moeten we een abstracte formulering vinden van de werkelijkheid. Bij het bekijken van netwerken doen we dit meestal met statistiek, namelijk we willen een kans toekennen aan een bepaald netwerk om te kijken of deze voldoet aan onze eisen. Als we dan een goed model gevonden hebben dan kan er met een geobserveerd netwerk al veel gedaan worden. Bijvoorbeeld de verspreiding van ziektes kan voorspeld worden, de meest effectieve vorm van marketing kan gevonden worden en groei van sociale netwerken kan voorspeld worden. Zo zijn er vele redenen om netwerkmodellen te bekijken die in deze scriptie ook benoemd zullen worden. Aangezien we nog niet weten hoe zo’n model er precies uitziet zal er daarna behandeld worden hoe zo’n model eruit ziet en in het bijzonder zal er één model in detail behandeld worden. Er zal blijken dat belangrijke al bestaande methodes in de statistiek gebruikt kunnen worden om dit model te bekijken. Als dit gedaan is zal er nog een toepassing van het model behandeld worden dat gaat over hersennetwerken. Al met al biedt deze scriptie dus een kleine introductie het tot onderzoeksgebied van de netwerken. Een interessant vakgebied waar we nog veel over te weten kunnen komen.

38

De Statistische Analyse van Netwerken

Recommend Documents