Interactive visualization of large graphs

In de laatste twee decennia heeft de computer de mens in staat gesteld enorme hoeveelheden informatie te vergaren, te bewaren en te bewerken. Als een direct gevolg van deze virtuele vloedgolf aan informatie is het voor de moderne mens steeds moeilijker om te bepalen welke informatie voor hem relevant is. Dit probleem wordt nog eens verergerd door het feit dat het moeilijk is om het begrip ‘relevante informatie’ vooraf te specificeren. Er is daarom een duidelijke behoefte aan verkennende gereedschappen die het mogelijk maken dergelijke informatie te achterhalen, voordat exact bekend is wat relevant is en wat niet. Visualisatie (meer specifiek, computer ondersteunde visualisatie) is een onderzoeksgebied dat zich bezig houdt met het gebruiken van computer grafiek om grote hoeveelheden data inzichtelijk te maken. Denk bijvoorbeeld aan gegevens uit windtunnels, computersimulaties of atmosferische metingen. Dit proefschrift gaat over het inzichtelijk maken van de informatie in abstracte data, zoals bijvoorbeeld de inhoud van databases, grote organisatiestructuren of communicatiepatronen. Abstracte data heeft geen voor de hand liggende ruimtelijke representatie, wat het zichtbaar maken bemoeilijkt. We beperken ons hier tot abstracte gegevens in de vorm van netwerken (ook wel grafen genoemd). Deze gegevens bestaan uit een verzameling nodes (bijvoorbeeld personen, stukjes software of internetpagina’s) waartussen relaties (bijvoorbeeld ‘is een vriend van’, ‘gebruikt’ of ‘verwijst naar’) zijn gedefinieerd. Een veelgebruikte manier om een graaf visueel te maken is het node-link diagram, een verzameling symbolen verbonden door lijnen. Het automatisch genereren van dergelijke diagrammen is echter niet eenvoudig, zelfs als de graaf relatief klein is. Grotere grafen (met meer dan een paar duizend nodes) vormen een nog groter probleem en resulterende diagrammen zijn vaak erg moeilijk leesbaar. De onderzoeksvraag die dit proefschrift probeert te beantwoorden is dan ook: hoe kunnen we visualisatie gebruiken om inzicht te krijgen in de structuur en inhoud van grote grafen, met duizenden of zelfs miljoenen nodes? In Hoofdstuk 2 karakteriseren we het probleem aan de hand van drie hoofdaspecten: data (wat zijn de karakteristieken van de gegevens?), doel (wat wil de gebruiker met deze gegevens?) en context (wat zijn de randvoorwaarden?). Hoofdstuk 3 beschrijft bestaande technieken die nuttig kunnen zijn bij het ontwerpen van een visualisatie en geeft een overzicht van de huidige toestand van het onderzoeksgebied. In Hoofdstuk 4 selecteren we vier verschillende versies van het visualisatie pro- bleem op basis van de karakteristieken in Hoofdstuk 2 en construeren daar vervolgens visualisaties voor. Hoofdstuk 5 beschrijft Beamtrees, een visualisatie methode voor boomstructuren die is gebaseerd op het gebruik van overlapping om relaties weer te geven. Als toepassingsgebied is de bestandsstructuur van een harde schijf gekozen. Een kwantitatieve gebruikerstest is uitgevoerd om onderzoeken of er een betere informatie overdracht plaatsvond. In Hoofdstuk 6 wordt een techniek beschreven die is ontwikkeld voor het visualiseren van eindige automaten. Een eindige automaat beschrijft het gedrag van een computerproces op een elementair niveau. Bestudering van deze automaten kan leiden tot het ontdekken van fouten in software zonder deze expliciet te testen. Eindige automaten kunnen in grootte vari¨eren van tientallen mogelijke toestanden tot honderden miljoenen toestanden. De ontwikkelde visualisatie kan de globale structuur en symmetrieen weergeven in automaten van een paar miljoen toestanden. Hoofdstuk 7 is een case-study in het visualiseren van software systeem dat ontwikkeld werd bij Philips Medical Systems. In veel systemen wordt door een groep software architecten een globaal ontwerp gemaakt, dat daarna door een veel grotere groep programmeurs wordt ge¨implementeerd. Tijdens dit implementatie proces wordt vaak (bewust of onbewust) afgeweken van het oorspronkelijke ontwerp, wat invloed kan hebben op de uiteindelijke kwaliteit. De ontwikkelde visualisatie is gebaseerd op een matrix representatie van een graaf en geeft architecten een overzicht van het ontwikkelde systeem, zowel op architectuur niveau als op code-niveau. Dit prototype is later uitgebreid met mogelijkheden om ook grafen aan te kunnen die zo groot zijn dat ze niet in het geheugen van een computer passen. Hoofdstuk 8 beschrijft een visualisatie voor grafen waarin elke node vanuit een willekeurige node bereikbaar is in een klein aantal stappen. Deze zogenaamde ’small world’ graphs komen vaak voor in de praktijk en zijn moeilijk te visualiseren vanwege hun sterk verbonden karakter. De methode gebruikt een nieuw plaatsings algoritme om interne structuren zichtbaar te maken en een nieuwe interactiemethode die het mogelijk maakt om tegelijkertijd gedetailleerde informatie en de globale context te zien. In Hoofdstuk 9 vergelijken we de vier ontwikkelde prototypes. Een eerste conclusie is dat als we een visualisatie schaalbaar willen maken, we vaak karakteristieke eigenschappen van de te visualiseren data gebruiken om deze te vereenvoudigen. Hierdoor is het vaak moeilijk om een visualisatie te hergebruiken voor een ander applicatiegebied. Aan de hand van de bovenstaande protoypes destilleren we vier kernproblemen die optreden tijdens de ontwikkeling van een visualisatie van een grote graaf. Deze problemen zijn: • Representatie: Hoe kiezen we een geschikte visuele representatie voor een graaf? • Abstractie: Gegeven een grote graaf hoe cre¨eren we een kleinere graaf die de hoofdeigenschappen van de grotere behoudt? • Navigatie: Hoe stellen we een gebruiker in staat een geabstraheerde graaf te verkennen zonder daarbij het overzicht te verliezen? • Mapping: Hoe koppelen we de daadwerkelijke informatie en de abstracte