  The advent of social networks poses severe threats on user privacy as
adversaries can de-anonymize users' identities by mapping them to correlated
cross-domain networks. Without ground-truth mapping, prior literature proposes
various cost functions in hope of measuring the quality of mappings. However,
there is generally a lacking of rationale behind the cost functions, whose
minimizer also remains algorithmically unknown. We jointly tackle above
concerns under a more practical social network model parameterized by
overlapping communities, which, neglected by prior art, can serve as side
information for de-anonymization. Regarding the unavailability of ground-truth
mapping to adversaries, by virtue of the Minimum Mean Square Error (MMSE), our
first contribution is a well-justified cost function minimizing the expected
number of mismatched users over all possible true mappings. While proving the
NP-hardness of minimizing MMSE, we validly transform it into the weighted-edge
matching problem (WEMP), which, as disclosed theoretically, resolves the
tension between optimality and complexity: (i) WEMP asymptotically returns a
negligible mapping error in large network size under mild conditions
facilitated by higher overlapping strength; (ii) WEMP can be algorithmically
characterized via the convex-concave based de-anonymization algorithm (CBDA),
perfectly finding the optimum of WEMP. Extensive experiments further confirm
the effectiveness of CBDA under overlapping communities, in terms of averagely
90% re-identified users in the rare true cross-domain co-author networks when
communities overlap densely, and roughly 70% enhanced re-identification ratio
compared to non-overlapping cases.
