The Class of all Regular Equivalences: Algebraic Structure and Computation

In this paper, we explore the structure of the set of all regular equivalences (White and Reitz 1983) proving that it forms a lattice, and suggest a general approach to computing certain elements of the lattice. The resulting algorithm represents a useful complement to the White and Reitz algorithm, which can only find the maximal regular equivalence of a graph. Using this algorithm, it is possible to compute several well-known equivalences, such as structural equiv-alence (Lorrain and White 1971), automorphic equivalence (Everett and Borgatti 1988) and Winship-Pattison equivalence (Winship and Mandel 1983). In addition, any number of other useful equivalences may be generated, providing suitable mathematical descriptions of them are available