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.
翻译:我们根据所谓的“邻里模式相似性”方法,分析网络中不同作用的恢复情况。我们的分析利用随机矩阵理论的结果,以显示当假设该图是作为具有Bernoulli概率分布的不同区块的特定的Stochastic块模型生成时,当该图具有足够大的维度时,则该回收就完全正确。根据这些假设,相似性矩阵的主要值和主导值之间有足够的差距,这保证了对不同作用数目的无症状的正确识别。我们还评论了与Stochastic区块模型文献的联系,包括n为图形大小的n/n顺序日志/n的概率。我们提供数字实验,以评估该方法在应用到限定大小的实用网络时的有效性。