Contents - Index

NETWORKS > ROLES > MAX REGULAR > OPTIMIZATION

PURPOSE Optimizes a cost function which measures the degree to which a partition forms regularly equivalent sets for binary data using a tabu search method.

DESCRIPTION Two actors are regularly equivalent if they are equally related to equivalent others.  Given a partition of a network then the partition divides the adjacency matrix into matrix blocks.  In a binary matrix the partition is regular if each block either contains all zeros (a zero block) or at least one 1 in every row and every column (a one-block).  A measure of the extent to which a partition is regular is therefore given by the minimum number of changes required to the elements of the adjacency matrix to satisfy this criteria.  

This cost function assumes that any block above a certain specified density will be changed to a one-block and below this density to a zero-block.  The routine attempts to optimize this cost function to try and find the best partition of the vertices into a specified number of blocks.

PARAMETERS
Input dataset 
Name of file containing dataset to be analyzed. Data type: Digraph.

Number of blocks: (Default = 2).
Number of groups or blocks into which the vertices are to be assigned.

Are diagonal values valid: (Default = NO).
Whether diagonals are to be included in cost function.

Maximum # of iterations in a series: (Default = max(2,n/3)).
The algorithm starts from an arbitrary partition and attempts to decrease the cost by taking the steepest descent.  If the cost cannot be reduced then the algorithm continues its search in the neighborhood of the current partition.  

This search direction is a mildest ascent direction and from there new search directions are explored.  This exploration only continues for a fixed number of iterations in a series.  If no improvement is made after the fixed number of iterations the algorithm terminates with the current minimum.  Increasing the parameter gives a more exhaustive and therefore slower search.

Length of time in penalty box: (Default = 10).
If the algorithm makes an ascending step then it is possible that the best possible descending step is the reverse of the direction just taken.  This parameter prohibits a move along the reverse direction for a set number of steps.  

The larger the value the more difficult it will be to come back to a previously explored local minimum, however it will also be more difficult to explore the vicinity of that minimum.  

The default of 10 has been shown experimentally to be the most useful.

Number of random starts: (Default = 10 - 2logn).
The whole procedure is repeated with a different initial partition.  The best of these are then selected as a minimum.

Random Number Seed:
The random number seed generates the initial partition.  UCINET generates a different random number as default each time it is run.  This number should be changed if the user wishes to repeat the analysis with different initial configurations.  The range is 1 to 32000.

Cut off value for zero blocks: (Default = 0.010).
In evaluation of cost, blocks with density equal to or below this value will be measured from zero-blocks and above this value from one-blocks.

Output Partition Dataset: (Default = 'RBMPart').
Name of output file which contains a partition indicator vector.  This vector has the form (k1,k2,...ki...) where ki assigns vertex i to block ki, so that (1 1 2 1 2) assigns vertices 1, 2 and 4 to block 1 and, 3 and 5 to block 2.  This vector is not displayed in the LOG FILE.

Output Sets Dataset: (Default = 'RBMSets')
Name of the output file to contain the block by actor incidence matrix.


LOG FILE The value of the cost function or fit.  A value of zero represents exact regular equivalence.

List of blocks.  Each block is labeled and is specified by the vertices it contains.

The blocked adjacency matrix.  The rows and columns of the original adjacency matrix are permuted into blocks.  The adjacency matrix is displayed in terms of the matrix blocks it contains.

TIMING Each iteration of the tabu search algorithm is O(N^2).

COMMENTS Care should be taken when using this routine.

The algorithm seeks to find the minima of the cost function.  Even if successful this result may still have a high value in which case the blocking may not conform very closely to regular equivalence.  

In addition there may be a number of alternative partitions which also produce the minimum value;  the algorithm does not search for additional solutions.  Finally it is possible that the routine terminates at a local minima and does not locate the desired global minima.

To test the robustness of the solution the algorithm should be run a number of times from different starting configurations.  If there is good agreement between these results then this is a sign that there is a clear split of the data into the reported blocks.

REFERENCES Glover F (1989).  Tabu Search - Part I.  ORSA Journal on Computing 1, 190-206.

Glover F (1990).  Tabu Search - Part II.  ORSA Journal on Computing 2, 4-32.

Batagelj V, Doreian P and Ferligoj A (1992).  An optimization approach to regular equivalence.  Social Networks 14, 121-135.