Technische toelichting netwerkanalyse (pdf)

Kan netwerkanalyse tot betere
herindelingsvoorstellen leiden?
Technische toelichting bij het artikel
Algoritmes (bij: paragraaf 3.3 Netwerkanalytische technieken)
Zoekstrategieën
Hoe worden gemeenten samengevoegd tot gewesten of landsdelen? Voor netwerkanalyse is
dat een kwestie van het clusteren van de knooppunten binnen het netwerk. Dat de
knooppunten in dit geval uit gemeenten bestaan, en het netwerk uit verplaatsingen tussen
die gemeenten, maakt technisch geen verschil. Algoritmes gebruiken verschillende
clusteringstechnieken die wij hier onbesproken moeten laten. Belangrijk is de kwaliteit van
het resultaat. Hoe ‘weet’ een algoritme of de ene onderverdeling van het netwerk beter is
dan de andere? Antwoord: door voor elke gevonden onderverdeling een kwaliteitsscore te
berekenen. Hoe gunstiger de score, des te beter de onderverdeling in ‘gemeenschappen’ of
clusters. De vijf algoritmes van onze netwerkanalyse gebruiken verschillende soorten
kwaliteitsscores.
1. Veel algoritmes gaan af op de modulariteitsscore (modularity). De score Q is het
verschil tussen het feitelijke aantal verbindingen tussen knooppunten binnen de
gemeenschappen (A) en het aantal verbindingen dat daar alleen al op grond van
kans zou zijn geweest (P). Dus: Q = A – P.1 Het aantal kansverbindingen P zou je
kunnen vaststellen door alle bestaande verbindingen tijdelijk bij de knooppunten weg
te halen en vervolgens willekeurig over het netwerk te verdelen (waarbij ervoor moet
worden gezorgd dat elk knooppunt weer hetzelfde aantal verbindingen krijgt als
tevoren). Gelukkig kan P ook eenvoudig worden berekend, zonder ingreep in het
netwerk zelf. Hoe hoger de modulariteitsscore Q, des te beter de onderverdeling. De
algoritmes Louvain, EO en SA maken gebruik van de modulariteitsscore.
2. Algoritme OSLOM laat zich leiden door statistische significantie. Knooppunten die
een significante relatie hebben met een gemeenschap, worden aan die
gemeenschap toegevoegd. Er kunnen overlappende gemeenschappen ontstaan als
knooppunten significante relaties met meer dan één gemeenschap blijken te hebben.
3. De map score (map equation) is de kwaliteitsscore van het algoritme Infomap. In feite
de lengte in bits en bytes van een ‘routebeschrijving’ door het netwerk. De naam van
het algoritme verraadt een relatie met informatie(theorie) en geografie. Om de
onderliggende gedachtegang te begrijpen zou je de gemeenschappen binnen een
netwerk kunnen vergelijken met de pleinen van een stad. Een denkbeeldige
wandelaar (random walker) loopt een volstrekt willekeurige route langs alle adressen.
Pleinen met weinig toegangsstraten zijn ‘blijfpleinen’, omdat onze wandelaar er lang
blijft ronddolen voordat hij bij toeval een uitgang treft. Blijfpleinen zijn voor Infomap
‘goede’ pleinen (echte gemeenschappen). Als er veel blijfpleinen zijn, dan komen er
in de routebeschrijving van onze wandelaar, naast huisnummers, slechts weinig
1
De hier gegeven formule is een schematische variant.
2
namen van pleinen voor (want daarin worden alleen pleinwisselingen vermeld).
Tegenover de blijfpleinen staan de ‘wisselpleinen’ met veel toegangsstraten –
‘slechte’ pleinen, waar onze wandelaar zó weer weg is. Veel wisselpleinen leiden tot
een routebeschrijving die, naast huisnummers, uit veel pleinnamen bestaat. Gevolg:
een lange beschrijving met veel meer bits en bytes. Omgekeerd geldt ook: hoe korter
de beschrijving, des te beter de pleinen. En vertaald naar netwerken: hoe korter de
beschrijving, des te beter de onderverdeling (Rosvall and Bergstrom 2008; Rosvall
and Bergstrom 2011; Fortunato 2010:53).2
Als geen verbetering van de kwaliteitsscore meer optreedt, presenteren de algoritmes hun
uitkomsten. Is dat altijd de beste onderverdeling? Neen. De algoritmes berusten op
benaderende zoekstrategieën; je moet daarom altijd rekening houden met statistische en
andere fouten. Een complete berekening van de beste onderverdeling is alleen voor heel
kleine netwerken mogelijk (in technische termen: de berekening is NP-hard). Bij
modulariteitgestuurde algoritmes krijg je bovendien te maken met de resolutielimiet.
Resolutielimiet
De modulariteitsscore is inzichtelijk, relatief eenvoudig en daardoor populair. Aan
modulariteit kleeft echter ook een nadeel: modulariteitgestuurde algoritmes zien kleine (en
soms ook grote) gemeenschappen over het hoofd (Fortunato and Barthelemy 2007; Clauset,
Moore, and Newman 2008). Wat in dit verband ‘klein’ is hangt af van de omvang of het
‘gewicht’ van het totale netwerk (de gewogen som van alle verbindingen) en van de exacte
manier waarop de score wordt berekend. Je kunt bijvoorbeeld bij de berekening van de
modulariteitsscore Q = A – P vervangen door Q = rA – P, waarbij de eerste term met een
getal r (de resolutieparameter) wordt vermenigvuldigd.3 Hierdoor zoomt het algoritme iets uit
of in, waardoor onderverdelingen op een wat hoger (of lager bij r< 1) schaalniveau in beeld
komen, terwijl andere uit beeld verdwijnen. Is het aantal gemeenschappen tevoren bekend,
dan kan de resolutieparameter dadelijk op een passende waarde worden ingesteld. Maar
wat te doen als dit aantal nu juist een open vraag is? De slimme multiresolutie- of
mesoscales-benadering kan in dat geval soms een uitweg bieden. Daarbij wordt gebruik
gemaakt van de ervaring dat echt bestaande onderverdelingen binnen een netwerk minder
gevoelig zijn voor veranderingen van de resolutieparameter dan meer oppervlakkige of
toevallige onderverdelingen (Arenas, Fernández, and Gómez 2008; Delvenne, S.N. Yaliraki,
and M. Barahona 2009; Lambiotte, Delvenne, and arahona
ranell, ómez, and
Arenas 2011; Fortunato 2010:38 e.v.). De onderstaande grafieken laten zien hoe dat werkt.
2
Infomap gaat uit van het quasi geografische beginsel dat uniciteit van straatnamen alleen is vereist
binnen dezelfde stad, maar niet tussen steden. En in ons voorbeeld: dat op ieder ‘plein’ de
huisnummering opnieuw bij 1 begint. Een vorm van efficiëntie bij naamgeving (namespaces) die ook
op tal van andere gebieden wordt toegepast. Zie artikel voor literatuurverwijzingen.
3
Het is ook mogelijk de tweede term P met een getal te vermenigvuldigen (Q = A - λP) of
andersoortige bewerkingen toe te passen waardoor de resolutie verandert.
3
Grafiek 1 Mesoscales
Extremal optimization [EO]
Simulated annealing [SA]
Op de horizontale as de (oplopende) waarde van de resolutieparameter (bij EO r en bij SA λ) en op
de verticale as het aantal gevonden clusters of communities (Ncomm).
Voor beide grafieken zijn de algoritmes een groot aantal malen aan het werk gezet bij
oplopende waarden van de resolutieparameter. Elk van beide krommen wordt onderbroken
door ‘plateaus’ waar het algoritme ondanks oplopende parameterwaarden nog enige tijd blijft
vasthouden aan het gevonden aantal gemeenschappen Ncomm. Bij EO blijken de
onderverdelingen met 2, 5, 10, 38 en 96 gemeenschappen robuuster dan de rest. Bij SA zijn
de corresponderende aantallen 8, 10 en 30.4
4
Zie Tabel 1 van het artikel. In deze tabel worden soms iets andere aantallen genoemd omdat in een
latere fase enkele instabiele individuele clusters uit het eindresultaat zijn verwijderd.
4
Robuustheidstoets van de uitkomsten (bij: paragraaf 4.3 Toetsing
robuustheid)
Naarmate uitkomsten van verschillende algoritmes dichter bij elkaar liggen, is de kans kleiner
dat ze het product zijn van ‘toevalligheden’ zoals de specifieke vertekening van een
algoritme of statistische fluctuaties. Iets vergelijkbaars geldt voor het geval uitkomsten (van
verschillende of dezelfde algoritmes) inpasbaar zijn in één en hetzelfde hiërarchische
systeem, waarbij de gevonden gewesten geheel en al binnen de gevonden landsdelen
blijken te liggen.
Hoge schaalniveaus. Drie algoritmes komen tot een onderverdeling van Nederland in vijf
deelgebieden. De kaartbeelden die zij daarbij produceren blijken echter nogal uiteen te
lopen. De verschillen zijn gemeten met behulp van de index NVI, een maat voor de
‘informatie-afstand’ tussen twee onderverdelingen.5 Hoe lager de index, hoe kleiner het
verschil. De indexwaarden van deze onderverdeling zijn een stuk minder gunstig dan bij een
onderverdeling in acht deelgebieden (gemiddelde NVI=0,16 tegen 0,10).6 Daarom bekijken
wij hier alleen de laatstgenoemde onderverdeling.
Tabel 1 NVI-indexen voor hoge schaalniveaus (8 landsdelen)
SA8
EO8
OSLOM13
Louvain8
Infomap8
SA8
0,07
0,11
0,17
0,13
EO8
0,05
0,16
0,12
OSLOM13
0,16
0,09
0,15
Hoe lager de index, hoe kleiner het verschil tussen de algoritmes.
SA8 = SA uitdraai met 8 deelgebieden enz.
OSLOM13 is door het grotere aantal deelgebieden niet geheel vergelijkbaar.
De indexen laten zien dat de resultaten van EO en SA het dichtst bij elkaar liggen
(NVI=0,05), op de voet gevolgd door SA en Infomap (zie Tabel 1). De deelgebieden van
Louvain wijken wat meer af, behalve van EO (NVI=0,09). De grootste afstand tot de rest
vertoont Oslom, maar dat zal ook samenhangen met het afwijkende aantal deelgebieden.
Lage schaalniveaus. Bij een indeling in 23 tot 56 gewesten liggen SA en Infomap het dichtst
bij elkaar (NVI=0,07); EO en SA (0,13) en EO en Infomap (0,15) verschillen meer van
elkaar. Ook hier toont Oslom een nog minder gunstig beeld (0,17 – 0,22), terwijl Louvain hier
natuurlijk ontbreekt. Ter vergelijking zijn de NVI-waarden met de COROP-indeling in de tabel
opgenomen (zie Tabel 2).
5
Normalized Variation of information Index. NVI is een maat voor de ‘informatie-afstand’ tussen twee
onderverdelingen. Een verwante index is de Normalized Mutual information Index (NMI), die voor
hetzelfde doel kan worden gebruikt. Zie: Fortunato 2010:77–79; Danon et al. 2005; Meilă
7.
Software beschikbaar in Radatools (zie: Netwerkanalytische programmatuur).
6
NVI is een afstandsmaat: hoe lager het getal, des te kleiner de afstand en des te groter de
overeenkomst.
5
Tabel 2 NVI-indexen voor lage schaalniveaus
Infomap56
SA28
EO38
OSLOM39
COROP40
Infomap23 Infomap56 SA28
EO38
OSLOM39
0,12
0,07
0,14
0,15
0,16
0,13
0,19
0,19
0,17
0,22
0,20
0,20
0,20
0,22
0,27
Hoe lager de index, hoe kleiner het verschil tussen de algoritmes.
Hiërarchische samenhangen. Om vast te stellen of de hogere en lagere schaalniveaus
sluitende hiërarchische systemen vormen kan de Wallace-index worden gebruikt.7 Bij een
zuiver hiërarchische relatie tussen de uitkomsten (de deelgebieden op het lagere
schaalniveau zijn volledig inliggend in die van het hoger niveau) is de index gelijk aan 1. Dat
is het geval bij Infomap8 en Infomap56. Infomap, SA en EO vertonen sterke (maar buiten het
genoemde geval geen perfecte) hiërarchische relaties (zie Tabel 3).
Tabel 3 Wallace-index (hoog-laag)
Infomap23 Infomap56 SA28
EO38
OSLOM39
Infomap8
0,97
1,00
0,92
0,92
0,83
SA8
0,95
0,98
0,89
0,89
0,82
EO8
0,97
0,97
0,95
0,95
0,82
OSLOM5
0,91
0,94
0,91
0,88
0,84
OSLOM13
0,87
0,92
0,84
0,85
0,78
Hoe hoger de index, hoe beter de hiërarchische relatie.
7
Bij een perfect hiërarchisch systeem mogen twee gemeenten die op een hoger schaalniveau in
verschillende landsdelen zijn ondergebracht op een lager schaalniveau niet in hetzelfde gewest
terechtkomen. Andersom mag wel. De Wallace-index houdt met deze asymmetrie rekening door twee
cijfers te berekenen: van hoog naar laag en van laag naar hoog. Alleen het eerste cijfer is hier van
belang. Zie voor de Wallace-index: Fortunato 2010:77–79; Meilă
7:875; voor software zie:
Netwerkanalytische programmatuur.
6
Netwerkanalytische programmatuur (bij: paragraaf 3.3
Netwerkanalytische technieken)
Algoritmes
-
Louvain - beschikbaar in de desktopprograma’s
ephi en Pajek
-
Extremal Optimization (EO) - uitvoerbaar bestand binnen Radatools
Simulated Annealing (SA) – code AndreaLancichinetti
Oslom – code AndreaLancichinetti
Infomap – code Mapequation
Programmatuur
-
Gephi (Levallois 2013): https://gephi.org
Pajek (De Nooy, Mrvar, and Batagelj 2005): http://pajek.imfm.si/doku.php
Radatools: http://deim.urv.cat/~sgomez/radatools.php
Code AndreaLancichinetti: https://sites.google.com/site/andrealancichinetti/software
Code Mapequation: http://www.mapequation.org/code.html
Indexen
-
NVI, NMI, Wallace-index (Danon et al. 2005; Meilă
Radatools
7) – beschikbaar binnen
7
Databestand (bij: paragraaf 3.1 Verplaatsingenonderzoek CBS)
Het gebruikte databestand bestaat uit een samenvoeging van de jaren 2010, 2011 en 2012
van het jaarlijks door het CBS uitgevoerde onderzoek naar het verplaatsingsgedrag binnen
Nederland. Omwille van de betrouwbaarheid van de resultaten op lagere schaalniveaus
worden gegevens over drie jaren gebruikt. Voorafgaand aan de analyse zijn enkele kleine,
maar storende onvolkomenheden met betrekking tot vertrek- en/of aankomstgemeenten
binnen de deelbestanden 2010 en 2011 zo goed mogelijk gecorrigeerd of verwijderd. De
onvolkomenheden zijn doorgegeven aan het CBS. In het deelbestand 2012 zijn ze niet
aangetroffen.
De bestanden zijn verkregen via Data Archiving and Networking Services (DANS).
Gegevens datasets
-
Onderzoek verplaatsingen in Nederland 2010 – OVIN 2010; Centraal Bureau voor de
Statistiek / Rijkswaterstaat; DANS id: 46383
Onderzoek verplaatsingen in Nederland 2011 – OVIN 2011; Centraal Bureau voor de
Statistiek / Rijkswaterstaat; DANS id: 50335
Onderzoek verplaatsingen in Nederland 2012 – OVIN 2012; Centraal Bureau voor de
Statistiek / Rijkswaterstaat; DANS id: 54132
Verdere informatie:
[email protected]

Download Report