Contents - Index

NETWORK >SUBGROUPS >FACTIONS

PURPOSE Optimizes a cost function which measures the degree to which a partition consists of clique like structures using a tabu search method.

DESCRIPTION Given a partition of a binary network of adjacencies into n groups, then a count of the number of missing ties within each group summed with the ties between the groups gives  a measure of the extent to which the groups form separate clique like structures. The routine uses a tabu search minimization procedure to optimize this measure to find the best fit.

PARAMETERS
Input dataset:
Name of file containing network to be analyzed. Data type: Digraph.
 
Number of blocks: (Default = 2)
Number of partitions into which the data needs to be split.

Output sets dataset: (Default ='FactionsSets')
Name of dataset which contains the factions by actor indicator matrix. Each row is a different faction and the columns are the vertices. A 1 in row i column j indicates that vertex j is in faction i. 

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

The following options are accessed by clicking on the 'additional' tab in the dialogue box

Measure of fit:
Choices are
 
Hamming. Counts the total number of errors, that is the number of zeros in a diagonal block and the number of ones in an off diagonal block.
Phi. Uses correlation between the data matrix and a structure matrix with diagonal one blocks and off diagonal zero blocks.
Q Modularity measure that is the fraction of internal edges in each group minus the expected fraction if they were distributed at random but with the same degree sequence. Note this can be negative.
 
Are diagonal values valid: 
Yes to include diagonals No to ignore them

Maximum # of iterations in a series: (Default = 20)
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 neighbourhood 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.

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 c

Length of time in penalty box: (Default = 15)
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 has been shown experimentally to be the most useful.

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

LOG FILE The initial and final value of the cost function.  
The group assignments. A list of the factions labelled, each faction is specified by the vertices it contains.
A grouped adjacency matrix that is a blocked permuted adjacency matrix where the diagonal blocks correspond to the factions.
A table of densities between and within blocks.

TIMING Each iteration of the tabu search algorithm is O(N^2).  Random tests with default parameters as specified indicate O(N^2.5).  

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 be a high value in which case the factions may not represent cohesive subgroups.  

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 factions.

REFERENCES de Amorim S G, Barthélemy J P and Ribeiro (1990).  Clustering and Clique Partitioning:  Simulated Annealing and Tabu Search Approaches.  Research report from Groupe d'études et de recherche en analyse des décisions.  Ecole des Hautes Etudes Commerciales, Ecole Polytechnique, Université McGill.

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

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