Finding and testing regular equivalence

被引:9
作者
Boyd, JP [1 ]
机构
[1] Univ Calif Irvine, Dept Anthropol, Irvine, CA 92697 USA
关键词
regular; clustering; significance;
D O I
10.1016/S0378-8733(02)00011-4
中图分类号
Q98 [人类学];
学科分类号
030303 [人类学];
摘要
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.
引用
收藏
页码:315 / 331
页数:17
相关论文
共 22 条
[1]
Aarts E., 1997, LOCAL SEARCH COMBINA, P1
[2]
AN OPTIMIZATIONAL APPROACH TO REGULAR EQUIVALENCE [J].
BATAGELJ, V ;
DOREIAN, P ;
FERLIGOJ, A .
SOCIAL NETWORKS, 1992, 14 (1-2) :121-135
[3]
BOCH HH, 1996, CLUSTERING CLASSIFIC, P377
[4]
BOYD J, 1991, SOCIAL SEMIGROUPS
[5]
Relations, residuals, regular interiors, and relative regular equivalence [J].
Boyd, JP ;
Everett, MG .
SOCIAL NETWORKS, 1999, 21 (02) :147-165
[6]
Are social equivalences ever regular? Permutation and exact tests [J].
Boyd, JP ;
Jonas, KJ .
SOCIAL NETWORKS, 2001, 23 (02) :87-123
[7]
BOYD JP, 2002, UNPUB SOCIAL NETWORK
[8]
DOMINANCE HIERARCHIES IN LEPTOTHORAX ANTS [J].
COLE, BJ .
SCIENCE, 1981, 212 (4490) :83-84
[9]
Feller W., 1957, INTRO PROBABILITY TH, VI
[10]
Fiduccia C., 1982, P 19 IEEE DES AUT C, P175, DOI [DOI 10.1109/DAC.1982.1585498, 10.1109/DAC.1982.1585498]