This paper studies the directed graph clustering problem through the lens of statistics, where we formulate clustering as estimating underlying communities in the directed stochastic block model (DSBM). We conduct the maximum likelihood estimation (MLE) on the DSBM and thereby ascertain the most probable community assignment given the observed graph structure. In addition to the statistical point of view, we further establish the equivalence between this MLE formulation and a novel flow optimization heuristic, which jointly considers two important directed graph statistics: edge density and edge orientation. Building on this new formulation of directed clustering, we introduce two efficient and interpretable directed clustering algorithms, a spectral clustering algorithm and a semidefinite programming based clustering algorithm. We provide a theoretical upper bound on the number of misclustered vertices of the spectral clustering algorithm using tools from matrix perturbation theory. We compare, both quantitatively and qualitatively, our proposed algorithms with existing directed clustering methods on both synthetic and real-world data, thus providing further ground to our theoretical contributions.

通过统计学的角度研究了有向图聚类问题，将聚类问题建模为有向随机块模型（DSBM）中估计底层社区的过程，并通过最大似然估计（MLE）推断出给定观察到的图结构的最可能的社区分配。此外，还建立了该MLE公式与新型流优化启发式算法之间的等价关系，该算法同时考虑了两个重要的有向图统计量：边密度和边方向。在此基础上，提出了两种高效且可解释的有向聚类算法，即谱聚类算法和基于半定规划的聚类算法。我们利用矩阵扰动理论中的工具给出了谱聚类算法中被错误聚类的顶点数量的理论上限。通过在合成数据和真实世界数据上定量和定性地比较我们提出的算法与现有的有向聚类方法，从而进一步验证了我们的理论贡献。

基于最大似然估计的有向图聚类中的随机块模型