Summarising and visualising large acyclic graphs

Details

Supervisors

Mens, Kim ; Maudoux, Guillaume

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] en sciences informatiques

Abstract

The purpose of this thesis is to explore ways of summarising large acyclic graphs. Past a certain threshold in the amount of nodes or edges, a human being will not be able to extract relevant information from a graph visualisation. This threshold may depend, among other elements, on the graph layout and the “kind” of relevant information. Aside from human limitations, a computer simply cannot build a visual representation of a graph past a certain threshold in the amount of nodes or edges. Once again the threshold depends on different factors, such as the required layout, the amount of edges per node, and the computer building the visualisation. We are here interested in building visual representations such that the amount of nodes and edges is below the human threshold, which is unsurprisingly (usually)inferior to the computer threshold. Of course, summarising comes at a cost. Determining the set of relevant information is not trivial and depends on the purpose of the summary. For any non-trivial graph, there isn’t a single summary and we might very well be unable to build an exhaustive, strict hierarchy between the possibly many summaries.To make large graphs understandable by a human being, we’ll explore ways of summarising an original graph by applying to this graph a sequence of filters.A filter is used to merge similar nodes, drop parts of the graph that are deemed uninteresting, or enrich information about nodes and edges. To produce different summaries, we make use of a desktop application to add, remove and swap filters, usually without repeating the whole summarisation process.