Considering that thousands if not millions of linked datasets will be published soon, we motivate in this paper the need for an e cient and e ective way to rank interlinked datasets based on formal descriptions of their characteristics. We propose DING (from Dataset RankING) as a new approach to rank linked datasets using information provided by the voiD vocabulary. DING is a domain-independent link analysis that measures the popularity of datasets by considering the cardinality and types of the relationships. We propose also a methodology to automatically assign weights to link types. We evaluate the proposed ranking algorithm against other well known ones, such as PageRank or HITS, using synthetic voiD descriptions. Early results show that DING performs better than the standard Web ranking algorithms.
Following Marshall and Shipman [
Two issues come to mind when talking about selecting
(possibly many) datasets: e ciency and e ectiveness.
While the former basically refers to how fast certain datasets
can be identi ed, the latter focuses on the relevancy, that
is how well the dataset ful lls the stated requirements in a
certain context (the domain of the Web application). When
faced with a list of potential candidates, one usually wants
to rank them according to certain criteria in order to select
the most relevant ones.
1A simple estimation might support this argument: take for
example relational databases such as MySQL found in nearly
every modern Web application, or the manifold
repositories in the software development domain (for example, CVS
or SVN) or registries (LDAP, OPACs, etc.)|each of them,
once on the Web of Data (using out-of-the-box linked data
publishing tools such as Triplify [
Our thesis at hand now is that, based on a formal
(highlevel) description of a dataset's content and interlinking
provided by voiD, Semantic Web clients can e ectively rank
datasets using well-known strategies such as PageRank [
The rest of the paper is structured as follows: the next section discusses exitsing approaches. Then, we lay out the foundations regarding the formal description of linked datasets in sec. 3 and render our proposal in detail (sec. 4). Further, in sec. 5, we report on early ndings when comparing our approach to widely used ones such as PageRank or HITS. We conclude in sec. 6 by discussing the proposed ranking methodology and point out possible future steps. 2.
Link analysis has proven to be e ective for query
independent quality web search. PageRanks [
When working on a ner granularity level - such as entity level - with more heterogeneous links, the previous approaches are no longer applicable. In such condition, by assuming that links are equivalent, the analysis of entity relationships does not provide accurate results since links of di erent types can have various impact on the ranking computation.
Recent works [
The Swoogle search engine [
In this paper, we are studying how to improve search results by ranking datasets according to their popularity. Our approach is based on link analysis between datasets by using the information provided by the voiD descriptions. We consider the types of relationships but also the cardinality of link sets. We propose also an automatic weighting scheme to nd appropriate weights for relation types.
In order to realise our vision of a semantic ranking, we
build upon a formal description of the datasets and their
interlinking. Only recently the Vocabulary of Interlinked
Datasets (voiD) [
Given that such voiD descriptions are published alongside
with the datasets, they can be collected via pings, by
crawling, or simply follow-your-nose by a semantic indexer such
as Sindice [
Our proposal for a semantic ranking of RDF datasets is called DING (from Dataset RankING) and is based on voiD descriptions of the datasets. 4.1
Based on the voiD guide [
The size of the dataset, that is, for example the
number of triples or the number of distinct subjects
can be used for ranking. In voiD this is a void:statItem
property along with one of ve prede ned dimensions
such as void:numberOfTriples or
void:numberOfDocuments. We have argued in [
Categorisation of datasets in voiD is done using
dcterms:subject along with DBpedia [
The interlinking of a dataset in voiD, that is, its outgoing and incoming links, is represented using the void:linkPredicate property. We identify two potential dimensions that might be exploited for ranking: { regarding the semantics of the links (such as rdfs:seeAlso vs. foaf:knows) and { on a quantitative level, that is regarding the number of interlinking triples.
The kind of and number of used vocabularies in a dataset can be seen from the void:vocabulary property value.
Other voiD characteristics such as void:uriRegexPattern or the technical features of a dataset (such as available serialisations) via void:TechnicalFeature) can not directly be used for ranking, though perfectly for ltering (as in case with categorisation).
The following example in Fig. 1 may help highlight our thinking:
In this section, we present how we adapted the weighted PageRank algorithm in order to perform the Dataset ranking based on their interconnection. We then explain how it is possible to assign automatically a weight to a certain link type.
PageRank is a ranking system that originates from Web Search Engines using a random walk algorithm. The Ranking system evaluates the probability of nding the web surfer on any given page. This algorithm is based on the assumption that when someone publishes a resource on the web, he will do his best to link the published resource | be it a web page, or in our case | a dataset | to the most relevant and trustworthy resources availiable on the web. Hence the relevancy is assumed to be related to a high degree of inlinks from other web resources. And from a probabilistic point of view | the more inlinks a dataset has, the most likely the 'random surfer' will be lead to it in his journey.
The original PageRank r(Pi) of a web page i is given by r(Pi) =
X
r(Pj) Pj2BPi jPjj (1) 10 1 : DS1 a void : Dataset ; 2 foaf : homepage < http :// example . org / cats / > ; 3 dcterms : subject
< http :// dbpedia . org / resource / Cats > ; void : subset : DS1toDS3 ; void : subset : DS1toDS4 . 4 5 6 7 : DS2 a void : Dataset ; 8 foaf : homepage < http :// petfood . example . org / > ; 9 dcterms : subject
< http :// dbpedia . org / resource / Cats > ; dcterms : subject
< http :// dbpedia . org / resource / Pet_foods > ; void : subset : DS2toDS1 . Where BPi is the set of pages linking to Pi and jPjj is the total number of pages linked by Pj . Hence, jP1jj is in fact the probability for the random surfer to choose to go from Pj to Pi out of all pages linked by Pj. This probability referred to as pj!i, can be modi ed in order to provide a weighting of the "importance" of the hyperlink.
The parallel from web documents to voiD descriptions is done in a naive way. The web pages are now datasets, and the hyperlinks correspond to linksets joining the dataset they belong to another:
Pi corresponds to an element Di de ne by void:dataset. A hyperlink form in the page Pi pointing to the page Pj will correspond to a void:linkset element connecting Di and Dj, de ned as void:subset of a dataset Di. The linkset will be referred to as Li!j. We also de ne n(Li!j) as the number of relations in the linkset, and s(Li!j) as the predicate declared in the linkset. For example, in Fig. 1 n(L1!3) = 600 and s(L1!3) = "foaf:interest". L is the set of linksets de ned in the entire data collection.
Similarly to the set BPi of pages linking to Pi, we de ne O(i) = fjj9Li!j 2 Lg as the indices of datasets linked from Di. pi!j can be modi ed according to the information available about the linkest Li!j, such as s(Li!j) or n(Li!j), as well as general statistics over L.
Like in the web page link analysis, the links between datasets deserve a deeper analysis in order to obtain a ner ranking. For example in Fig. 1 the probability of the user going from DS1 to DS3 is likely to be di erent from the (2) (3) (4) (5) probability of going to DS4 - since the predicate and number of links associated to L1!3 are not the same as the ones associated to L1!4.
The goal will hence be to de ne a weight function w(Li!j). The weight will then be normalized in order to generate the transition probability pi!j as follows.
pi!j = Pk2O(i) w(Li!k)
w(Li!j) The rst approach is simply to de ne w(Li!j) = n(Li!j) . 600 In the case of Fig. 1, p1!3 = 2000+600 ' 0:23 and p1!4 = 2000 2000+600 ' 0:77. However, this de nition does not take into account the nature of the link, and the likelihood that the user may well chose foaf:interest above dc:author to browse into another dataset. As a result, additional weights can be assigned based on the nature of the predicate involved in the link.
The values assigned can be either statically prede ned, or computed dynamically, given the accumulated voiD information. We present our approach, based on TF-IDF a well known algorithm when it comes to weight the relevance of a term(in our case - the predicate), given its frequency in a data collection. Hence, the weight, given by TF-IDF would be
T F (Li!j) =
n(Li!j) maxk2O(i) n(Li!k) IDF (s(Li!j)) = log
N 1 + f req(s(Li!j)) Where f req(s(Li!j)) is the frequency of occurrence of linksets using the predicate of Li!j in the collection's datasets. Finally, we de ne w as w(Li!j) = T F (Li!j)
IDF (s(Li!j))
In order to verify our thesis that formal descriptions of linked datasets help yielding better results for the ranking of the datasets, we have set up an evaluation framework that executes various ranking algorithms on a synthetic voiD description2(see Fig. 2). It is composed of 15 arti cial dataset descriptions interlinked using 8 di erent predicates and partitioned into two clouds (datasets 1 to 9 and 10 to 15). The experiment used several ranking algorithms to estimate the generic relevancy of every arti cial dataset within the synthetic cloud. 5.1
For the evaluation we use the Java Universal Network/Graph Framework (JUNG)3 to compare the DING algorithm with other established and well known ranking algorithms. Further, we use a naive link-sum rank function (DRank ) as a baseline to discuss the results. Three out of the four ranking algorithms are also extended with the DING link weight function. In detail we evaluate and compare the following ranking algorithms: 2The full benchmark data is available at http://sw.deri. org/2009/02/DING/example-void-collection.ttl. Unfortunately no real-world voiD cloud was readily availiable for the experiment at the time of writing. 3http://jung.sourceforge.net/ DRank: A baseline ranking algorithm using a naive approach. The datasets are ranked according to the number of links they have with other datasets.
PageRank Google's page rank algorithm [
DING PageRank modi cation of the PageRank
Algorithm as described in Sec 4.2
HITS Another well known ranking algorithm is HITS
[
Table 1 lists the results of the evaluation. The naive ranking approach, DRank, completely leaves out the rst cloud for having much less links in its linksets than the second cloud. We see that standard PageRank and HITS algorithms do not take into account the nature of the links and rank DS1 rst. Although DS1 is indeed heavily linked by other datasets, it is mostly inlinked by "weak" links like owl:sameAs or rdfs:seeAlso. The information-theory view de ned in tfidf suggests that these links | being the most common ones | do not hold as much information content as less common ones, and are therefore less signi cant. For example while looking for information about an article, the user will get more precise information following dcterms:author than a generic property such as rdfs:seeAlso, and is hence more likely to follow the former. As a result a dataset linked by uncommon links will likely be more significant than one linked by common ones - and should have a higher voiD ranking.
Another advantage of PageRank that makes it very relevant for the Linked Data approach is that it gives a low ranking to datasets that do not have inlinks. The value of a dataset within the cloud is dependent on how well it is linked by other datasets.
We have presented DING, a new approach to rank linked datasets based on voiD descriptions. Though one might object that currently there are not many voiD descriptions available4 we argued that this is very likely to change soon. Further, the infrastructure to collect voiD descriptions is in place (voiD being RDF, the requirements to do so are minimal).
We have motivated the need for a e cient and e ective way to rank datasets based on their characteristics (contentwise and with respect to the interlinking). Finally we have shown how DING performs in relation to existing ranking algorithms and discussed the results. 4Indeed one nds voiD descriptions at time of writing, already; see for example http://void.rkbexplorer.com/.
Our work has partly been supported by the European Commission under Grant No. 217031, FP7/ICT-2007.1.2, project \Domain Driven Design and Mashup Oriented Development based on Open Source Java Metaframework for Pragmatic, Reliable and Secure Web Development" (Romulus)5, by the European FP7 project Okkam - Enabling a Web of Entities (contract no. ICT-215032), and by Science Foundation Ireland under Grant No. SFI/02/CE1/I131. 7. 5http://www.ict-romulus.eu/