Social networks are online applications that allow their users to connect by means of various link types. As part of their offerings, these networks allow people to list details about themselves that are relevant to the nature of the network. For instance, Facebook is a general-use social network, so individual users list their favorite activities, books, and movies. Conversely, LinkedIn is a professional network; because of this, users specify details are related to their professional life reference letters, previous employment. This personal information allows social network application providers a unique opportunity; direct use of this information could be useful to advertisers for direct marketing. Privacy concerns can prevent these efforts. This conflict between desired use of data and individual privacy presents an opportunity for social network data mining that is, the discovery of information and relationships from social network data. The privacy concerns of individuals in a social network can be classified into one of two categories: privacy after data release, and private information leakage. Privacy after data release has to do with the identification of specific individuals in a data set subsequent to its release to the general public or to paying customers for specific usage. Perhaps the most illustrative example of this type of privacy breach (and the repercussions thereof) is the AOL search data scandal. AOL released the search results from 650,000 users for research purposes. However, these results had a significant number of “vanity” searches searches on an individual’s name, social security number, or address that could then be tied back to a specific individual.