Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold

arXiv:2205.11677v4 Announce Type: replace-cross
Abstract: The stochastic block model is a canonical random graph model for clustering and community detection on network-structured data. Decades of extensive study on the problem have established many profound results, among which the phase transition at the Kesten-Stigum threshold is particularly interesting both from a mathematical and an applied standpoint. It states that no estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below …

abstract arxiv block canonical clustering community cs.lg data detection graph graphs information math.oc math.pr network random results semi-supervised stat.ml stochastic structured data study the information threshold transition type