Graph matching with applications to network analysis
OA Version
Citation
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.