提出高效算法联合聚类与排序社交账号，兼顾准确性与速度。
Algorithms for the preordering problem and their application to the task of jointly clustering and ordering the accounts of a social network
- 用子图最大割构造4倍近似解，线性时间完成。
- 通过奇闭行走不等式收紧线性规划松弛，提升上界精度。
- 适用于需同时聚类和排序的社交网络分析任务。
NP难的最大值预排序问题既是团划分问题（聚类）又是部分排序问题的联合松弛与混合体。为获得近似解与下界，本文提出一种线性时间4-近似算法，通过构建子图的最大割来实现；并引入局部搜索启发式方法。为获取上界，通过证明奇闭行走不等式是预排序多面体的面，从而收紧线性规划松弛。我们实现了这些算法，并将其应用于公开社交网络中账号的联合聚类与部分排序任务，从定性和定量角度对比了输出结果与计算效率。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。