The most popular collaborative filtering implementations require either a critical mass of referenced resources and a lot of active users. Other solutions are based on finding a referral with an expertise on the given domain of discourse. In this article we present the semantic social collaborative filtering solution to information retrieval. We describe how the concept of users' managed collections can be exploited to provide collaborative filtering system based on social network maintained by the users themselves. We present FOAFRealm, a user profile management system based on the social networking and the FOAF metadata. FOAFRealm enables distributed collaboration between parties in the semantic social collaborative filtering way.
The contemporary Internet contains a lot of information. In the unorganised
structure of the Web all the information that we are looking for seems to be
always just behind the corner. Though, still beyond our scope. And when we
fail to find that information, it turns to be useless. Search engines and online
catalogues tend to return a lot of resources as an answer to our queries. Very
often some of results are unrelated to given queries. No wonder, we end up
asking our friends and acquaintances for interesting references on the exact topic.
Collaborative filtering is an idea of automating the process of asking around when
looking for the information on the Internet[
Since early implementations of collaborative filtering, like introduced in [
Outline of the paper The next section describes the architecture of the semantic social collaborative filtering in the context of other similar solutions. In section 3 we present the evaluation of the underlying model of social interactions in the semantic social collaborative filtering. We describe in section 4, the FOAFRealm system that implements a distributed user profile management system and delivers semantic social collaborative filtering features. Later, we discuss the relations between social collaborative filtering and digital library systems. 2
The semantic social collaborative filtering presented in this article is based on two concepts: distributed collections and annotations of resources. Each user classifies only a small subset of the knowledge, based on the level of expertise he/she has on the specific topic. This knowledge is later shared across the social network. 2.1
The problem that there is a trade-off between accuracy and scalability is often found in search engine applications. The information gathered in online collections is very precise, as the human factor is involved in the indexing process. But since the Internet is growing so fast, the process of creating the catalogue does not scale. On the other hand, search engines do the indexing work without involving the human activity. And results of queries are not always satisfiable.
A social network is a set of people or group of people, with some pattern
of interactions or ”ties” between them[
It is possible to construct a subgraph, on top of a social network, that represents flow of expertise in the certain domain. The idea of the semantic social collaborative filtering is based on this observation. Each person in the social network gathers the interesting information in collections he/she has created. Collections maintained by other people can be easily linked into own collections created by the user. As we show later (see section 3) the information disseminated through the collections linking across the social network corresponds to the expertise level on particular subject in the social network.
Distributed collections. The information is gathered in colletions by a number of people.
Each of them handles specific domains of discourse within the colletions information space he/she has created. The quality of the information gathered across the colletions can be satisfied by approving the expertise in given domain of discourse.
Each user maintains his own
collections (private bookshelf [
In our example scenario, Alice writes a thesis on ”Mediation in Bibliographic Ontologies”. She registers to the digital library run by the University. She discovers that some of her friends are already registered to the library as well. With features based on online communities, she connects her profile to her friends profiles. Later on, Alice starts to gather the information required for her thesis topic. She keeps links to resources she has found in collections managed by the online bookmarks system. Soon she discovers that resources that she has bookmarked do not cover the topic of the thesis at satisfiable level. The following sections describe different algorithms Alice uses to find the desired information with the help of the semantic social collaborative filtering.
Simple Social Collaborative Filtering To find the desired information Alice sings up to the university digital library. The system used by the library is based on the simple semantic social collaborative filtering implementation (see Fig. 1). Alice uses the searching features provided by the digital library web application (see Fig. 2(a)) to find interesting resources.
We introduce a solution to the problem stated in previous section (see 2.2) – a simple semantic social collaborative filtering model (see Fig. 2(b)). Each collection is categorised by the owner. Collaborative filtering feature in the digital library lists all the collections, within the given range of friendship neighbourhood, with topics related to the ones defined by Alice. Each collection has a quality level assigned to it. The quality of the collection corresponds to the expertise level of the owner on related topic. The expertise level can be computed with PageRank algorithm applied to graphs of collections inclusions and social network. Both graphs represents the rank value each person and each collection receives from other people. The rank values are assigned directly (by people to people) and indirectly (by including someone’s collection to own collection).
Alice finds out that one of her friends, Caroline, gathers the information about digital libraries and her expertise level on that topic is very high. Though her direct friend Bob is interested in Artificial Intelligence, she finally decides to link resources provided by Eric, who has a highly ranked ”Semantic Web” collection. From now on, Alice takes the advantage of the information gathered by Caroline and Eric in their collections.
Secured Semantic Social Collaborative Filtering Alice is still looking for more information required for her thesis. She decides to register in an open, hererogenous digital library. Some people protect their collections with access control restrictions (see Fig.3). The restrictions applied on the collection are based on maximal distance and minimal trust level between two people in the social network graph. Apart from defining friendship relations, users express the quality (trust level) of every outgoing social connection.
Since not all information should be accessible by everyone, some of it need to be protected from people from the outside of the given community. This is why access control lists (ACL) have been introduced (see Fig.4(a)). In the semantic social collaborative filtering environment based on ACL each collection has its own ACL, that defines the maximal distace and minimal friendship quantisation level from the specific person1 to the person willing to access that collection. Only when this is satisfied the user can access and include this collection in his/her collections.
Alice wants to make use of the knowledge provided by Damian. But the algorithm for retrieving a list of collections in the secured environment (see Fig.4(b)) omitted some of collections. With ACL applied Alice is out of the range defined in Damian’s ACL constrains. The collection managed by Damian is not presented to her. 1 please note that it does not have to be an owner of the collection, thought the owner is the one that manages ACL procedure ListCollectionsSM (p,t) : collections[] for p0 ∈ P with PeerDistance(p,p0) < knowsRange C0 ← C0 S PeerCollection(p0) end for sort C0 according to FinalRankingSM end procedure
(a) Algorithm retrieving list of collections P is a set of peers C is a set of collections F oaf Knows is a set of directed connections between peers Gpeers(P, F oaf Knows) is a digraph of friendship relations T is a lattice of categorisation topics We assume that each collection c ∈ C has exactly one owner p ∈ P .
PeerCollection: P → 2C – returns all collections owned by the peer
OwnedBy: C → P – returns the owner of the collection
Expertise: (P, C) → [
(b) Definition of model
The main bottleneck of existing passive collaborative filtering systems is the
process of gathering users’ preferences[
Active collaborative filtering solutions depends on maintaining the social network by users themselves. Outdated information on list of friends can mislead the person in his quest for an answer.
Backward Referral Chaining Maintaining a list of friends, posting a question and gathering the answers may be time consuming. That is why the social collaborative filtering (a new approach to active collaborative filtering) tends to ease some hardships by introducing the concept of backward referral chaining, reusing existing classification schemata and extrapolating user’s profile information with interests of his friends.
Usually, a user is not aware of the whole social network. To gather the knowledge outside of his direct friendship neighbourhood the user has to rely on references provided by his friends. Because the expert in the specific domain can be quite distant from the user, in terms of relationship links, the access to the answer provided dependents on the path to an expert. As it has been introduced in 2.2, an expert can restrict the access to some parts of information by applying access control lists.
The referral chaining[
Connection to the established classification schemata. In social collaborative filtering each person can create own categories according to the local understanding of the world. The definition of the category might be hard to understand to other peers because of the use of ambiguous descriptions or an native language.
We propose to apply additional semantically reach description based on
existing thesauri or classification ontologies, like WordNet[
ACLP D is an access control constrains, defining maximal distance D (in number of
’hops’) from user P
ACLF Q is an access control constrains, defining minimal F riendshipQuantization
value (calculated across the graph) from user P
DistanceACL: (C) → 2ACLPD – defines a list of allowed maximal distances to the user
QuantizationACL: (C) → 2ACLFQ – defines a list of allowed minimal
F riendshipQuantization values
Peer: (ACL) → P – returns a peer from which the computation of ACL dinstance/level
is do be performed
Distance: (ACLP D) → N – returns the maximal distance defined in ACL
Quantisation: (ACLF Q) → [
(a) Definition of model
procedure ListCollectionsACL(p,t) : collections[]
cp ← PeerCollection(p)
for p0 ∈ P with PeerDistance(p,p0) < knowsRange
Extrapolated user’s profile. When information about user’s activities
(personal bookshelf, resources’ annotations) is gathered for a longer time it can be
re-used during the search process. The query expansion process[
New users registered to the system very often suffer from lack of rich profile information. This may have a strong influence on the quality of search results. To overcome this problem then social collaborative filtering paradigm introduces the concept of an extrapolated user’s profile. The profile of the new user can be represented with some probability depending on trust level (see 2.4) as a combination of profiles of his/her friends. Collaborative filtering implementations suffer in most cases from very weak security features or frequent privacy abuse. The information about the user in passive collaborative filtering systems is very often gathered without his knowledge. In the active collaborative filtering the user very often has no chance to protect himself from gathering information about him.
To implement the security and privacy features the concept of digraph of interpersonal connections have been utilised. Each user defines a list of his friends and states the level of trust to each of them. The user can then define the maximal distance and minimal trust level required from the person which wants to view information gathered in specific category.
As all the information about the user is provided by himself and he/she manages the access control lists for each piece of information, the privacy of the user is preserved. 3
Semantic social collaborative filtering utilises existing social networks instead of creating artificial connections between people. That is why on the contrary to other collaboration filtering solution, there is no need to evaluate an algorithm for creating a social network, as the social network is given explicitly.
On the other hand, since the semantic social collaborative filtering is based on friendship connections, the actual similarities of interests between connected users might differ. That is why, the evaluation of this collaborative filtering approach should prove that the dissemination of knowledge is possible within graph of semantically annotated friendship connections.
Simulation model In this section we present the implementation of the simple semantic social collaborative filtering model. We prove that average level of expertise in the subgraph of social network is almost maximal within 6 degrees of separation.
The definition of a simulation model has been based on similar ideas defined
in Refferal Web project[
Underlying assumptions. In the model of social network for the semantic social collaborative filtering, each user manages collections with information on selected topic. The different users represent different expertise on the given topic. We assume that: – The quality of the information provided by a user on a certain collection is proportional to the expertise level of the user on the topic of collection. – It is possible to find a user with a high expertise on given topic within the network of social connections.
According to simple social collaborative filtering model (see Fig. 2(b)) the simulation environment is modeled by a set of users and a set of collections managed by those users. There is exactly one user that owns each collection. On the base of the user’s expertise on related topic the quality of the collection is defined. Each user has a predefined set of other users he knows (this relation should not be considered as implicitly symmetric).
Although according to the Small World Phenomena[
O(i) =
n iθHθ(V ) , Hθ(V ) = XV i1θ
i=1 f (x) = √ 1 2πσ2
(x−μ)2 e− 2σ2 (1) (2)
The distribution of expertise on a certain topic within the social network
can be based on the Lotka’s Law[
In order to make sure that there would be at least one absolute (Expertise(T ) = 1) expert in each topic T , we have normalised the associated expertise values dividing each but the value of the highest expertise in each topic.
The list of topics used to describe content of collection has been based on
Dewey Decimal Classification[
AverageMaximalExpertise + = NeP end procedure Definition of the experiment. During the experiment each user (p ∈ P , sizeOf(P ) = NP ) tries to find in the social network within a given range R, the collection that provides the information on the topic t ∈ Tp. The topic is randomly selected from the list of topics associated to collections owned by the user. The average value of the highest expertise E¯max(R) level found within given range is computed (see Fig.5).
We have performed four experiments. Each time the social network model consited of NP = 1000 users.
Each user in our social collaborative filtering environment had only one collection associated. This simplification is correct since during the experiment we are looking only for collections with exactly the same topic as selected. So collections associated with each topic creates a subgraph that is independent of the actual number of collections owned by each user.
The expertise level for each collection has been randomly selected according
to power law distribution. In the first two experiments the degree of
friendship connections has been randomly selected according to normal distribution
(μ =25, σ =12.5). In the last two experiments the power law distribution
(θ =1.9) has been applied. During each experiment average maximal expertise
values E¯max(R) has been calculated for maximal degree of separation R ∈ [
It is interesting that even for the power law based distribution user is able to find information with almost the highest possible quality within 6 degrees of separation (see Fig.6).
The FOAFRealm is a library for distributed users management based on the
FOAF vocabulary. It enables users to control their profile information, as the
information can be accessed in the open FOAF format. Users can sign-in
automatically across the P2P network (called D-FOAF2) of FOAFRealm enabled
systems[
FOAFRealm provides a basic implementation of the semantic social collaborative filtering concept. The knowledge (annotations and private collections) can be shared among registered users. Security constraints can be applied to each piece of information separately.
The current implementation of FOAFRealm consists of four layers:
– The distributed communication layer providing access to highly scalable HyperCuP3 P2P infrastructure to communicate and share the information with other FOAFRealm implementations.. – FOAF and collaborative filtering ontology management. It wraps the actual RDF storage being used from the upper layers providing simple access to the semantic information. The Dijkstra algorithm for calculating distance and friendship quantisation is implemented in that layer. – Implementation of the org.apache.catalina.{Realm,Valve} interfaces to easily plug-in the FOAFRealm in to Tomcat-based web applications. It provides authentication features including autologin based on Cookies. – A set of Java classes, Tagfiles and JSP files plus list of guidelines that can be used while developing user interface in own web applications.
The library has been successfully deployed as a user management system in JeromeDL - e-Library with Semantics4. It is used to handle private bookshelves of readers, and provides additional semantical annotations to the resources. The concept of extrapolated user profile has been adapted in the semantically enhanced search engine in JeromeDL. So that even new users to the system can benefit from the full-fledged semantic search process.
The FOAFRealm system has also become a part of MarcOnt Initiative5 collaboration portal for ontologies management based on negotiations. The portal will utilise social networks based features of FOAFRealm to: – isolate outside world from the ontology management community. The registered users will be allowed to take part of the ontology management process when they will be defined as a friend of at least on of the community members. – differentiate evaluations of ontology changes suggestions provided by different members of the community. We will explore if evaluations provided by close friends of the person that posted the suggestion should be ranked lower than evaluations provided by people with higher degree of separation from the suggestion owner. 5
Collaborative filtering. The most popular types of the collaborative filtering systems are Active Collaborative Filtering and Passive Collaborative Filtering. The distinction between those is based on the activeness of the user that receives information. With passive collaborative filtering, the information about the user, such as: mailing-lists posts, links on home pages, citations in publications and co-authors of articles, is utilised. Since the user does not actively take part in maintaining his network of friends, he has no direct impact on information he/she receives. 3 Lightweight HyperCuP Implementation project: http://www.hypercup.org/ 4 JeromeDL - e-Library with Semantics: http://www.jeromedl.org/ 5 MarcOnt Initiative: http://www.marcont.org/
Active collaborative filtering implements two models of information retrieval: user pull model - where a user generates a query to the network of other users, and user push model - where the answers on previously stated questions or information filters, are feed to the user.
Though by shifting from central (a search engine) to a distributed method of
recommendation the problem tends to be more manageable, particular
collaboration filtering implementations suffer various difficulties: (1) ”heterophilous
diffusion” (exchange information across different socio-economic groups) is
neglected in favour to ”homophilous diffusion” (exchange of information within
socio-economic groups); (2) security and privacy issues are weakly supported;
(3) meaning (semantics) of shared concepts are lost; (4) when the network of
friends is created automatically by harvesting various databases with advance
algorithms: the ”critical mass” of registered users is required to provide
satisfiable level of correlation to user’s interests; it is impossible to create a digraph of
social connection from most of commonly used sources; privacy of individuals is
violated; monopolies are supported[
Hybrid filtering[
Active collaborative filtering solutions concentrate on utilising the existing
social connections provided explicitly. One of the approaches [
To format and distribute collections of bookmarks several simple system have
been developed. With Simon system [
Some of them, like Orkut6 provides forum-like channels of dissemination of knowledge, where community members can ask questions to their friends
or other members of specific thematic group. In the Semantic Web field the
FOAF (a vocabulary for RDF [
User Profile Management The existing implementations of user profile management lack: (i) fine granularity of security constraints; (ii) scalability; (iii) openness/privacy. Both of which play important roles in semantic social collaborative filtering.
One of the features that is becoming more and more important in social P2P
environment is single-sign-on[
The semantic social collaborative filtering presented in the article opens new possibilities of exchanging and managing knowledge. Users can share their bookmarks (collections and their content) with their friends. Everyone can organise the knowledge by gathering collections that other people are maintaining. Since collections can be linked it is possible to find more relevant information in categories provided by some distant people. Annotations are also a key part of the semantic social collaborative filtering. Together with private collections (private bookshelves) they are utilised in the semantically enhanced information retrieval in systems like digital libraries.
FOAFRealm is a reference implementation of the semantic social collaborative filtering. It refers to social networks and open standards like FOAF. FOAFRealm provides support for J2EE based web applications for quick extending their features with user management and social collaborative filtering. Since the social network is represented as a digraph, FOAFRealm utilises informations about distance between two people and the trust level, to provide the security and privacy features.
Current implementation of FOAFRealm, D-FOAF, provides a distributed user profile management system and hence, the social semantic collaborative filtering across different systems. The future step, DigiMe, will deliver this features to mobile devices and will explore the ad-hoc social networks paradigm.