Relaxations in Practical Clustering and Blockmodeling (Informatica, 2015)
Network analysts try to explain the structure of complex networks by the partitioning of their nodes intogroups. These groups are either required to be dense (clustering) or to contain vertices of equivalentpositions (blockmodeling). However, there is a variety of definitions and quality measures to achieve thegroupings. 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 offour basic graph theoretical definitions. The theory holds for both clustering and blockmodeling. It can beused as the basis of a methodological analysis of different practical approaches.