Some Results on Colored Network Contraction

Networks are pervasive in computer science and in real world applications. It is often useful to leverage distinctive node features to regroup such data in clusters, by making use of a single representative node per cluster. Such contracted graphs can help identify features of the original networks that were not visible before. As an example, we can identify contiguous nodes having the same discrete property in a social network. Contracting a graph allows a more scalable analysis of the interactions and structure of the network nodes. This paper delves into the problem of contracting possibly large colored networks into smaller and more easily manageable representatives. It also describes a simple but effective algorithm to perform this task. Extended performance plots are given for a range of graphs and results are detailed and discussed with the aim of providing useful use cases and application scenarios for the approach.