Graph Contraction on Attribute-Based Coloring

Graph structures are nowadays pervasive in Big Data. It is often useful to regroup such data in clusters, according to distinctive node features, and use a representative element for each cluster. In many real-world cases, clusters can be identified by a set of connected vertices that share the result of some categorical function, i.e. a mapping of the vertices into some categorical representation that takes values in a finite set C. As an example, we can identify contiguous terrains with the same discrete property on a geographical map, leveraging Space Syntax. In this case, thematic areas within cities are labelled with different colors and color zones are analysed by means of their structure and their mutual interactions. Contracted graphs can help identify issues and characteristics of the original structures that were not visible before. This paper introduces and discusses the problem of contracting possibly large colored graphs into much smaller representatives. It also provides a novel serial but parallelizable algorithm to tackle this task. Some initial performance plots are given and discussed together with hints for future development.