Contents - Index


NETWORKS > ROLES & POSITIONS > MAXIMAL REGULAR > REGE

PURPOSE Compute a measure of regular equivalence using the standard REGE algorithm.

DESCRIPTION Two actors are regularly equivalent if they are equally related to equivalent others.  REGE is an iterative algorithm, within each iteration a search is implemented to optimize a matching function.  

The matching function between vertices i and j is based upon the following.  For each k in i's neighborhood search for an m in j's neighborhood of similar value.  A measure of similar values is based upon the absolute difference of magnitudes of ties.  This measure is then weighted by the degree of equivalence between k and m at the previous iteration.  It is this match that is optimized.  This is summed for all members of i's neighborhood over all relations and normalized to provide the current iteration's measure of equivalence between i and j.  The procedure is repeated for all pairs of vertices for a fixed number of iterations.

The result of this iterative procedure is a symmetric similarity matrix which provides a measure of regular equivalence.  This matrix is automatically submitted to a single link hierarchical clustering routine.

PARAMETERS
Input dataset:
Name of file containing data to be analyzed Data type: Valued graph.  Multirelational.
Undirected data will give a trivial result with all non-isolate vertices being equivalent.
 
Maximum number of iterations: (Default = 3).
Number of iterations to be performed.  Larger values increase the differentiation between vertices. A value of 3 has often been used and is now customary. 

Convert data to geodesic distances: (Default = NO).
YES performs the analysis on the valued distance matrix.  If symmetric data is to be analyzed then this option will provide a non-trivial analysis of the data.

Diagram Type: (Default = 'Dendrogram')
The clustering diagram can either be a Tree Diagram or a Dendrogram.

(Output) similarity matrix: (Default = 'Rege').
Name of file which contains REGE measure of regular equivalence described in LOG FILE.

(Output) Partition Matrix: (Default = 'Regepart').
Name of file which contains a partition indicator matrix corresponding to the single link hierarchical clustering displayed in the LOG FILE.  A value of k in a row labeled i and column j means that vertex j is in partition k at level i.  Vertex k is always a member of partition k and is a representative label for the group. This matrix is not displayed in the LOG FILE.


LOG FILE Single link hierarchical clustering dendrogram (or tree diagram) of the regular similarity measure. The level at which any pair of actors are aggregated is the point at which both can be reached by tracing from the start to the actors from right to left. The diagram can be printed or saved. Parts of the diagram can be viewed by moving the mouse to the split point in a tree diagram or the beginning of a line in the dendrogram and clicking. The first click will highlight a portion of the diagram and the second click will display just the highlighted portion. To return to the original right click on the mouse. There is also a simple zoom facility simply change the values and then press enter. If the labels need to be edited (particularly the scale labels) then you should take the partition indicator matrix into the spreadsheet editor remove or reduce the labels and then submit the edited data to Tools>Dendrogram>Draw. 

Behind the dendrogram is an alternative cluster diagram. The columns have been rearranged and labeled.  A '' in row labeled i column label j indicates that vertex j is in a singleton cluster at level i.  An 'X' indicates that vertex j is in a non-trivial cluster at level i, all other members of j's cluster are found by tracing along the row labeled i in both directions from column j until a space is encountered in each direction.  The column labels corresponding to an 'X' which are connected to j's X are all members of j's cluster at level i.

  
An actor by actor REGE similarity matrix.  Values vary between 0 and 100.  A value of 100 indicates strict regular equivalence.

  
TIMING O(N^5).

COMMENTS The values obtained for non-equivalent vertices are not robust measures of equivalence.  The number of iterations affects these values there is little correlation between the values from one iteration to the next, even at the rank order level. This situation is improved if the number of iterations are increased.

For these reasons users with binary or nominal data are advised to use CATEGORICAL  REGE

REFERENCES White D R (1984).  REGE: A regular graph equivalence algorithm for computing role distances prior to block modelling.  Unpublished manuscript.  University of California, Irvine.

White D R and Reitz K P (1983).  Graph and semi-group homomorphisms on networks of relations.  Social Networks 6, 193-235.