Calculating role similarities: An algorithm that helps determine the orbits of a graph

The orbits or a graph, diagraph or network provide an effective definition for role equivalence since they are a natural generalization of the principle of substitutability of structural equivalence. Calculation of the orbits is a computationally difficult task but in this paper we present a fast and efficient algorithm which finds the orbits of a large class graph. In addition, we suggest a simple measure of role similarity based upon the constructions contained within the algorithm. This makes it possible to perform a role analysis when only a limited number of automorphisms exist.