Maximum Likelihood Estimation on Stochastic Blockmodels for Directed
  Graph Clustering
Mihai Cucuringu Xiaowen Dong Ning Zhang
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.