Vertex nomination via seeded graph matching

Statistical Analysis and Data Mining

article

Heather G. Patsolic¹  Youngser Park²  Vince Lyzinski³  Carey E. Priebe¹ 

[1] Department of Applied Mathematics and Statistics, The Johns Hopkins University;Center for Imaging Science, The Johns Hopkins University;Department of Mathematics, University of Maryland

关键词: graph inference;    graph matching;    graph mining;    seeded graph matching;    stochastic block model;    vertex nomination;   

DOI  :  10.1002/sam.11454

学科分类：社会科学、人文和艺术（综合）

来源: John Wiley & Sons, Inc.

【 摘 要 】

Consider two networks on overlapping, nonidentical vertex sets. Given vertices of interest (VOIs) in the first network, we seek to identify the corresponding vertices, if any exist, in the second network. While in moderately sized networks graph matching methods can be applied directly to recover the missing correspondences, herein we present a principled methodology appropriate for situations in which the networks are too large/noisy for brute-force graph matching. Our methodology identifies vertices in a local neighborhood of the VOIs in the first network that have verifiable corresponding vertices in the second network. Leveraging these known correspondences, referred to as seeds, we match the induced subgraphs in each network generated by the neighborhoods of these verified seeds, and rank the vertices of the second network in terms of the most likely matches to the original VOIs. We demonstrate the applicability of our methodology through simulations and real data examples.

【 授权许可】

Unknown