Relaxations in Practical Clustering and Blockmodeling
groups. These groups are either required to be dense (clustering) or to contain vertices of equivalent
positions (blockmodeling). However, there is a variety of definitions and quality measures to achieve the
groupings. In surveys, only few mathematical connections between the various definitions are mentioned.
In this paper, we show that most of the definitions used in practice can be seen as certain relaxations of
four basic graph theoretical definitions. The theory holds for both clustering and blockmodeling. It can be
used as the basis of a methodological analysis of different practical approaches.
This work is licensed under a Creative Commons Attribution 3.0 License.