Clustering in block Markov chains (Q1996780)

It is important to recognize the hidden links between items to approve their similarity. The solution to such a task is pivotal for many applications. The main theoretical contribution of this paper is the fundamental information-theoretical lower bound on the detection error rate which is valid for the arbitrary clustering algorithm. Two optimal (in sense of ability to reach the fundamental detectability limit) algorithms are proposed to recover the cluster structure from the shortest possible trajectories.