Methodology and Statistics
International Conference, 24  27 September 2000
Hotel Bor and Castle Hrib, Preddvor, Slovenia
Computing Regular Equivalence: practical and theoretical issues.
Martin Everett
School of Computing and Mathematical Sciences
The University of Greenwich
Social network analysts have tried to capture the idea of social role
explicitly by proposing a framework that precisely gives conditions
under which grouped actors are playing equivalent roles.
They term these methods postional analysis techniques.
The most general definition is regular equivalence which captures
the idea that equivalent actors are related in a similar way to
equivalent alters. Regular equivalence gives rise to a whole class
of partitions on a network. Given a network we have two different
computational problems. The first is how to find a particular
regular equivalence. An algorithm exists to find the largest
regular partition but there are no efficient algorithms to test
whether there is a regular kpartition. That is a partition into
k groups that is regular. In addition, when dealing with real data,
it is unlikely that any regular partitions exist. To overcome
this problem relaxations of regular equivalence have been proposed
along with optimisation techniques to find nearly regular partitions.
In this paper we review the algorithms that have been developed to
find particular regular equivalences and look at some of the recent
theoretical results which give an insight into the complexity of
finding regular partitions.
Key words: regular partitions
