Relaxations in Practical Clustering and Blockmodeling

Abstract

Network analysts try to explain the structure of complex networks by the partitioning of their nodes into
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.