Improving the output of algorithms for large-scale approximate graph matching

In approximate graph matching, the goal is to find the best correspondence between the labels of two correlated graphs. Recently, the problem has been applied to social network de-anonymization, and several efficient algorithms have been proposed for approximate graph matching in that domain. These algorithms employ seeds, or matches known before running the algorithm, as a catalyst to match the remaining nodes in the graph. We adapt the ideas from these seeded algorithms to develop a computationally efficient method for improving any given correspondence between two graphs. In our analysis of our algorithm, we show a new parallel between the seeded social network de-anonymization algorithms and existing optimization-based algorithms. When given a partially correct correspondence between two Erdos-Renyi graphs as input, we show that our algorithm can correct all errors with high probability. Furthermore, when applied to real-world social networks, we empirically demonstrate that our algorithm can perform graph matching accurately, even without using any seed matches.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2019

Author dc:creator

• Lubars, Joseph

Contributors dc:contributor

• Srikant, R.

• Privacy
• Social Networks
• De-anonymization
• Approximate Graph Matching
• Stochastic Block Model

Statement dc:rights

• Copyright 2018 Joseph Lubars

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/102401

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/102401