Files in this item

FilesDescriptionFormat

application/pdf

application/pdfLUBARS-THESIS-2018.pdf (639kB)
(no description provided)PDF

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:Thesis
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)

Item Statistics