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.