The rise in use of the social web has forced web users to duplicate their identity in fragmented information spaces. Commonly these spaces contain rich identity representations hidden within walled garden data silos. This paper presents work to export social graphs from such data silos as RDF datasets, and provide linkage between these social graphs according to a graph matching paradigm. Our work contributes to the linked data movement by providing a decentralised social graph containing linked data describing fragmented identity components.
The social web has allowed web users to replicate their ofine lives and actions in an online environment. Sharing photos, messaging friends and networking to build relationships both socially and professionally has drawn users into using social web platforms to organise their lives. This has brought about the generation of rich social data attached to individual web users, describing their online identity. Properties of this identiy include biographical information; name, address, date of birth, and social infrormation; relationships, contacts and a liations. The modern web user has a fragmented identity distributed over multiples platforms and services. Each service contains a di erent social graph, aggregating each graph would generate a clear description of the person, who their contacts are with useful contact information, and an identity reference point through a URI. Work by the linked data1 community has linked together existing accessible social web data sources (Flickr exporter, DBPedia) and published the linked content. Despite social web platforms and services o ering advanced functionalities to enhance a person's online identity, exporting the internal social graph is not supported therefore inhibiting access to useful datasets. Such sites are described as 'data silos', where data is hidden within a walled garden. Exported and aggregated social graphs from di erent services could be used when signing up to a new web service to import the user's existing social network, trust networks could be created based on transitive relationships in the social network, and recommendation systems could retrieve suggestions based on the imported social graph (based on the actions of social network members).
This aggregation also creates a dentralised description of a
person's online identity. The aggregation contains linked
data which can be referenced for additional identity
information from distributed data silos. Thus exporting
information from closed data services and opening up information
for reuse [
In this paper we present our contribution to the linked data project by describing an approach to export social data in a semantic graph format using RDF from a range of social web services, and aggregate the generated RDF by providing links between the exported datasets. The former component relies on mapping XML schemas to the appropriate ontology, whereas the latter is a graph matching problem providing links between person instances in separate graphs that are found to refer to the real world person or entity. Deciding when a link should be created is an issue due to the non-existence of global unique identi ers for people, using simply the name of a person is problematic due to name ambiguity. Therefore we utilise as much additional semantic information as possible to aid the linking process. We present our own approach to matching person instances using low-level reasoning, and evaluate its success against two formal graph matching functions. 2.
Representing social data found within social web services
and platforms has been investigated by the SIOC
(SemanticallyInterlinked Online Communities) project2. Work by Bojars
et al presented in [
Social data extraction was described by Halpin in [
Our approach to aggregating social graphs is split into two distinct stages: The rst stage generates RDF using the necessary ontologies from various social web services, and the second stage then aggregates these social graphs. RDF provides a useful formalisation to describe information within each data silo, capturing biographical information and social network information. Where possible our approach must provide links to social network members in separate networks that are the same person. Based on these functionalities we have de ned four requirements that our approach 2http://sioc-project.org/ 3http://www. ickr.com 4http://tools.opium eld.com/twitter/mattroweshow/rdf 5http://www.twitter.com 6http://qdos.com/ 7http://foafbuilder.qdos.com/ 8http://www.w3.org/2004/01/rdxh/spec 9http://www.gmpg.org/xfn/ 10http://www.facebook.com must ful ll: 1. Export social data contained within data silos into the same semantic form. 2. Link person instances from separate social networks referring to the same real world person. 3. Maximise the number of correct links while minimising the number of incorrect links.
Exporting social graphs from walled garden data silos
commonly involves the trivial task of mapping XML schemas
o ered by the web service to a semantic speci cation. We
extend our previous work in [
We have created social graph exporters for two social networking sites. The rst exporter extracts social data from Facebook by mapping the returned XML response to the FOAF ontology thus capturing the identity information, and the social network consisting of instances of foaf:Person linked by the foaf:knows property to provide relationship ties. The FOAF ontology is well suited to capturing social information due its extensive expression and de nition of identity information. Thus we consider XML schemas used by social web services to be subsets of the FOAF speci cation. We found that there were no properties that we could not map from the XML schema to concepts from the FOAF ontology.
Geographical information including city and country is formliased as an instance of geo:Feature by assigning the person's city and country to the geo:name and geo:inCountry properties from the Geonames ontology13. We chose the Geonames ontology due to its adoption by the Semantic Web community as a standard for describing geographical concepts. Each social network member is assigned a URI using the user identi cation number from the service, unfortunately the exportation of email addresses and web sites is not allowed which would serve as a useful dereferencing point. The following is a snippet of the RDF exported from Facebook. <foaf:Person rdf:ID="#me"> <foaf:name>Matthew Rowe</foaf:name> <foaf:givenname>Matthew</foaf:givenname> 11http://openid.net 12http://ext.dcs.shef.ac.uk/~u0057/SocialGraphAggregator/ 13http://www.geonames.org/ontology/ We applied the same approach when exporting social graphs from the social networking site MySpace14. As MySpace follows the OpenSocial15 speci cation, our exportation tool can be adapted to easily extract social graph information from several other social networking platforms supporting the same speci cation (Bebo, Orkut, Hi5). As the OpenSocial speci cation and MySpace's data accessibility are still in development at the time of writing this paper and conducting our work, we were unable to extract rich social network data. This reduced the exportation process to only the person name of each social network member described using foaf:name and the user identi cation number from the site which was employed as a URI, each is assigned to an instance of foaf:Person which we bind to the social graph owner using the foaf:knows property. The ability to only extract person names and a URI meant that we were unable to export geographical information.
For exporting RDF from the micro-blogging site Twitter we followed the same methodology as the exportation of social graphs from the previous social networking sites. Twitter also o ers an XML response (without the required authentication) enabling a mapping to be made between the XML schema to concepts from the FOAF ontology. As Twitter allows access to geographical information we model this data as an instance of geo:Feature, and assign the city and country to the geo:name and geo:inCountry properties respectively. Each social network member is described using an instance of foaf:Person, and the geo:Feature instance is assigned using the foaf:based_near property. We also used the display name used by each member of the social network as their URI. Figure 1 shows an example social graph exported from Twitter. 4.3
14http://www.myspace.com
15http://code.google.com/apis/opensocial/
Following the exportation of social graphs from their
hosting service, it is essential to enrich the graph where
possible. The rst stage of the exportation process only
creates a geographical reference using the place name which
can cause problems with ambguity. Therefore we enrich
this representation by resolving the place name with unique
identi ers. To perform this process we query the Geonames
Web Service16 (which accesses the Geonames dataset) using
the geo:name and geo:inCountry properties assigned to the
geo:Feature instance for each social network member. This
returns a list of possible URIs for the location. We select
the most relevant URI from the list and then assign this to
the geo:Feature instance, and the latitude and longitude
of the location which are assigned using the geol:lat and
geol:long properties from the Geolocations vocabulary [
Aggregating social graphs identi es matching foaf:Person instances in separate graphs and provides links between these instances using the owl:sameAs property. The main challenge we face is deciding if two instances of foaf:Person with the same name in di erent social networks refer to the same real world person or entity. To make this decision we formalise a graph from each instance of foaf:Person and all outgoing properties and relations in the social network: This graph contains biographical information about the person, which can then be compared using graph matching techniques to derive a similarity measure and therefore the possibility of a match.
Formally we de ne the person graph as G = hV; Ei where V denotes all the nodes within the graph represented as resources and literals extracted from the foaf:Person instance in the social network, and E denotes the edges con16http://www.geonames.org/export/ necting those nodes represented as semantic relations and properties. Therefore the social network found within a given FOAF le contains a set of person graphs, each describing a di erent real world entity. Imagine we have two FOAF les F1and F2 where g 2 F1and h 2 F2 describes all the graphs within F1 and F2 respectively, and a similiarity function sim(g; h) that measures the similarity of the two graphs: Our task is to nd the graphs in both F1 and F2 that achieves the maximum similarity measure whilst exceeding a given threshold, and therefore provide a match. This reduces the aggregation problem to a graph matching task; to investigate this procedure we now present three alternative methods for computing graph similarity. We evaluate and compare the success of each method later.
Graph matching using node and edge overlap as described
in [
jVgj + jVhj + jEgj + jEhj
When generating the intersection of the node set from g
and h we used the Levenstein string similarity measure [
Work by [
Pin=1 max(strsim(sig; s:h)) + Pjn=1 max(strsim(ojg; o:h))
#mappings
The application of the approach in [
Due to the semantic structure of the graphs we are comparing it is possible to utilise semantic metadata to detect a positive match using some basic low-level reasoning: Imagine we have two graphs that we wish to compare: We extract the string literal from both graphs connected from the foaf:Person instance using the foaf:name property, thereby returning the person name of each graph. We compare the names using the Levenstein string metric to derive a match. If the names match we then move on to comparing other properties from each graph to con rm that the foaf:Person instances are in fact referring to the same real world object.
Unique identi ers, where available, can be exported from social web services and de ned using the foaf:homepage, foaf:mbox and foaf:phone properties for the website, email address and telephone number respectively within the social graph. We nd the edges in each graph that point to such unique identi ers, and compare them. Our intuition is that a match would provide su cient con dence to con rm the link between foaf:Person instances in both social networks. However, should an edge only exist in one graph there is not su cient knowledge to con rm the link, therefore we move on to analysing further semantic information de ned in the graph space.
When deciding if two people from di erent social networks refer to the same real world entity we rely on geographical information as another useful information source for reaching a match decision. We follow the intuition that the owner of several social networks would not be friends with two or more people who share the same name and live in the same place. For example, a person named "Matthew Rowe" is friends with "Sam Chapman" on Facebook, and friends with "Sam Chapman" on Twitter. It is likely that "Sam Chapman" refers to the same person in each social network. On Facebook "Sam Chapman" is described as living in "She eld" and on Twitter "Sam Chapman" is also described as living in "She eld". Therefore we believe such additional information is su cient to con rm that both instances of "Sam Chapman" are the same person, and should therefore be linked.
We extract the geo:Feature class attached to each instance
of foaf:Person by the foaf:based_near property. In the
previous section, we added additional geographical edges to
the geo:Feature instance to describe the latitude and
longitude of the location, together with a URI obtained from
the geonames web service. Given that we wish to
compare instances of foaf:Person sharing the same name, we
rst compare the location URI assigned to the geo:Feature
class. Should the URIs match then we con rm that both
foaf:Person instances refer to the same real world entity.
However, if the URIs are di erent we compare the
geographical proximity of the locations. Our reasoning behind this
comparison is that people will divulge more sensitive
information in di erent social networks, for example in a walled
garden social networking site the user feels safer, averting
prying eyes and would therefore state what suburb they
reside in. Conversely, on a micro-blogging platform the user
may only de ne the city they reside in. One method is to
derive the geographical distance using the latitude and
longitude described by the geo:lat and geo:long properties,
and calculate the distance between the two points using the
Haversine formula from [
?districts . ?districts <http://www.w3.org/2004/02/skos/core#prefLabel>
?city } This query returns the literal \Districts of She eld" describing the label for the DBPedia category containing all districts in She eld. The geo:name property can then be matched against this literal to con rm that the location \Crookes" is a district of \She eld" and therefore the graphs should be linked as they refer to the same real world entity. We de ne the similarity function using the following pseudocode: sim(g; h) :
Get person name ng from g using foaf:name Get person name nh from h using foaf:name If strsim(ng; nh) > threshold
If mboxg=mboxh
return match Get homepageg from g using foaf:homepage Get homepageh from h using foaf:homepage
If homepageg=homepageh 17http://dbpedia.org return match Get location URI geoidgfrom g assigned to geo:Feature Get location URI geoidhfrom h assigned to geo:Feature If geoidg = geoidh
return match Else If geoidg = null and geoidh = null
return maybematch Else
Get city name cg from g using geo:name Get city name ch from h using geo:name return checkSuburb(cg; ch)
return nomatch checkSuburb(cg; ch) :
Get districts of city label lg for cg If strsim(lg; ch)
return match Else
return maybematch As we demonstrate above, the sim() function returns three classes of match: match, maybematch, and nomatch. If the foaf:name and geo:Feature URI match in each graph then we are fairly con dent that the foaf:Person instances refer to the same real world entity, we also believe that the same level of con dence should be attached to matching a suburb using the the checksuburb() function. In both cases we return match. However, we are less con dent when location infomation is not available for either person, likewise if we cannot discover if either foaf:Person instance's location is somehow related, therefore we only return a maybematch. Only when the foaf:name properties do not match are we con dent that the foaf:Person instances refer to di erent people.
Following the previous section we now have a set of matched graphs where each graph refers to the same real world entity or person. We produce links between these representations in the form of a new RDF graph describing the aggregated social graph content. We do not wish to duplicate information contained within each exported social graph, but instead provide links to this information for later reuse (we explain our reasoning behind this decision in the preceding subsection). For biographical information we aggregate all available properties from each social graph to generate a complete identity representation. For example the Facebook social graph contains identity information such as name, and data of birth, whereas the Twitter and MySpace social graphs contain the homepage, aggregating this contain defragments this person identity to generate a complete prole.
A new social network is created containing the
aggregation of individual social networks from each social graph,
matched instances of foaf:Person are merged to create a
new instance as follows:
For this instance we only include the foaf:name property
and an identi er. We use hash values for identi ers
according to guidelines described in [
By providing linked data representations for each instance of
foaf:Person in the aggregated social graph we attempt to
minimise the duplication of personal information while o
ering decentralisation through linked data. This minimisation
is an essential component of the defragmentation of
identity information. It also passes responsibility for data access
to separate locations and therefore separate access policies.
For example, if a person may wish for their Facebook
social graph to remain separate and only accessible by people
they know and trust then access responsibility is delegated
to the hosting service. Work by Yeung et al presented in [
Another motivation behind this design decision was for the allowance of extensibility and addition of new triples into the aggregated social graph. If we imagine that a user has created their aggregated social graph containing exported social data from Facebook and Twitter, meanwhile they have also recently built up a rich social graph of contacts and information on the professional networking site LinkedIn20. Linking this new social graph to the existing aggregated graph only requires the addition of new triples to the exisiting sctructure, which in essence would be either a new foaf:Person instance linked by the foaf:knows property for a new person in the aggregated graph space, or a new owl:sameAs relation pointing to the foaf:Person instance in the exported social graph from LinkedIn.
In order to evaluate and compare the success of our graph matching methodology against the two alternative methods we generated three les containing valid RDF according to the FOAF ontology. Each le was obtained from a di erent web service (Facebook, MySpace, and Twitter) using the exportation methodology described in section 4, and each le holds information related to one web user who has an account with each social web service.
We analyse the success of the three matching methods when attempting to match instances of foaf:Person in the different datasets by evaluating for type I errors (false positives) and type II errors (false negatives). Positives indicate a match and therefore where the datasets should be interlinked for that concept, negatives indicate where a match should not take place and therefore no linked data should exist. The optimum method should produce neither of these error types.
Figure 3 demonstrates how each individual dataset used in the experiment contains possible overlaps which should be linked together. These overlaps consist of social network members from each dataset who are the same person. For example, "Sam Chapman" appears in the Facebook dataset, and "Sam Chapman" also appears in the Twitter dataset, therefore a decision must be made whether a link could be established. The lack of an intersection between the Twitter and MySpace datasets is due to the fragmentation of identity information in each data silo. The user in question whose information we extracted from each service, used Twitter for professional purposes, Facebook for both professional and social, and MySpace for music and social purposes. Therefore the music and professional elements should not overlap, thus separating the Twitter and Myspace datasets.
Tables 1 and 2 show the results obtained from our analysis together with the gold standard indicated in the nal column. As we can see from Table 1 node/edge overlap returns 20http://www.linkedin.com True Pos True Neg False Pos
False Neg the poorest results by correctly matching the fewest person graphs and also incorrectly matching the most person graphs. Node mapping performs well but still falsely classies 3 instances of foaf:Person as being no matches. Graph Reasoning outperforms both previous methods by producing the most correct links between the person graphs. The reason for this method's outperformance is due to the large number of triples available in each person graph. Both the Facebook and Twitter datasets contain rich social data that can be exported from each service, namely geographical information that can be used to classify positive matches. In the experiments we permitted links to be created for foaf:Person concepts that returned a maybematch when performing graph reasoning.
The matching of graphs within the Facebook and MySpace datasets yields interesting results. As Table 2 demonstrates node/edge overlap performed poorly by only nding 2 instances of foaf:Person that intersected the datasets. Node mapping derived 10 positive links between foaf:Person instances, but incorrectly created 107 links. Graph Reasoning did not classify as many correct links as node mapping yet only falsely generated two links between the datasets. The results from this part of the evaluation throw up some interesting points: When we consider that we wish to minimise the number of false links, then the most naive method; node/edge overlap is the most reliable, however this procedure creates very few correct links. The reason for the poor performance of node mapping (generated 107 incorrect links) and graph reasoning (only generating 5 correct links) is due to the triples available in each dataset. Unlike the Twitter dataset, the MySpace dataset only contains a name property for each instance of foaf:Person. This means that the graph matching task has very few triples and therefore a limited graph structure to perform low-level reasoning with, and in the case of node mapping must rely heavily on the string similarity metric to derive the mapping which as the results demonstrates is unreliable.
As mentioned previously when discussing the datasets for use during the experiment, the Twtiter and MySpace datasets do not contain any overlap. When performing the experiments none of the three graph matching methods produced links between these datasets, therefore we decided to omit the results as there was nothing to present.
This paper presents our work investigating the exportation of social data described using semantic ontologies, and the linking of this data where possible. Comparing the outcome of this work with the previously detailed requirements it is clear that social data has been exported from data silos in a semantic form, and person instances from separate social networks are linked together where possible. Our method to perform low-level reasoning when matching person graphs yields good results in comparison with similar methods by maximising the number of correctly matched person instances and minimising the number of incorrect matches.
The produced RDF containing linked data describes links between matched person instances. Our decision not to aggregate all biographical information for each social network member is due to the privacy policies that we believe social data must adhere to. Instead, links to the existence of this data are provided. The data contained within the exported social graph data can then be controlled by a separate access policy. This ts in nicely with recent work to address privacy and trust within the Semantic Web community, where technologies such as FOAF+SSL (to control social graph access) and POWDER21 (to describe social graph properties) are being adopted.
Our future work will include additional social graph exportation tools for other web services, and also the release of the aggregation service. We also plan to test our graph matching approach on additional larger datasets, and hope that existing XML schemas expand to allow additional information to be exported.
We would like to thank both Harry Halpin and Sam Chapman for allowing their information to be presented in this paper as examples. And also Neil Ireson for his meticulous proof reading expertise. 21http://www.w3.org/TR/2008/WD-powder-dr-20081114/