  A crucial privacy-driven issue nowadays is re-identifying anonymized social
networks by mapping them to correlated cross-domain auxiliary networks. Prior
works are typically based on modeling social networks as random graphs
representing users and their relations, and subsequently quantify the quality
of mappings through cost functions that are proposed without sufficient
rationale. Also, it remains unknown how to algorithmically meet the demand of
such quantifications, i.e., to find the minimizer of the cost functions. We
address those concerns in a more realistic social network modeling
parameterized by community structures that can be leveraged as side information
for de-anonymization. By Maximum A Posteriori (MAP) estimation, our first
contribution is new and well justified cost functions, which, when minimized,
enjoy superiority to previous ones in finding the correct mapping with the
highest probability. The feasibility of the cost functions is then for the
first time algorithmically characterized. While proving the general
multiplicative inapproximability, we are able to propose two algorithms, which,
respectively, enjoy an \epsilon-additive approximation and a conditional
optimality in carrying out successful user re-identification. Our theoretical
findings are empirically validated, with a notable dataset extracted from rare
true cross-domain networks that reproduce genuine social network
de-anonymization. Both theoretical and empirical observations also manifest the
importance of community information in enhancing privacy inferencing.
