Hoe genereer (of creër) je een sociaal netwerk?

09-09-2019

15.45

Aula

When Nash met Markov: Novel results for pure Nash equilibria and the switch Markov chain

P.S. Kleer

prof.dr. G. Schäfer, prof.dr. A. Schrijver

School of Business and Economics

Economie

Promotie

Het proefschrift van Pieter Kleer bevat theoretische resultaten m.b.t. twee problemen in de vakgebieden wiskunde en theoretische informatica: het berekenen en analyseren van Nash-evenwichten in congestiespellen en het analyseren van simpele algoritmen voor het generen van grafen. 

Het eerste probleem betreft het analyseren van theoretische spellen die gebruikt kunnen worden om, bijvoorbeeld, verkeerscongestie te modelleren. We zijn geïnteresseerd in evenwichtssituaties waarin het verkeer zich dusdanig heeft verdeeld over het wegennetwerk, dat geen enkele weggebruiker de behoefte heeft om een andere route te kiezen. Een van de belangrijkste resultaten hier is het feit dat onzekerheid in reistijden een negatief gevolg kan hebben op de kwaliteit van dit soort evenwichtssituaties. Dit betekent dat de gemiddelde reistijd veel hoger kan zijn dan nodig is (indien er geen onzekerheid in de reistijden zou zijn geweest). 

Het tweede probleem betreft het analyseren van algoritmen voor het generen van grafen. Een graaf is een verzameling van zogenoemde punten en lijnen. Een goed voorbeeld hier is de Facebook graaf. De punten zijn mensen met een Facebook account en er is een lijn tussen twee mensen als ze bevriend zijn op Facebook. In veel vakgebieden is er interesse in het analyseren van sociale netwerken, zoals deze Facebook graaf. Om dit te kunnen doen, wil men veel grafen kunnen generen (of creëren) die lijken op de Facebook graaf. Het belangrijkste resultaat in dit proefschrift is een nieuwe analyse van een simpel algoritme voor dit probleem. 

Meer informatie over dit proefschrift in DARE