Preordering: A hybrid of correlation clustering and partial ordering

Motivation stems from the problem of estimating a binary relation on the accoun ts of a social network where the notions that one account follows, likes or reacts to another account need neither be symmetric nor asymmetric. In particular, i following j does not need to imply that j follows i, nor does it necessarily imply that j does not follow i . Clustering alone does not capture asymmetric subsets of the relation on the social network because the equivalence relation that characterizes the clustering is symmetric. Similarly, partial ordering alone does not capture symm etric subsets of the relation on the social network because partial orders are antisymmetric. Like in clustering and partial ordering, we work with the assumption t hat the relation on the social network is transitive, i.e., if i follows j and j follows k then i follows k . This assumption simplifies reality and we quantify the deviation empirically. Unlike in clusterin g and partial ordering, we do not assume symmetry or antisymmetry. To model our assump tion we introduce algorithms that output a preorder on a set, i.e., a binary relation on the set that is reflexive and transitiv e. More specifically, we introduce algorithms for the preordering problem: Definition 1. (Wakabayashi, 1998) Given a finite set V and a value c