On role extraction for digraphs via neighbourhood pattern similarity
arXiv:2111.02208 · doi:10.1103/PhysRevE.106.054301
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 (26)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- 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
- Community detection in complex networks using Extremal Optimization
- 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
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Mixture models and exploratory analysis in networks
- Spectral clustering and the high-dimensional stochastic blockmodel
- Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
- Consistency of spectral clustering in stochastic block models
- Fast community detection by SCORE
- Pseudo-likelihood methods for community detection in large sparse networks
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Parsimonious module inference in large networks
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Stochastic blockmodels with growing number of classes
- Uncovering latent structure in valued graphs: A variational approach
- Infinite-Order Percolation and Giant Fluctuations in a Protein Interaction Network
- Role models for complex networks
- Protein-Interaction-Networks: More than mere modules
- Inversion method for content-based networks