Understanding the importance of side information in graph matching problem

Singhal, Kushagra

Permalink

https://hdl.handle.net/2142/95467 Copy

Description

Title

Understanding the importance of side information in graph matching problem

Author(s)

Singhal, Kushagra

Issue Date

2016-11-22

Director of Research (if dissertation) or Advisor (if thesis)

Kiyavash, Negar

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• graph matching
• privacy
• deanonymization
• side information

Abstract

Graph matching algorithms rely on the availability of seed vertex pairs as side information to deanonymize users across networks. Although such algorithms work well in practice, there are other types of side information available which are potentially useful to an attacker. In this thesis, we consider the problem of matching two correlated graphs when an attacker has access to side information either in the form of community labels or an imperfect initial matching. First, we propose a naive graph matching algorithm by introducing the community degree vectors which harness the information from community labels in an e cient manner. Next, we analyze the basic percolation algorithm for graphs with community structure. Finally, we propose a novel percolation algorithm with two thresholds which uses an imperfect matching as input to match correlated graphs. We also analyze these algorithms and provide theoretical guarantees for matching graphs generated using the Stochastic Block Model. We evaluate the proposed algorithms on synthetic as well as real world datasets using various experiments. The experimental results demonstrate the importance of communities as side information especially when the number of seeds is small and the networks are weakly correlated. These results motivate the study of other types of potential side information available to the attacker. Such studies could assist in devising mechanisms to counter the effects of side information in network deanonymization.

Graduation Semester

2016-12

Type of Resource

text

Permalink

http://hdl.handle.net/2142/95467

Copyright and License Information

Copyright 2016 Kushagra Singhal

Owning Collections