Verbondenheid in grafen met lage boombreedte: Algoritmische berekening van de Shapleywaarde

Na de aanslagen op het World Trade Center in New York in 2001 rees de urgente vraag naar het brein achter de organisatie. Deze vraag werd na verloop van tijd beantwoord, maar wiskundigen vroegen zich af of dit probleem ook speltheoretisch aangepakt kon worden. Er is een netwerk gemaakt van de onderlinge relaties tussen alle betrokkenen. Al snel werd vermoed dat degene met de meeste verbindingen de belangrijkste was uit het terrorismenetwerk. Meer specifiek, als we het netwerk als graaf presenteren, dat de knoop met de hoogste Shapleywaarde ook de belangrijkste persoon representeert. Echter is de Shapleywaarde computationeel heel lastig. Om deze te berekenen moest het netwerk kleiner gemaakt worden, waardoor de gevonden waarde afwijkt van de werkelijke waarde. In 2018 hebben T.C. Van der Zanden, H.L. Bodlaender en H.J.M. Hamers [9] een algoritme ontwikkeld, waarmee de Shapleywaarde van het totale netwerk berekend kan worden in een fractie van de tijd die nodig was om het gereduceerde...Show moreNa de aanslagen op het World Trade Center in New York in 2001 rees de urgente vraag naar het brein achter de organisatie. Deze vraag werd na verloop van tijd beantwoord, maar wiskundigen vroegen zich af of dit probleem ook speltheoretisch aangepakt kon worden. Er is een netwerk gemaakt van de onderlinge relaties tussen alle betrokkenen. Al snel werd vermoed dat degene met de meeste verbindingen de belangrijkste was uit het terrorismenetwerk. Meer specifiek, als we het netwerk als graaf presenteren, dat de knoop met de hoogste Shapleywaarde ook de belangrijkste persoon representeert. Echter is de Shapleywaarde computationeel heel lastig. Om deze te berekenen moest het netwerk kleiner gemaakt worden, waardoor de gevonden waarde afwijkt van de werkelijke waarde. In 2018 hebben T.C. Van der Zanden, H.L. Bodlaender en H.J.M. Hamers [9] een algoritme ontwikkeld, waarmee de Shapleywaarde van het totale netwerk berekend kan worden in een fractie van de tijd die nodig was om het gereduceerde probleem op te lossen. In deze scriptie wordt dit algoritme besproken en hoe dit algoritme de Shapleywaarde van een knoop kan berekenen. Hiervoor wordt eerst de benodigde achtergrond samengevat en doorgenomen en worden enkele stellingen bewezen. De bedoeling was eerst om een code te schrijven aan de hand van het algoritme om het vervolgens toe te kunnen passen op metronetwerken. Echter bleek dit een onbegaanbaar pad te zijn. In het artikel dat besproken wordt in deze scriptie staat een aantal foutjes, die gedeeltelijk repareerbaar bleken. Ook zijn niet alle details volledig uitgewerkt in het artikel. Dit maakte het schrijven van een correcte code te tijdrovend, hetgeen ertoe leidde dat dit plan werd stilgelegd na een jaar. Besloten is toen om meer te richten op het toelichten van het algoritme en, waar mogelijk, de kleine foutjes te repareren. Echter is dit ook maar gedeeltelijk gelukt. De achtergrondartikelen zijn vaak wat kort door de bocht. De stellingen zo helder mogelijk te formuleren en bewijzen was hierdoor wat lastig. Het kort door de bocht zijn, geldt in het bijzonder voor het artikel met het algoritme. Er is zeer veel tijd besteed aan het identificeren en repareren van fouten in het algoritme, en toch is het nog steeds niet gelukt om dit zodanig te interpreteren dat het goede uitkomsten geeft. Het is in dit licht dan ook opmerkelijk dat [9] in 2022 nog steeds niet gepubliceerd is. Wel is het gelukt te identificeren waar in het algoritme iets misloopt.Show less

Leiden University Student Repository

Documents

In Collections

Verbondenheid in grafen met lage boombreedte: Algoritmische berekening van de Shapleywaarde