Vertex Nomination via Seeded Graph Matching

• Activity Number: 609
• Type: Contributed
• Date/Time: Wednesday, August 3, 2016 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Heather Patsolic* and Vince Lyzinski and Carey Priebe
• Companies: The Johns Hopkins University and The Johns Hopkins University and The Johns Hopkins University
• Keywords: graph matching ; vertex nomination ; social networks ; stochastic blockmodel ; seeded graph matching

Abstract

Given a vertex of interest in a network, we seek the corresponding vertices in a second network. We present an algorithm appropriate for situations in which the networks are too large for brute-force graph matching. Our algorithm identifies vertices in the neighborhood of the vertex of interest in the first network that have verifiable corresponding vertices in the second network. Leveraging these known correspondences, we match the induced subgraphs in each network generated by the neighborhoods of these verified seeds. We then rank the vertices of the second network in terms of the most likely matches to the original vertex of interest. We demonstrate the applicability of our algorithm through simulations and real data examples, including a pair of high school friendship networks.