Exploratory blockmodeling for one-mode, unsigned, deterministic networks using integer programming and structural equivalence

Although there are well-known heuristics for the blockmodeling of one-mode, unsigned, deterministic networks using structural equivalence, the potential benefits of exact algorithms that generate globally optimal solutions are many. In this paper we extend the applicability of one such method - integer programming - to exploratory blockmodeling. Specifically, leveraging the work of Brusco and Steinley (2009), we use the isomorphic properties of the image matrix to develop a minimal, representative set of image matrices with P positions. Not only does this drastically reduce the total number of image matrices the researcher must fit, but it also simultaneously solves all blockmodels with less than P positions. We demonstrate and prove the latter using the structural equivalence of positions, and we subsequently develop a minimal set of image matrices for four or fewer positions. These developments are illustrated using Fine's well-known Sharpstone Auto Little League Team network (1987), and we use the results to discover new structural features. In our account, competing, globally optimal alternatives are embraced as equally compelling, coexisting representations of a complex culture.