Vertex nomination schemes for membership prediction
From MaRDI portal
Publication:902928
DOI10.1214/15-AOAS834zbMATH Open1454.62180arXiv1312.2638MaRDI QIDQ902928FDOQ902928
Authors: Li Chen, Donniell E. Fishkind, Vince Lyzinski, Henry Pao, Carey E. Priebe 
Publication date: 4 January 2016
Published in: The Annals of Applied Statistics (Search for Journal in Brave)
Abstract: Suppose that a graph is realized from a stochastic block model where one of the blocks is of interest, but many or all of the vertices' block labels are unobserved. The task is to order the vertices with unobserved block labels into a ``nomination list such that, with high probability, vertices from the interesting block are concentrated near the list's beginning. We propose several vertex nomination schemes. Our basic - but principled - setting and development yields a best nomination scheme (which is a Bayes-Optimal analogue), and also a likelihood maximization nomination scheme that is practical to implement when there are a thousand vertices, and which is empirically near-optimal when the number of vertices is small enough to allow comparison to the best nomination scheme. We then illustrate the robustness of the likelihood maximization nomination scheme to the modeling challenges inherent in real data, using examples which include a social network involving human trafficking, the Enron Graph, a worm brain connectome and a political blog network.
Full work available at URL: https://arxiv.org/abs/1312.2638
Recommendations
- Vertex nomination: the canonical sampling and the extended spectral nomination schemes
- On the consistency of the likelihood maximization vertex nomination scheme: bridging the gap between maximum likelihood estimation and graph matching
- On consistent vertex nomination schemes
- Vertex nomination, consistent estimation, and adversarial modification
- Estimation and prediction for stochastic blockmodels for graphs with latent block structure
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Probabilistic graphical models (62H22) Social networks; opinion dynamics (91D30)
Cites Work
- MCLUST: Software for model-based cluster analysis
- A nonparametric view of network models and Newman–Girvan and other modularities
- Estimation and Prediction for Stochastic Blockstructures
- Title not available (Why is that?)
- Mixed membership stochastic blockmodels
- Community structure in social and biological networks
- Enhanced model-based clustering, density estimation, and discriminant analysis software:\newline MCLUST
- 10.1162/jmlr.2003.3.4-5.993
- Title not available (Why is that?)
- Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
- A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
- Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
- Asymmetric graphs
- Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
- Scan statistics on Enron graphs
- Castelnuovo-Mumford Regularity and Analytic Deviation of Ideals
Cited In (10)
- Vertex Nomination Between Graphs via Spectral Embedding and Quadratic Programming
- Subgraph nomination: query by example subgraph retrieval in networks
- Statistical inference on random dot product graphs: a survey
- On estimation and inference in latent structure random graphs
- Hypothesis testing for equality of latent positions in random graphs
- Locating names on vertices of a transaction network
- Vertex nomination via seeded graph matching
- On consistent vertex nomination schemes
- Vertex nomination, consistent estimation, and adversarial modification
- Vertex nomination: the canonical sampling and the extended spectral nomination schemes
Uses Software
This page was built for publication: Vertex nomination schemes for membership prediction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q902928)
