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

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

Lubars, Joseph ; Srikant ; R.

关键词: Privacy;    Social Networks;    De-anonymization;    Approximate Graph Matching;    Stochastic Block Model;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/102401/LUBARS-THESIS-2018.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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.