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 varied cost functions. However, many cost functions are empirically proposed without sufficient theoretical support. For some other works probing the theoretical bound, it remains unknown how to algorithmically meet the demand of such quantifications, i.e., to minimize the cost functions. Besides, only few prior works have discussed the de-anonymization of social networks with communities. We address those concerns in a social network modeling parameterized by community structures that can be leveraged as side information for de-anonymization. Based on the Maximum A Posteriori (MAP) estimation, our first contribution is a series of MAP-based 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. We prove the general multiplicative inapproximability and thus propose two heuristics, which, respectively, enjoy an$\epsilon$-additive approximation and a conditional optimality in carrying out successful user re-identification. Our theoretical findings are also empirically validated under classical synthetic and real-wrold social networks. Both theoretical and empirical observations manifest the importance of community in enhancing privacy inferencing.

Anonymization techniques have tranquilized current social network users in terms of privacy leakage, however, it does not radically prevent adversaries from de-anonymizing users, as they may map the users to an un-anonymized network. Till now, researchers share a common thread in such de-anonymization attack: unveiling conditions leading to successful de-anonymization under the chosen network model. However, it has not yet been well understand how the structural property in different network models intrinsically determines de-anonymizability. We address the above issue in this paper by making the two contributions: (i) We discover that the automorphic degree and homomorphic degree of social networks determine their de-anonymizability universally. The automorphic degree characterizes the distinguishability of the users in a network, while the homomorphic degree models the similarities of users between two networks. We conclude that a smaller automorphic degree and a larger homomorphic degree conduce to a higher de-anonymizability. Such model-independent phenomenon refreshes us with a latitudinal study as it generalizes the essential commonness of de-anonymization in different network models. (ii) We derive explicit parametric bounds of the de-anonymizability for three classic network models, showing that such bounds correspond well to our conclusion about morphism property. We then algorithmically and experimentally show that such theoretical results literally make sense to adversaries. Such longitudinal study, including welding theory, algorithm and validation, promises applicability of our results on morphism property in real cases.