{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/102401"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/102401","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Improving the output of algorithms for large-scale approximate graph matching","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Lubars, Joseph"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Srikant, R."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-02-06T19:32:41Z","date_published":"2019-02-06T19:32:41Z","updated_at":"2026-07-22T22:24:40Z","subjects":["Privacy","Social Networks","De-anonymization","Approximate Graph Matching","Stochastic Block Model"],"languages":["en"],"rights":["Copyright 2018 Joseph Lubars"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/102401","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Srikant, R."]},{"key":"dc:creator","label":"Author","values":["Lubars, Joseph"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-02-06T19:32:41Z","2018-09-13","2018-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Privacy","Social Networks","De-anonymization","Approximate Graph Matching","Stochastic Block Model"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2018 Joseph Lubars"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/102401"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Improving the output of algorithms for large-scale approximate graph matching"]}]}],"canonical_facts":{"dc:contributor":["Srikant, R."],"dc:creator":["Lubars, Joseph"],"dc:date":["2019-02-06T19:32:41Z","2018-09-13","2018-12"],"dc:description":["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"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/102401"],"dc:language":["en"],"dc:rights":["Copyright 2018 Joseph Lubars"],"dc:subject":["Privacy","Social Networks","De-anonymization","Approximate Graph Matching","Stochastic Block Model"],"dc:title":["Improving the output of algorithms for large-scale approximate graph matching"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:40Z"}