Role extraction for digraphs via neighborhood pattern similarity

Funding Information: The authors thank the anonymous reviewers for useful comments. G.B. and V.N. are supported by an Academy of Finland grant (Suomen Akatemian päätös 331240). G.B. thanks the Alfred Kordelinin säätiö for the financial support under Grant No. 210122. P.V.D. is supported by an Aalto Science Institute Visitor Programme. Publisher Copyright: © 2022 American Physical Society.We analyze the recovery of different roles in a network modeled by a directed graph, based on the so-called Neighborhood Pattern Similarity approach. Our analysis uses results from random matrix theory to show that, when assuming that 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.Peer reviewe