Popularity Adjusted Block Models are Generalized Random Dot Product Graphs
We connect two random graph models, the Popularity Adjusted Block Model (PABM) and the Generalized Random Dot Product Graph (GRDPG), by demonstrating that the PABM is a special case of the GRDPG in which communities correspond to mutually orthogonal subspaces of latent vectors. This insight allows us to construct new algorithms for community detection and parameter estimation for the PABM, as well as improve an existing algorithm that relies on Sparse Subspace Clustering. Using established asymptotic properties of Adjacency Spectral Embedding for the GRDPG, we derive asymptotic properties of these algorithms. In particular, we demonstrate that the absolute number of community detection errors tends to zero as the number of graph vertices tends to infinity. Simulation experiments illustrate these properties.
Code (1)
Tasks
ClusteringCommunity Detectionparameter estimationSimilar Papers 제목 키워드 기반
Hypothesis Testing for Equality of Latent Positions in Random Graphs
We consider the hypothesis testing problem that two vertices $i$ and $j$ of a generalized random dot product graph have the same latent positions, possibly up to scaling. Special cases of this hypothesis test include tes…
Model SelectionStochastic Block ModelSparse Popularity Adjusted Stochastic Block Model
In the present paper we study a sparse stochastic network enabled with a block structure. The popular Stochastic Block Model (SBM) and the Degree Corrected Block Model (DCBM) address sparsity by placing an upper bound on…
modelStochastic Block ModelStrongly Consistent Community Detection in Popularity Adjusted Block Models
The Popularity Adjusted Block Model (PABM) provides a flexible framework for community detection in network data by allowing heterogeneous node popularity across communities. However, this flexibility increases model com…
ClusteringCommunity DetectionThe Hierarchy of Block Models
There exist various types of network block models such as the Stochastic Block Model (SBM), the Degree Corrected Block Model (DCBM), and the Popularity Adjusted Block Model (PABM). While this leads to a variety of choice…
ClusteringStochastic Block ModelOptimal Graph Clustering without Edge Density Signals
This paper establishes the theoretical limits of graph clustering under the Popularity-Adjusted Block Model (PABM), addressing limitations of existing models. In contrast to the Stochastic Block Model (SBM), which assume…
Graph Clustering