| Hundreds of millions of people use social network sites daily for entertainment, socialization, and business purposes. Social network sites have accumulated huge amount of personal information, which can be modeled by social graphs, where vertices represent persons, and edges represent relationships. Social graphs have attracted tremendous interest of scholars and application developers in many areas. However, varieties of sensitive personal information become a privacy concern for social network users and owners, and prohibit publishing the graphs for massive usage. Diverse privacy attacks cause privacy disclosure in social graphs. We categorize the privacy attacks into two categories --- vertex re-identification attacks and information re-association attacks.;For vertex re-identification attacks, many early researches propose anonymization methods to protect the identity of vertices so that private information on vertices is preserved. Nevertheless, sensitive relationships represented by edges may still disclose. Our work focuses on design anonymization methods to protect the sensitive edges. We deal with three issues in the method design: privacy measure, utility loss measure and performance. Our contribution includes using a strong equivalence relation to define the privacy measure, choosing the number of edges changed as utility loss measure in a theoretic manner, and developing efficient methods based on a condensed graph for the large scale graph.;For information re-association attacks, recent researches have designed attack models based on various techniques, such as statistics models, data mining techniques, or security attacks. We design a new information re-association attack that combines web search and information extraction techniques. Our contribution includes proposing a measurement to evaluate the effectiveness of the attack, and empirically analyzing the privacy disclosure under this attack. |
