  We analyse the recovery of different roles in a network modelled by a
directed graph, based on the so-called Neighbourhood Pattern Similarity
approach. Our analysis uses results from random matrix theory to show that when
assuming the graph is generated as a particular Stochastic Block Model with
Bernoulli probability distributions for the different blocks, then the recovery
is asymptotically correct when the graph has a sufficiently large dimension.
Under these assumptions there is a sufficient gap between the dominant and
dominated eigenvalues of the similarity matrix, which guarantees the asymptotic
correct identification of the number of different roles. We also comment on the
connections with the literature on Stochastic Block Models, including the case
of probabilities of order log(n)/n where n is the graph size. We provide
numerical experiments to assess the effectiveness of the method when applied to
practical networks of finite size.
