Hoe machtig is het superknooppunt?

Wiskunde Dit jaar ontstond een wiskundig debat over schaalvrije netwerken. Bestaan die echt óveral in de werkelijkheid?

Het is ooit begonnen met een kroegspelletje over acteurs en speelfilms. En het werd een wiskundige theorie over schaalvrije netwerken, die bij elkaar gehouden worden door een aantal superknooppunten. Die zouden overal voorkomen: het internet, het menselijk brein. Maar dit jaar rees er twijfel. Hoe algemeen is dit type netwerken eigenlijk echt?

Het begon allemaal op een avond in 1994 toen drie Amerikaanse studenten van Albright College in Pennsylvania voor de buis zaten om de film Footloose te bekijken. In de hoofdrol: Kevin Bacon. Na de film werd een reclame uitgezonden voor The Air Up There, een film die later dat jaar zou uitkomen, eveneens met Bacon. De studenten vroegen zich af in hoeveel films hij had gespeeld, met wie hij had samengewerkt, en ‘hoe ver’ andere acteurs van hem ‘verwijderd’ zijn.

Tom Cruise is direct met Bacon gelinkt, omdat ze samen in A Few Good Men hebben gespeeld. Carice van Houten is twee stappen van Bacon verwijderd: Van Houten speelde met David Mazouz in Incarnate, Mazouz met Bacon in The Darkness. Grote namen als Bacon verbinden in een paar stappen minder bekende acteurs aan elkaar – een voorbeeld van wat men het ‘kleinewereldeffect’ noemt.

Het Hollywood-netwerk

Six degrees of Kevin Bacon’ werd een beroemd kroegspelletje, maar was ook een onderwerp voor serieus onderzoek. In 1999 maakte Albert-László Barabási (Northeastern University, Boston) met een aantal collega’s een analyse van het Hollywood-netwerk. In de taal van netwerken zijn de acteurs knooppunten in een web waarin de acteurs via links met elkaar verbonden zijn. Twee knooppunten zijn verbonden als de acteurs samen in een film hebben gespeeld. Het aantal links dat uit een knooppunt vertrekt heet de ‘graad’ van dat knooppunt.

Barabási berekende dat de gemiddelde graad in het Hollywood-netwerk 27 was. Veel belangrijker was echter een andere uitkomst, namelijk dat dit gemiddelde niets zegt; daarvoor zijn de fluctuaties rondom het gemiddelde te groot. Meer dan 40 procent van de knooppunten heeft een graad van hooguit tien. Het gemiddelde wordt flink opgestuwd door knooppunten met een zeer hoge graad, de hubs.

Barabási ontdekte dat veel netwerken zijn opgebouwd zoals het acteursnetwerk. Met zijn theorie over deze zogeheten ‘schaalvrije netwerken’ werd hij wereldberoemd. Maar hoe zuiver is die theorie? Onder wiskundigen is daar discussie over. Twee maanden geleden verscheen in Physical Review Research een artikel van vier onderzoekers – twee van de TU Eindhoven, twee van Northeastern University in Boston – die de discussie moet beslechten.

Miljarden zenuwcellen

In de afgelopen twintig jaar zijn veel netwerken bestudeerd. Bijvoorbeeld het wereldwijde web, een netwerk waarvan de meer dan anderhalf miljard websites de knooppunten vormen. Andere voorbeelden: sociale platforms als Facebook en Twitter, of citaties in de wetenschap. Maar ook netwerken van eiwitpolymeren, of het menselijk brein, een netwerk dat uit miljarden zenuwcellen bestaat.

Al deze netwerken hebben gemeen dat ze zijn opgebouwd uit vele knooppunten met een lage graad en een aantal hubs die ervoor zorgen dat de netwerken niet uit elkaar vallen. Megahubs van Twitter zijn Barack Obama en Katy Perry, met allebei meer dan honderd miljoen volgers.

Hubs zijn alomtegenwoordig in de complexe netwerken die theoretici hebben geanalyseerd. Ze verklaren het kleinewereldeffect in al die netwerken. Dankzij die hubs liggen twee willekeurige knooppunten zelden ver van elkaar vandaan. En ze geven inzicht in bepaalde ontwikkelingen. Hoe snel verspreidt een virus zich? Hoe gaan filmpjes viraal op sociale media?

Hoe beschrijf je zo’n netwerk?

Netwerkonderzoekers maken analyses van netwerken met veel knooppunten met lage graad en weinig knooppunten met hoge graad. Maar hoe beschrijf je zo’n netwerk wiskundig? In elk geval niet met de bekende ‘klokkromme’, waarbij alle knooppunten een graad hebben die rondom het gemiddelde schommelt en waarin uitschieters zijn uitgesloten.

Barabási kwam een wiskundige wet op het spoor waaraan de graden van de knooppunten bleken te voldoen: de kans dat een knooppunt graad n heeft, neemt af volgens een zogeheten ‘machtswet’. Dat wil zeggen dat die kans ongeveer evenredig is met 1/na, waarbij a de exponent heet. Bij het Hollywood-netwerk werd de exponent geschat op 2,12. Het www heeft exponent 2,1 voor de ‘inkomende’ links en 2,45 voor de ‘uitgaande’ links.

In tegenstelling tot de klokkromme heeft de grafiek van een machtsfunctie geen piek in het midden. De grafiek begint hoog, wat inhoudt dat er veel knooppunten met een lage graad zijn, en zakt dan langzaam naar beneden. De grafiek heeft een ‘dikke staart’. Het gevolg daarvan is dat extreem hoge uitkomsten weliswaar zeldzaam zijn, maar niet ontbreken.

In een schaalvrij netwerk kunnen probleemloos heel veel (willekeurig gekozen) knooppunten wegvallen

Omdat in netwerken die met een machtswet kunnen worden gemodelleerd de gemiddelde graad zo non-informatief is, ontbreekt het idee van een ‘schaal’ – er is niet één karakteristiek knooppunt. Zulke netwerken worden daarom ‘schaalvrij’ genoemd. Dergelijke netwerken zijn erg robuust. Valt een groot aantal willekeurig gekozen knooppunten weg, dan heeft dat nauwelijks gevolgen voor de stabiliteit van het netwerk. Zelfs het uitvallen van een hub hoeft niet erg schadelijk te zijn. „Triomfalisme bij dood van IS-leider is misplaatst en riskant”, schreef NRC op 29 oktober in het dagelijkse commentaar. Inderdaad, het uitschakelen van Al-Baghdadi mag van grote betekenis zijn, het terroristische netwerk is daarmee nog niet weggevaagd. Toch hebben schaalvrije netwerken een kwetsbare kant. Een gerichte aanval op méérdere hubs kan een netwerk wel degelijk platleggen.

In zijn populair-wetenschappelijke boeken herhaalt Barabási het vaak: in de ‘echte wereld’ zijn schaalvrije netwerken niet de uitzondering maar de norm. Een omstreden claim. Twee onderzoekers van de universiteit van Colorado gooiden eerder dit jaar de knuppel in het hoenderhok: in maart beweerden ze in Nature Communications exact het tegenovergestelde: schaalvrije netwerken zijn zeldzaam. Anna Broido en Aaron Clauset analyseerden 928 netwerken, uit uiteenlopende domeinen zoals biologie, technologie en transport, in grootte variërend van honderd knooppunten tot miljoenen. Hun conclusie: maar 4 procent is schaalvrij.

Volstaat een benadering?

Hoe kan dat? Kort gezegd doordat Broido en Clauset een nogal beperkte definitie van ‘schaalvrij’ hanteerden. Over die definitie is onder de netwerkgeleerden al jaren een heftig dispuut gaande. Moet de machtswet exact gelden? Of volstaat een benadering en zo ja, hoe goed moet die benadering dan zijn? Moet de exponent in de machtsfunctie tussen 2 en 3 liggen? Zulke voorwaarden staan niet in steen gebeiteld en daardoor is het moeilijk te zeggen hoeveel netwerken schaalvrij genoemd mogen worden.

Wat betreft die exponent: kleiner dan 2 kan die niet zijn. Dat zou namelijk tot gevolg hebben dat de graad van de grootste hub groter is dan het aantal knooppunten – dat kan natuurlijk niet. Ligt de exponent tussen 2 en 3, is er sprake van een extreem ‘dikke staart’, wat het begrip ‘schaalvrij’ rechtvaardigt. Is de exponent groter dan 3, wat bijvoorbeeld bij elektriciteitsnetwerken het geval is, neemt de dikte van de staart af – de hubs spelen dan een minder centrale rol. Mag zo’n netwerk dan nog schaalvrij heten?

De auteurs van het stuk in Nature Communications onderscheidden vijf categorieën, van ‘zeer zwak’ tot ‘sterkst’. De eisen voor de sterkste categorie waren streng: de verdeling van de graden moet vanaf een bepaalde waarde een pure machtswet aannemen met een exponent tussen 2 en 3. Slechts 4 procent van de onderzochte netwerken doorstond de strengste test en dat leidde tot de aandacht genererende titel ‘Scale-free networks are rare’.

Gedoogde afwijkingen

Maar Remco van der Hofstad en Pim van der Hoorn (TU Eindhoven) hebben vervolgens met twee collega’s uit Boston een nieuwe definitie van schaalvrije netwerken opgesteld, die alle ruis rondom dit begrip moet wegnemen. Hun artikel, met de geestige titel ‘Scale-free networks well done’, verscheen in oktober in Physical Review Research. Zij gaan nog steeds uit van de machtsfunctie 1/na, die de kans geeft dat een knooppunt graad n heeft. „Ons model laat echter ook verstoringen in de precieze machtswet toe en is dus algemener”, legt Van der Hofstad uit. Voor knooppunten met lage graad mag de afwijking ten opzichte van een pure machtswet nog fors zijn. Hoe hoger de graad, hoe minder afwijkingen worden gedoogd. De staart van de grafiek, die dus iets over de graad van de hubs zegt, wijkt nauwelijks af van een pure machtswet.

De specialisten uit Eindhoven en Boston analyseerden 115 netwerken. Van der Hofstad: „Op netwerkdata hebben we methoden uit de extremewaardenstatistiek toegepast. Die methoden zijn bewezen consistent. Ze gebruiken gegevens van de grootste waarden in de set, omdat die de meeste informatie geven over de staart van de kansverdeling, en zijn dus bij uitstek geschikt om de exponent van de machtswet te schatten.” Wat bleek? Ruim een kwart van de netwerken is ‘schaalvrij’.

„Onze studie werpt een nieuw, rigoureus, licht op de claims van Broido en Clauset”, zegt Van der Hofstad. „Veel conclusies zouden wegvallen als de meeste netwerken geen schaalvrij gedrag zouden vertonen. Maar volgens ons is dat niet zo. In elk geval niet zo stellig als Broido en Clauset beweren.”