Relaxations in Practical Clustering and Blockmodeling

Stefan Wiesberg, Gerhard Reinelt


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.

Full Text:


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.