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 equivalence (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.