On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap Between Maximum Likelihood Estimation and Graph Matching
arXiv:1607.01369
Abstract
Given a graph in which a few vertices are deemed interesting a priori, the vertex nomination task is to order the remaining vertices into a nomination list such that there is a concentration of interesting vertices at the top of the list. Previous work has yielded several approaches to this problem, with theoretical results in the setting where the graph is drawn from a stochastic block model (SBM), including a vertex nomination analogue of the Bayes optimal classifier. In this paper, we prove that maximum likelihood (ML)-based vertex nomination is consistent, in the sense that the performance of the ML-based scheme asymptotically matches that of the Bayes optimal scheme. We prove theorems of this form both when model parameters are known and unknown. Additionally, we introduce and prove consistency of a related, more scalable restricted-focus ML vertex nomination scheme. Finally, we incorporate vertex and edge features into ML-based vertex nomination and briefly explore the empirical effectiveness of this approach.
References in corpus (13)
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Lethality and centrality in protein networks
- Finding community structure in networks using the eigenvectors of matrices
- Stochastic blockmodels and community structure in networks
- Structure and inference in annotated networks
- Community detection in networks: Modularity optimization and maximum likelihood are equivalent
- Network histograms and universality of blockmodel approximation
- Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
- Vertex nomination schemes for membership prediction
- Vertex Nomination via Content and Context
- Community Detection in Networks with Node Features
- Network modularity in the presence of covariates