Finding and testing regular equivalence

A natural way to test for the significance of a given approximation to a regular equivalence is to compare its degree of regularity to that of a large number of random permutations of the data matrix. However, if the original equivalence was chosen to be regular in the first place, this method is invalid. Now suppose we have an algorithm (regular equivalence) for approximating the best regular equivalence for network data. If we then apply regular equivalence to a large number of random permutations of the data, we now have a valid test for the regularity of the data, relative to the regular equivalence algorithm. This approach eliminates very slow algorithms, such as simulated annealing, since the algorithm must be applied to hundreds of permuted data matrices. On the other hand, simple greedy algorithms are notorious for finding inferior local optima. Instead, we use a variable-depth search algorithm pioneered by Kernighan and Lin, and generalized by Fiduccia and Matheyses. Using this method, regularity was found not to be present in the data examined. (C) 2002 Elsevier Science B.V. All rights reserved.