Tangled webs: A practical investigation of graph tangles.

Many tasks in network theory involve finding highly cohesive regions of a network, raising the question of what it means to be cohesive. Tangles, introduced by Robertson and Seymour in 1991 to answer questions in abstract graph theory, are one way of answering this question.

In an intuitive sense, a cohesive region is one that can’t be pulled apart easily. The tangle definition takes this idea and formalises it, providing a general structure that can be used in a range of settings. What it means to be “pulled apart” is defined differently for tangles in different settings, creating a consistent idea of cohesiveness that can be applied across multiple domains, including graphs and other more abstract systems.

I examine the applicability of tangles to two practical domains that seek cohesive regions of their objects of interest: community detection and image segmentation. A community is a region that is more highly connected internally than externally, but there are a number of different definitions of “highly connected”, and a number of different algorithms for identifying these regions. I examine how well tangles describe communities, and whether communities identified by tangles correspond better to one such definition than others. Image segmentation involves separating an image, represented as an array of pixels, into parts that correspond to some object or component in the image. I explore how well tangles can identify such components.

In order to perform practical comparisons, I developed and implemented an algorithm for finding tangles. I describe this algorithm and, since this task is very computationally intensive, I present and validate a number of strategies used to reduce the processing load. I then present experiments using this algorithm in the applications of interest.

The correspondence between tangle communities and other definitions was found to vary significantly between different networks. In some cases, tangles identified clearly distinct regions of the network similar to those found by other methods, whereas in other cases, tangles did not identify communities even in graphs with known community structure.

A single tangle might resemble a single community quite closely, while the set of all tangles does not create a community structure aligning with any other method. A tangle set might contain a number of tangles corresponding to single vertices or pairs of vertices, which does not match an intuitive picture of what a community means. This tendency of tangles to isolate one or two vertices was also found for images. Tangles could not always distinguish a simple shape on a plain background, instead pointing to small groups of pixels in the corners or edges of the shape.

Overall the results suggest that, while there are commonalities between the network structures identified by tangles and those used in the practical applications of community detection and image segmentation, how tangles define cohesiveness differs from how it must be defined to be used effectively in these applications.