Ordinal network representation: Representing proximities by graphs

Ordinal network representations are graph-theoretic representations of proximity data. They seek to provide parsimonious representations of the ordinal (nonmetric) information in observed proximity data by means of the minimum-path-length distance of a connected and weighted graph. In contrast to traditional tree-based graph-theoretic approaches, ordinal network representation is not limited to but includes the representation by trees. Asymmetry in the proximity data and violations of zero-minimality are allowed for. The paper explores fundamental representation and uniqueness results and discusses a method of constructing ordinal network representations. A simple strategy for handling the problem of errors in the data is described and illustrated.This work was supported by grant Fe 75/20-2 of the Deutsche Forschungsgemeinschaft. The author is indebted to Hubert Feger for many inspiring discussions.