  Following the trend of data trading and data publishing, many online social
networks have enabled potentially sensitive data to be exchanged or shared on
the web. As a result, users' privacy could be exposed to malicious third
parties since they are extremely vulnerable to de-anonymization attacks, i.e.,
the attacker links the anonymous nodes in the social network to their real
identities with the help of background knowledge. Previous work in social
network de-anonymization mostly focuses on designing accurate and efficient
de-anonymization methods. We study this topic from a different perspective and
attempt to investigate the intrinsic relation between the attacker's knowledge
and the expected de-anonymization gain. One common intuition is that the more
auxiliary information the attacker has, the more accurate de-anonymization
becomes. However, their relation is much more sophisticated than that. To
simplify the problem, we attempt to quantify background knowledge and
de-anonymization gain under several assumptions. Our theoretical analysis and
simulations on synthetic and real network data show that more background
knowledge may not necessarily lead to more de-anonymization gain in certain
cases. Though our analysis is based on a few assumptions, the findings still
leave intriguing implications for the attacker to make better use of the
background knowledge when performing de-anonymization, and for the data owners
to better measure the privacy risk when releasing their data to third parties.
