On role extraction for digraphs via neighbourhood pattern similarity

Abstract

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.

References in corpus (12)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Stochastic blockmodels and community structure in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• An information-theoretic framework for resolving community structure in complex networks
• Mixture models and exploratory analysis in networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Parsimonious module inference in large networks
• Uncovering latent structure in valued graphs: A variational approach
• Role models for complex networks
• Inversion method for content-based networks