2026-09-19T22:51:50Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/102401 2023-07-11 col_2142_5131 col_2142_8888 com_2142_5130 com_2142_8887 com_2142_234

Srikant, R. Lubars, Joseph 2019-02-06T19:32:41Z 2019-02-06T19:32:41Z 2018-09-13 2018-12 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. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-02-05 without embargo terms The student, Joseph Lubars, accepted the attached license on 2018-09-12 at 12:23. The student, Joseph Lubars, submitted this Thesis for approval on 2018-09-12 at 12:34. This Thesis was approved for publication on 2018-09-13 at 10:04. DSpace SAF Submission Ingestion Package generated from Vireo submission #13010 on 2019-02-05 at 11:08:00 Made available in DSpace on 2019-02-06T19:32:41Z (GMT). No. of bitstreams: 2 LUBARS-THESIS-2018.pdf: 639030 bytes, checksum: ec4035dd7c1b2e3ab5efbd58f101f636 (MD5) LICENSE.txt: 4210 bytes, checksum: 777780c8ca3db32c778383db37c5b65c (MD5) Previous issue date: 2018-09-13 application/pdf http://hdl.handle.net/2142/102401 en Copyright 2018 Joseph Lubars Privacy Social Networks De-anonymization Approximate Graph Matching Stochastic Block Model Improving the output of algorithms for large-scale approximate graph matching text text Electrical & Computer Eng Electrical & Computer Engr University of Illinois at Urbana-Champaign Thesis M.S.