|
Abstract:
|
Given a vertex of interest in a network G, vertex nomination seeks to find the corresponding vertex of interest (if it exists) in a second network G', thereby ranking the vertices in G' according to their likelihood of correspondence. The vertex nomination problem and related information retrieval tasks have attracted much attention in the machine learning literature, with numerous applications in 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 vertexnomination schemes has barely been explored. In this talk, we extend the vertex nomination problem to a very general random graph model; drawing inspiration from the essentials of pattern recognition, we provide key definitions 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, and we explore practical ramifications of the lack of universal consistency in the context of robust vertex nomination in the presence of adversarial node behavior.
|
