Introduction

With the rapid growth of the social web an increasing number of people started to replicate their off-line preferences and lives in an on-line environment. Indeed, the usage of social network sites (SNS) such as Facebook, Google+, or LinkedIN the use of messaging services (e.g., Twitter), tagging systems (e.g., del.ico.us), sharing and recommendation services (e.g., Last.fm) has not only increased immensely, but the activities on these site become an integral element in the daily lives of millions of people. Hence, the social web provides an enormous source for social network data collection.

Often people take part in multiple of these SNSs. In some cases this multiparticipation arises from necessity, as some features may only be provided by some sites and not by others. However, in most cases, it is also the result of free choice. The many services allow people to "partition" their lives (e.g, they may use facebook for the private-and LinkedIN for the professional network). In fact, the construction of site-specific identities enables the possibility to gain multiple personalities as identifying features, such as the email address can be changed easily-an effect that has been called "multiplicity" by Internet researchers [21]. Hence, users will continue to maintain multiple identities even if one service will cater to all their needs. At the same time, the identification of users for interlinking data from different and distributed systems is getting increasingly important for different kind of applications. In personalization, the use of cross-site profiles is essential as the incorporation of multi-source user profile data significantly increases the quality of preference recommendations [4]; In social network analysis, the merging of multiple networks provides a more complete picture of the overall social graph and helps to minimize the data selection bias on which most single-site studies suffer [1]; and trust networks can be created by aggregating relationships among network participants [17]. Even if the semantic web were to become immensely popular the increased usage of a global identifier may not simplify universal identification of a person, as some sites may not use the same identifiers or even totally ignore the identification scheme and the users may choose-to ensure their multiplicity-to maintain multiple identifiers. In fact, Mika et al. [16] argue that the key problem in the area of extraction of social network data-the disambiguation of identities and relationships-still remains, as different social web applications refer to relationship types, attributes, or tastes in profiles in different ways and do not share any common key for the identification of users. As a consequence, both researchers and practitioners (such as marketers) are placed in front of a complicated research question: how can we combine the multitude of information available about a person in the multiple SNSs to develop a holistic, combined (and as complete as possible) user model when the identity of the user in different sites is difficult to combine?

Current proposals for interlinking social network profiles based on comparing text-based attributes of user profiles [4] or using the network structure [13] have the drawback that these methods scale poorly or they need to contain some overlap in the relationship structure and result in a large computational expenditure respectively. In this paper we propose to enhance current text-based methodsin absence of semantic metadata -by combining it with face recognition algorithms. Specifically, we propose to use face-recognition software to compare the images uploaded by users on different SNSs as an additional feature for identity merging. As we show, this statistical entity resolution procedure significantly enhances the merging precision of two SNSs. Consequently, the contribution of this paper are: (1)The presentation of an enhanced identity merging framework to incorporate images; (2) The presentation of an algorithm that merges identities based on face recognition software. (3) The combination of traditional text-based and the introduced image-based merge-approach to counter-balance the respective weaknesses of each of the approaches.

To this end, we first ground our idea by giving an overview of related work and introducing the fundamental concepts of entity resolution (i.e. re-identification) and face-recognition. Then we present our novel re-identification technique and discuss our prototype. Finally, we evaluate our procedure empirically on three real-world datasets and close with a discussion of the limitations, future work and some general conclusions.

Related Work

Winkler [26], showed that with a minimal set of attributes a large portion of the US population can be re-identified based on US Census data. Furthermore, Gross et al. [10] showed that about 80% of social network sites user provide enough public data for a direct re-identification and that at least 61% of the published profile images on Facebook.com allow a direct identification by a human.

Carmagnola et al. [4] and Bekkermann et al. [2] provide a cross-system identity discovery system, which is based on text-based identification probability calculations, whereby public available textual attributes of social network sites are analyzed by their positive, respectively negative, influence on identification. Further, [3] suggest the use of key phrase extraction for the name disambiguation process, which is also used in POLYPHONET [14] for interlinking web pages [13] and [22] provide re-identification algorithms based on network similarity. These system provide high accuracy, but lack on computational complexity and time expenditure.

A lot of research concerns shared approaches [12]: Especially, the application of common semantic languages , such as the FOAF ontology1 , the SIOC (Semantically-Interlinked Online Communities) ontology2 for online communities or the SCOT (Social Semantic Cloud Of Tags) ontology3 for tagging systems. Such systems are desirable, but not widely spread in reality. The most well-known system based on such data is FLINK [15].

Theoretical Foundations

In this section, we present the theoretical foundations for our approach. First, we present a formal model for entity resolution and then succinctly explain the basics of face-recognition. Both foundations are used in our framework.

Entity Resolution and the Fellegi-Sunter Model

Entity resolution can be defined as the methodology of merging corresponding records from two or more sources [26]. Consider for example a profile about "Peter J. Miller" and another one about "Peter Jonathan Miller" on two different SNS. Entity Resolution tries to decide if these two profiles belong to the same person or not. Therefore, entity resolution assumes that an individual shares similar features in different environments which can be used to identify an entity, even though no common key is defined. Generally, to complicate the resolution process, there are different entities that share similar attribute values.

Most current re-identification approaches are variants of the Fellegi-Sunter model-a distance-and rule-based technique. The Fellegi-Sunter Model determines a match between two entities by computing the similarity of their attribute (or feature) vectors [9]. Specifically, given entities a ∈ A and b ∈ B, where both A and B are the set of entities in SNS A and B, it tries to assign each pair (a, b) of the space A × B to a set M or U whereby:

M := is the set of true matches = {(a, b); a ∈ A ∧ b ∈ B ∧ a = b} U := is the set of non-matches = {(a, b); a ∈ A ∧ b ∈ B ∧ a = b}

It does so using a comparison function γ that computes the similarity measures for each of the n comparable attributes of the entities and arranges these in a vector:

γ(a, b) = {γ 1 (a, b), ..., γ n (a, b)}

Based on the comparison vector γ(a, b) a decision rule L now assigns each pair (a, b) to either to the set M or U as follows:

(a, b) ∈ M if p(M |γ)≥p(U |γ) U otherwise

whereby p(M |γ) is the probability that the comparison vector γ belongs to the match class and p(U |γ) that γ belongs to U . In other words, the Fellegi-Sunter model treats all pairs of possible matches as independent. Recently several authors argued that this independence offers the opportunity for enhancements. Singla et al [18], e.g., proposes such an enhancement based on Markov logic.

Face-Recognition and the Eigenface Algorithm

The face provides an enormous set of characteristics that the human perception system uses to identify other individuals. The problem of face-recognition can be formulated as follows "Given still or video images of a scene, identify or verify one or more person in the scene using a stored database of faces. Available collateral information [...] may be used in narrowing the search (enhancing recognition)" [25, p. 4]. Accordingly, face-recognition includes [25]: (1) The detection and location of an unknown number of faces in an image [11];

(2) The extraction of key facial-features; and (3) The identification [25, p. 12] which includes a comparison and matching of invariant biometric face signatures [25, p. 14 -16]. The identification can either be done by using holistic matching, featurebased matching, or hybrid matching methods which concern the whole face, local features-e.g. the location or geometry of the nose -or both as an input vector for classification respectively [25, p. 14].

Our re-identification framework uses the holistic face-recognition algorithm Eigenface [20] based on Principal Component Analysis (PCA) and covering all relevant local and global features [20]. The Eigenface approach tries to code all the relevant extracted information of a face image, such that the encoding can be done efficiently, allowing for a comparison of the information to a database of encoded models [25, p. 67].The Eigenface algorithm can be split up into two parts:

(1) Representation of the Image Database in Principal Component Vectors Based on PCA, the principal components of a face-image are extracted, by (1) acquiring an initial set of face images; (2) Defining the face space by calculating the eigenvectors (Eigenfaces) from the set and eliminating all but k best eigenvectors with the highest eigenvalues, by using PCA; and (3) Presenting each known individual by projecting their face image onto the face space.

Therefore, an image I(x, y) can be interpreted as a vector in a N -dimensional space, where N = rc and r are the rows and c columns of the image [20] . Every coordinate in the N -dimensional vector I(x, y)-the image space -corresponds to a pixel of the image. This representation of an image obfuscates any relationship between neighboured pixels as long as all images are rearranged in the same manner. Thus the average face of the initially acquired training set

Γ := {γ 1 , γ 2 , ..., γ m } can be calculated by γ = 1 m m n=1 γ n .

and the distance between an image and the average image is measured by φ i = γ i − γ. Whereby, the orthonormal vectors define an Eigenface with the eigenvectors:

u l = M k=1 e lk φ k ∀i ∈ [1, M]

whereby the eigenvectors e l are calculated from the covariance matrix L = AA , where L mn = φ m φ n and A = [φ 1 , φ 2 , ..., φ M ]. The derivation of the best eigenvectors out of the covariance matrix is presented in [19]. The k significant eigenvectors of L span an k-dimensional face space-a subspace of the N × N dimensional image space-where every face is represented as a linear combination of the Eigenfaces [20] [25, p. 67 -72].

(2) The Identification Process The identification respectively verification of an image is processed by: (1)Subtracting the mean image from the new face images and projecting the result onto each of the eigenvectors (Eigenfaces); (2) Determining if the image is a face by calculating the distance to the face space and comparing it to a defined threshold; and (3)If it is a face, classifying the weight pattern as a known or unknown individual by using a distance metric, such as the Euclidian distance.

Thus, a new face image I(x, y) will be projected into the face space by ω k = u k (γ − γ) for ∀k = [1, ..., M ]. The weight matrix Ω = [ω 1 , ..., ω M ] represents the influence of each eigenvector on the input image. Hence, given a threshold θ ε , if the face class k, which minimizes the Euclidian distance is

ε k = (Ω − Ω k ) and θ ε > ε k (1)

then the image will belong to the same individual. Else the face is classified as unknown. Furthermore, the distance between an image and the face space can be characterised by the squared distance between the mean-adjusted input image:

ε 2 = (φ − φ f ) , where φ = γ k − γ and φ f = M i=1 ω i u i(2)

Therefore, a new face image I(x, y) will be calculated as a non-face image if

ε > θ ε , as known face image if ε < θ ε ∧ ε k < θ ε and as an unknown face image if ε < θ ε ∧ ε k > θ ε .

Re-Identification Framework

Our theoretical re-identification framework for user disambiguation in a social network aggregation and cross-system personalization process. is based on the Fellegi-Sunter-Model. The presented algorithms calculate the probability that two user profiles belong to the same entity, and incorporates the ability to incorporate images as an additional feature based on the Eigenface method. Therefore, the framework provides three kind of methods: a pure face-recognition based, a text-attribute based, and joined re-identification method.

The methods follow a simple re-identification algorithm. Assume, two sets A = {a 1 , a 2 , ..., a m } and B = {b 1 , b 2 , ..., b n } of user profiles from two different SNSs. Each profile is characterized by a set of text attributes and a single profile image. We can now define E = {e 1 , e 2 , ..., e z } as the set of different individuals, who have a profile in one or both social networks. Consequently, the re-identification algorithm is based on the following three subtasks: Therefore, a distance d k of 0 indicates, that the two attribute instances are completely equal, and a value of 1 indicates the opposite. 2. Matching Probability Calculation: Then, based on the comparison vector γ(a i , b j ), the probability ρ(a i , b j ), that a pair (a i , b j ) belongs to the same entity, is calculated. 3. Merging Task: Finally, if probability ρ(a i , b j ) is greater or equal to a threshold value θ ∈ [0, 1] (i.e., θ ≥ ρ(a i , b j )) then the profiles a i and b j are assumed to belong to the same person.

Attribute Comparison and Matching Probability Calculation

The following three generic methods allow the comparison of n different attributes and the calculation of a matching probability. The methods cover the first two subtasks of the above introduced re-identification algorithm.

(1) Pure Face-Recognition Based Method The method re-identifies user profiles only by the application of the face-recognition algorithm Eigenface on profile images. Hence, ∀a i ∈ A ∧ b j ∈ B, the probability ρ(a i , b j ), that two profiles a i and b j belong to the same entity e l ∈ E, is defined as:

ρ(a i , b j ) = ε ij (a i , b j ) = (Ω ai − Ω bj ) ∈ [0, 1]

Whereas, it is assumed that the profile images are projected into the face space by ω ai = u k (a i − γ) and ω bj = u k (b j − γ). Additionally, the set B is used as training set for the initialization task, thus Γ = B.

(2) Text-Attribute Based Method The algorithm re-identifies user profiles by the application of text-attribute comparison. The attributes are compared with the token-based QGRAM algorithm [7]. Note that spelling errors minimally affects the similarity when using QGRAM, as it uses q-grams instead of words are used as tokens. For the k th -attribute the algorithm computes a normalized distance d(a ik , b jk ) ∈ [0, 1], where the distance is zero, if the value of the k th -attribute of a i and b j are syntactically equivalent. As we discuss in Section 6, we considered name, email address, birthday, city as a minimal set of text attributes in the experiments as they where shown to be strong indicators for identification [5] [26] [10] and other attributes such as address or phone number are often not accessible. As a result, the matching probability is calculated by a logistic function [8]:

ρ(a i , b j ) = exp(Y T (a i , b j )) 1 + exp(Y T (a i , b j )) ∈ [0, 1] where Y T (a i , b j ) = α 0 + n k=1 α k d(a ik , b jk )

The intercept α 0 and regression coefficients {α 1 , ..., α n } for the linear regression model Y T (a i , b j ) are learned by a logistic regression on a specific training set.

(3) Joined Method Finally, the two previously described methods are joined to a method that uses both face-image-based and text-attribute-based identification. Thus, for all pairs of profiles a i ∈ A ∧ b j ∈ B, it is assumed that the matching probability is equal to:

ρ(a i , b j ) = exp(Y J (a i , b j )) 1 + exp(Y J (a i , b j )) ∈ [0, 1] where Y J (a i , b j ) = α 0 + n k=1 α k d(a ik , b jk ) + βε ij (a i , b j )

Again, the intercept α 0 and regression coefficients {α 1 , ..., α n , β} for the linear regression model Y J (a i , b j ) are learned by a logistic regression on a specific training set.

Merging Task

Finally, based on one of the above introduced matching probabilities, a pair (a i , b j ) is called to belong to the same entity (i.e., (a i , b j ) ∈ M), if:

∀a i ∈ A ∧ b j ∈ B : θ ≥ ρ(a i , b j ) −→ M(3)

Prototype

Our re-identification framework consists of four major components. Currently, the Data Gathering and Acquisition module enables the acquisition of network data from the social network sites Facebook, LinkedIn, Twitter and Flickr, whereby only concerns public available data. The Data Preprocessing module preprocesses the crawled data by transforming profile attributes into an internal schema and establish connections between profiles for each relationship in the source network. The implementation provides functionality for both the integration of text attributes and profile images. For the integration of profile images, we use an implementation of the face detection algorithm OpenCV

Experiments

We evaluated the accuracy of the framework based on two experiments. In the first experiment we determined various input parameters, the intercept and the coefficients for the two regression models. The second experiment benchmarked the suitability of profile images for user disambiguation in the pure face-recognition and joined method against the text-based matching algorithm.

Experiment 1: Determining the Parameters

In the first experiment two social networks with a size of 47 and 45 were generated from data crawled on Facebook. 36 of these users had a profile in both networks. The profile image was randomly selected from all public available published images in the specific Facebook profile. We performed a pairwise comparison of the two sets, whereas for each pair the attribute similarities were stored as a quintuple [name, emailaddress, birthday, city, image similarity ] whilst varying the number of Eigenfaces in the image similarity computation. Finally, the optimal number of Eigenfaces and parameters for the two linear models were calculated using a logistic regression model in SPSS 7 .

Performance metric The profile image similarity measurements based on Eigenfaces were compared using Receiver Operating Characteristics (ROC) curves. The ROC-curve graphs the true positive rate (y-axis) respectively sensitivity against the false positive rate (x-axis) respectively 1 -Specificity, where an ideal curve would go from the origin (0,0) to the top left (0,1) corner, before proceeding to the top right (1,1) one [24, p. 244 -225]. The area under the ROC-curve (AUC, also called c-statistic in medicine) can be used as a single number performance metric for the merge accuracy. In contrast to the traditional precision, recall, or f-measure it has the advantage that both the ROC-curve and the AUC are independent of the prior data-distribution and, hence, serve as a more robust metric to compare the performance of two approaches. Results As illustrated in Figure 1, the number of Eigenfaces influences on the accuracy of match. The accuracy of the algorithm increases when increasing the number of Eigenfaces until a specific barrier, where any increase in its numbers is not beneficial or even detrimental to the overall performance. Thus, the Eigenface algorithm should use between 50 to 60% of the top-most Eigenfaces-a result similar to [24]. The resulting input parameters for the linear models are shown in Table 1.

Computational Costs The computational costs for the face-image comparison is higher than for single text-based comparison. On our test-machine (an Apple iMac computer with a 3.06 GHz Intel Core 2 Duo processor and 4 GB of RAM) the comparison of the four concerned text-attributes takes between 10 to 20ms per pair without data preprocessing; the image-based comparison alone takes 25 to 35ms/pair. Additionally, once per image, the face preprocessing, including face-detection and image resizing, takes between five and six seconds.

Experiment 2

For the second experiment we collected a subgraph of both Facebook and LinkedIn. Departing from the first author's profile we collected 1610 (Facebook) respectively 1690 (LinkedIn) profiles and manually determined that 166 users where present in both samples. We compared all these profiles with the three approaches using the input parameters determined in Experiment 1. Results Figure 2 graphs the ROC curves for the three methods. Note that whilst the text method (AUC=0.986) outperforms the pure image-based method (AUC=0.938), the combined method (AUC=0.998) significantly outperforms either methods (p = 0.001, p = 0.0001 compared with a non-parametric method described by DeLong [6]).

Discussion, Limitations and Future Work

As the above results show the combined method clearly outperforms each of others. It is interesting to observe that the ROC-Curve of both text-based and the image-based method both shoot almost straight up until about (0,0.9). Then the text-based method flattens out whilst the combined one continues to rise. This suggests that the element of the method's accuracy is contributed mostly by the image-based method. Only then does the image-based method contribute additional predictive power. When looking at the regression parameters this suggestion receives some additional support as the parameters for the Email and City lose in their contribution whilst the algorithm relies more on the N ame, Image, and interestingly the Birthday. Obviously, all these results are limited by the usage of only one, albeit realworld, dataset and will have to be validated with a others. Also, our experiment assumed that we knew the semantic alignment of the text-attributes. When merging only two SNS this assumption seems reasonable, when more are involved the this alignment may introduce additional error. Consequently, we probably overestimated the accuracy of the textual method.

Last but not least, a real-world system would probably not perform a full pairwise comparison to limit the computational expenditure but use some optimization approach.

We intend to investigate all these limitations in our future work. In this paper we proposed an extension of the traditional text-attribute-based method for re-identification in social networks using the images of profiles. The experimental results show that the pure face-recognition based re-identification method does not compete the traditional text-based methods in accuracy and computational performance. A combined method, however, significantly outperforms the pure text-based method in accuracy suggesting that it contains complementary information. As we showed this combined method significantly improves the accuracy of a social network system merge. Consequently, we believe that it provides a more solid basis for both researchers and practitioners interested in investigating multiple SNSs and facing the problems of multiplicity.