Computing core/periphery structures and permutation tests for social relations data

The core/periphery structure is ubiquitous in network studies. The discrete version of the concept is that individuals in a group belong to either the core, which has a high density of ties, or to the periphery, which has a low density of ties. The density of ties between the core and the periphery may be either high or low. If the core/periphery structure is given a priori, then there is no problem in finding a suitable statistical test. Often, however, the structure is not given, which presents us with two problems, searching for the optimal core/periphery structure, and devising a valid statistical test to replace the one invalidated by the search. UCINET [Borgatti, S.P., Everett, M.G., Freeman, L.C., 2002. UCINET for Windows, Version 6.59: Software for Social Network Analysis. Analytic Technologies, Harvard], the oldest and most trusted network program, gives incorrect answers in some simple cases for the first problem and does not address the second. This paper solves both problems with an adaptation of the Kernighan-Lin search algorithm, and with a permutation test incorporating this algorithm. (c) 2005 Elsevier B.V. All rights reserved.