On consistent vertex nomination schemes
arXiv:1711.05610
Abstract
Given a vertex of interest in a network , the vertex nomination problem seeks to find the corresponding vertex of interest (if it exists) in a second network . A vertex nomination scheme produces a list of the vertices in , ranked according to how likely they are judged to be the corresponding vertex of interest in . The vertex nomination problem and related information retrieval tasks have attracted much attention in the machine learning literature, with numerous applications to social and biological networks. However, the current framework has often been confined to a comparatively small class of network models, and the concept of statistically consistent vertex nomination schemes has been only shallowly explored. In this paper, we extend the vertex nomination problem to a very general statistical model of graphs. Further, drawing inspiration from the long-established classification framework in the pattern recognition literature, we provide definitions for the key notions of Bayes optimality and consistency in our extended vertex nomination framework, including a derivation of the Bayes optimal vertex nomination scheme. In addition, we prove that no universally consistent vertex nomination schemes exist. Illustrative examples are provided throughout.
arXiv comment32 pages, 4 figures
References in corpus (13)
- Statistical mechanics of complex networks
- Lethality and centrality in protein networks
- Finding community structure in networks using the eigenvectors of matrices
- Link Prediction in Complex Networks: A Survey
- Stochastic blockmodels and community structure in networks
- Structure and inference in annotated networks
- Vertex nomination schemes for membership prediction
- A nonparametric two-sample hypothesis testing problem for random dot product graphs
- Vertex Nomination via Content and Context
- Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurability
- Geometric Network Comparison
- Graph Matching: Relax at Your Own Risk
- On the Incommensurability Phenomenon