Back to search

Boston University

Graph matching with applications to network analysis

Abstract

dc:description.abstract

The graph matching (GM) problem seeks to find an alignment between the vertex sets of two graphs and has applications in social network analysis, bioinformatics, and pattern recognition. In this dissertation, we propose to (a) develop the iGraphMatch R package for common GM algorithms and steps for analysis of GM, (b) develop the mutual nearest neighbor algorithm for matching node pairs with high precision in polynomial time, and (c) analyze a user de-anonymization problem based on their Venmo transaction networks along with various information associated with users and their transactions. The iGraphMatch package enables seamless matching of generalized graphs with versatile options for the form of input graphs and the specification of available prior information, as well as evaluation of matching performance, and visualization. For the methodology component, we empirically demonstrate the effectiveness of the mutual nearest neighbor algorithm for finding a high precision sub-match. In addition, we develop a mathematical framework for the analysis of the proposed method and provide conditions for achieving high matching precision under a correlated random graph model. Lastly, for the challenging GM problem on Venmo transaction networks, we introduce a similarity-based learning method for integrating multiple features into a single similarity score that optimizes the expected number of correctly matched nodes.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Mathematics & Statistics
Grantor
Boston University
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Qiao, Zihuan
Advisor dc:contributor.advisor
  • Sussman, Daniel

Subjects

dc:subject × 1

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/46986

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Qiao, Zihuan. Graph matching with applications to network analysis. doctoral thesis, Boston University, 2022. https://hdl.handle.net/2144/46986