EURO Journal on Computational Optimization (May 2015)
Evaluating the quality of image matrices in blockmodeling
Abstract
One approach for analyzing large networks is to partition its nodes into classes where the nodes in a class have similar characteristics with respect to their connections in the network. A class is represented as a blockmodel (or image matrix). In this context, a specific question is to test whether a presumed blockmodel is well reflected in the network or to select from a choice of possible blockmodels the one fitting best. In this paper, we formulate these problems as combinatorial optimization problems. We show that the evaluation of a blockmodel’s quality is a generalization of well-known optimization problems such as quadratic assignment, minimum k-cut, traveling salesman, and minimum edge cover. A quadratic integer programming formulation is derived and linearized by making use of properties of these special cases. With a branch-and-cut approach, the resulting formulation is solved up to 10,000 times faster than a comparable formulation from the literature.
