Files in this item
Files | Description | Format |
---|---|---|
application/pdf ![]() | (no description provided) |
Description
Title: | Improving the output of algorithms for large-scale approximate graph matching |
Author(s): | Lubars, Joseph |
Advisor(s): | Srikant, R. |
Department / Program: | Electrical & Computer Eng |
Discipline: | Electrical & Computer Engr |
Degree Granting Institution: | University of Illinois at Urbana-Champaign |
Degree: | M.S. |
Genre: | Thesis |
Subject(s): | Privacy
Social Networks De-anonymization Approximate Graph Matching Stochastic Block Model |
Abstract: | 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. |
Issue Date: | 2018-09-13 |
Type: | Text |
URI: | http://hdl.handle.net/2142/102401 |
Rights Information: | Copyright 2018 Joseph Lubars |
Date Available in IDEALS: | 2019-02-06 |
Date Deposited: | 2018-12 |
This item appears in the following Collection(s)
-
Dissertations and Theses - Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering -
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois