On Spectral Algorithms for Community Detection in Stochastic Blockmodel Graphs With Vertex Covariates
- 26 May 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 9 (5) , 3373-3384
Abstract
In network inference applications, it is often desirable to detect community structure. Beyond mere adjacency matrices, many real-world networks also involve vertex covariates that carry key information about underlying block structure in graphs. To assess the effects of such covariates on block recovery, we present a comparative analysis of two model-based spectral algorithms for clustering vertices in stochastic blockmodel graphs with vertex covariates. The first algorithm uses only the adjacency matrix, and directly estimates the block assignments. The second algorithm incorporates both the adjacency matrix and the vertex covariates into the estimation of block assignments, and moreover quantifies the explicit impact of the vertex covariates on the resulting estimate of the block assignments. We employ Chernoff information to analytically compare the algorithms’ performance and derive the information-theoretic Chernoff ratio for certain models of interest. Analytic results and simulations suggest that the second algorithm is often preferred: one can better estimate the induced block assignments by first estimating the effect of vertex covariates. In addition, real data examples also indicate that the second algorithm has the advantage of revealing underlying block structure while considering observed vertex heterogeneity in real applications.Keywords
All Related Versions
Funding Information
- Defense Advanced Research Projects Agency (FA8750-17-2-0112)
- National Science Foundation (SES-1951005)
This publication has 33 references indexed in Scilit:
- A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel GraphsJournal of the American Statistical Association, 2012
- Stochastic blockmodels with a growing number of classesBiometrika, 2012
- Spectral clustering and the high-dimensional stochastic blockmodelThe Annals of Statistics, 2011
- Model-Based Clustering for Social NetworksJournal of the Royal Statistical Society Series A: Statistics in Society, 2007
- Automatic dimensionality selection from the scree plot via the use of profile likelihoodComputational Statistics & Data Analysis, 2006
- Latent Space Approaches to Social Network AnalysisJournal of the American Statistical Association, 2002
- Comparing partitionsJournal of Classification, 1985
- Stochastic blockmodels: First stepsSocial Networks, 1983
- Large-Sample Theory: Parametric CaseThe Annals of Mathematical Statistics, 1956
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952