Vertex nomination: The canonical sampling and the extended spectral\n nomination schemes Article Swipe
YOU?
·
· 2018
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.1802.04960
· OA: W4302846816
Suppose that one particular block in a stochastic block model is of interest,\nbut block labels are only observed for a few of the vertices in the network.\nUtilizing a graph realized from the model and the observed block labels, the\nvertex nomination task is to order the vertices with unobserved block labels\ninto a ranked nomination list with the goal of having an abundance of\ninteresting vertices near the top of the list. There are vertex nomination\nschemes in the literature, including the optimally precise canonical nomination\nscheme~$\\mathcal{L}^C$ and the consistent spectral partitioning nomination\nscheme~$\\mathcal{L}^P$. While the canonical nomination scheme $\\mathcal{L}^C$\nis provably optimally precise, it is computationally intractable, being\nimpractical to implement even on modestly sized graphs. With this in mind, an\napproximation of the canonical scheme---denoted the {\\it canonical sampling\nnomination scheme} $\\mathcal{L}^{CS}$---is introduced; $\\mathcal{L}^{CS}$\nrelies on a scalable, Markov chain Monte Carlo-based approximation of\n$\\mathcal{L}^{C}$, and converges to $\\mathcal{L}^{C}$ as the amount of sampling\ngoes to infinity. The spectral partitioning nomination scheme is also extended\nto the {\\it extended spectral partitioning nomination scheme},\n$\\mathcal{L}^{EP}$, which introduces a novel semisupervised clustering\nframework to improve upon the precision of $\\mathcal{L}^P$. Real-data and\nsimulation experiments are employed to illustrate the precision of these vertex\nnomination schemes, as well as their empirical computational complexity.\nKeywords: vertex nomination, Markov chain Monte Carlo, spectral partitioning,\nMclust MSC[2010]: 60J22, 65C40, 62H30, 62H25\n
