Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network
This work addresses the computational challenge of jointly clustering and ordering social network accounts, though it appears incremental as it builds on existing clique partition and partial ordering problems.
The authors tackled the NP-hard maximum value preordering problem by developing a 4-approximation algorithm and local search heuristics for approximate solutions, and tightening linear program relaxations with facet-defining inequalities for upper bounds. They applied these methods to jointly cluster and partially order social network accounts, demonstrating practical utility.
The NP-hard maximum value preordering problem is both a joint relaxation and a hybrid of the clique partition problem (a clustering problem) and the partial ordering problem. Toward approximate solutions and lower bounds, we introduce a linear-time 4-approximation algorithm that constructs a maximum dicut of a subgraph and define local search heuristics. Toward upper bounds, we tighten a linear program relaxation by the class of odd closed walk inequalities that define facets, as we show, of the preorder polytope. We contribute implementations of the algorithms, apply these to the task of jointly clustering and partially ordering the accounts of published social networks, and compare the output and efficiency qualitatively and quantitatively.