The Regular Coloration of Graphs
Martin G. Everett, Stephen P. Borgatti · 1997
Abstract A regular coloration of a graph is an assignment of colours to the vertices which obeys the rule that if two vertices are coloured the same then their neighborhoods have the same set of colours. If the graph represents a social system then vertices which are coloured the same can be thought of as playing the same role. We investigate the concept of regular coloration and present some results which allow for the development of algorithms which can be used to analyze social network data. Graph theory has been extensively used as a model in the social sciences. The vertices of a graph represent individuals or groups of individuals. The groups can be as diverse as political parties, countries or family groups. The edges represent interpersonal or intergroup relations, for example “likes”, “hates”, “agrees”, “communicates with”, “married to”, “allied with”, “trades with” etc. Clearly this model can give rise to both digraphs and graphs.