Brass Tacks: Complexity Reduction

Kimmo Soramäki and Samantha Cook

When networks get large, particularly in terms of the number of links, making sense of them becomes difficult. This chapter will present several methods for reducing the number of nodes or links in a network, leaving only the most important ones to create a subset of the original network that highlights important relationships and can be visualised more easily. Here we cover complexity reduction algorithms, focusing on threshold methods, spanning trees and planar maximally filtered graphs.

THRESHOLD METHODS

The simplest way to filter nodes or links from a network is by removing those whose property values are larger or smaller than some threshold. Depending on the use case, the threshold may be chosen as some intrinsically meaningful value. Network visualisations may allow for interactive filtering, allowing the user to choose a threshold such that the resulting network visualisation is appropriately uncluttered and easy to read, and also to observe how the network changes as the threshold changes. Alternatively, a threshold may be set such that a fixed number or proportion of nodes/links or node/link values is retained in the network. For example, the projection networks shown