In large online social networks, Friend Recommendation has evolved into an interesting problem. We try to nd known acquaintances and new interesting friends on a Federated Social Network (FSN) , using StatusNet as our platform. FSNs are decentralized networks on the internet which can interoperate using the OStatus Suite of protocols. Friend nding on these networks is hard because we do not know the existence of other social networks or Users. We show how Linked Data representation like FOAF can solve this problem. We devise a model for the Federated Network centered around a User and use it to de ne the problem of Friend Finding. The solution uses two phases, rst known as Quick Connect which tries to nd old acquaintances. The second phase, Delayed Connect uses the Social Graph of Users to nd prospective friends. We show how the FSN information centered around a User can be extracted from FOAF entries and generate new recommendations. We shall illustrate the working of Talash as a part of StatusNet. We experimented on the existing FSN and collected feedback from its Users. The results are encouraging and open new avenues for Friend Finding on the Internet. To the best of our knowledge, this is the rst study of Federated Social Networks and the problem of Friend Finding in them.
E.1 [Data Structures]: Graphs and networks; H.3.5 [Online Information Services]: Web-based services Part of this work was done as Google Summer Of Code 2010 project for StatusNet Inc. Part of this was also done at Indian Institue of Technology, Kanpur, as a part of authors masters program.
Online social networks have evolved over the past few
years and have been interest of research for the
community. Social graph analysis has opened new avenues for
better user experience and expansion of these networks. The
term social networking is now synonymous with the various
activities such as commenting, replying, direct messaging,
like/faving, updating status etc.. Typically an Online
Social Network(OSN) for a particular User has three parts to
it [
Popularity of OSN sites like Orkut, Facebook, Twitter has
generated huge amount of data about the various interaction
of Users on the Internet. Social network analysis deals with
study of these networks and their properties[
Many forms of social networking have existed before OSN's.
Interaction on email within an organization has been an
area of interest[
A Federated Social Network (FSN) tries to break the
boundaries of the speci ed system in which the User interacts. A
User owns an online pro le page (website) on which he
describes himself and his connections. The connections, or
friends list is described in a machine readable format [
In such a federated scenario we study the problem of friend recommendation. Since each individual exists on di erent websites, it is very di cult to nd a speci c individual on the Internet that you already know, unless you know the exact website on which he exists. Once we know the website that pro le can be accessed.
In this work, we model the Federated Social Network of a User in the form of a graph. We give the problems faced by a system for Friend Finding in this setting. Initially we only consider nding those friends that a User already knows beforehand. Further we design an automated friend recommendation system for the Users. We show how the scale free nature of a social network a ects this recommendation system. We then exploit the properties of the social graph centered around a User to reduce the overheads in recommending new and nding interesting friends for a User.
The remainder of paper is organized as follows. Section 2 contains a review of technologies used, a quick overview of the OStatus Suite of protocols and Social Graph API. Section 3 builds a model of social graph and we formally de ne the problem of Friend Finding. Section 4 describes our approach to nding friends in federated social networks. We give a simple method to nd new acquaintances on the Internet, or those friends that, you did not know, already existed. We give the problems faced by this system and how the nature of graph centered around a User in Federated Social networks can be used to leverage the drawbacks. Finally we provide the experimental results to show the success of our method.
This system named Talash was built for the StatusNet
software and the results presented here are feedbacks from
the users of Identi.ca [
To de ne a Federated Social Network we break the phrase
into two parts and try to infer its collective meaning. The
term Social Network here is synonymous to the interactions
among individuals with each other. Since we are studying
OSN's we call the participants of this network as Users.
Every User has an online presence in the form of a web-page,
also known as the Pro le Page. That presence may be
either public or access controlled. Many di erent systems have
been developed for securing privacy issues on OSN's[
Typically, Users sign up on Online Social Networking Service (OSNS) e.g. Facebook, Orkut for networking with friends and family. All the mechanism of social network interactions are governed by and limited to the regulations of that online service. There are other Users signed up on the same OSNS with whom hhe can interact. Usually Users on one social networking service cannot interact with a User on another social networking service.
StatusNet is a microblogging platform that enables a User to set up his own public pro le. The activities of this User are now governed by his own regulations. He is not under any central authority or social networking service. The StatusNet software provides a set of protocols to interact with other independent pro les on the Internet. Since each of these pro les is federated (individually controlled and not under a central authority) in its activities and regulated by the User's themselves, we call this system a Federated Social Network.
In this paper we study the task of Friend Finding on this federated social network. In the following sections we give a brief overview of the OStatus Protocol suite and a centralized index of the Social Network on the internet - Social Graph API. 2.1.1
Previously known as the OpenMicroBlogging [
WebFinger : an open protocol to identify Users with their
email addresses [
PubSubHubBub: an open protocol based upon Publish
Subscribe architecture [
Salmon: [
Activity Streams: interactions of a User with his social
network are published to his subscribers and appear as a
stream of activities [
Any OSNS can independently develop a website which uses OStatus Protocols and can become a part of the FSN. Any User who has OStatus enabled on his pro le page can subscribe to or be subscribed by other Users on the FSN and we call such pro les OStatus Subscribable. 2.1.2
FOAF [
The social interaction of individuals can be modeled as
a graph, with individuals being nodes and the interactions
being edges if one User interacts with the other. For our
problem we look at the social graph generated by the social
interactions of Users on the internet. There are millions of
Users on the internet that are part of various Online Social
Networks. We study the graph whose nodes are public
proles and those that declare their connections publicly.
Former work [
Google has indexed the FOAF data on the internet and
made it available as the Social Graph API [
We now de ne certain notations which we shall use often in the paper.
Users: an individual who uses and interacts on the Federated Social Network.
Connections: the set of other Users with whom one User interacts. The interaction may be one way or two way.Connection are neighbors of a User on the social graph.
Public Pro le: an online webpage which describes the User and lists his publicly described connections. Status Update: an update posted by the User on his Pro le Page that can be seen by everyone else. Subscriptions: list of connections whose activities User follows and declares on his Pro le.
Subscribers: list of connections that follow a Users activities.
Friends: a common word to describe the connection. It might be an acquaintance, known individual, a subscriber or a subscription.
There already exist many systems on the web that behave
in a decentralized mechanism.TCP/IP, Email, DNS operate
in a distributed manner on the Internet [
Consider the federated social network existing on the Internet. Let there be N Users, each denoted by Ui 2 U where U is the set of all Users and i 2 1:::N . Every User Ui has a label which is a unique URL on the Internet. If any two
URL's are same, then they represent the same User, hence we assume that all Users Ui are distinct and hence unique.
For every User Uj, he keeps a list of connections in two separate lists. Sjin U n Uj is the set of all Users that subscribe to User Uj. Sjout U nUj is the set of all User's to whom Uj subscribes to and hence known as subscriptions of Uj. All the User's Uk 2 U n (Sjin [ Sjout [ Uj) are unknown to the User Uj and is denoted by the set H.
The interactions in this social networks are modeled as a graph. The G = (V; E) where V is set of vertices's and E is a set of edges. The V here is a set of User's in the social network, also equal to U . Each User (node) is uniquely dened by is URL of its public pro le. The edges are directed and Eij shows an edge from User Ui to User Uj.
We de ne a directed edge Eji if Ui belongs to the subscriptions list of the User Uj, that is Uj 2 Siin , and directed edge Eij if Uj belongs to the subscription list of User Ui, that is Uj 2 Siout .
Since the model is federated, any User Ui can never view the complete social network. He can only see or operate upon the network with Ui as the center and intereact with Siin [ Siout . This is the FSN centered around a User. If he needs to query the social graph of any User Uk , he sends a request to the pro le of Uk and is returned with the social graph of User Uk as its center. Figure 1 shows a FSN User labeled 65, and all his connections. All the friends are connected to the User 65, and may have interconnections between themselves.
Problem Statement: For every User Ui we choose a set Ri H such that for every Rij 2 Ri 1. Ui knows Rij 2. Ui will nd Rij interesting, if they know each other.
The notion of knows is de ned by the fact that, one User
appears in the others address book or has communicated
with the other atleast once over email or on other public
forums or online social networks. The relationship strength
between two Users can be modeled by the interaction
activity and the notion of knows can be made stronger [
The de nition of interestingness of one User to another
is relative and we say that one User will be interesting to
another if they share some common attribute. Tags for
people and status updates can also determine intrestingness of
a User [
Consider a new User on the Internet, a new addition to the FSN. Initially he does not have any subscriptions and subscribers and his pro le URL is unknown to the rest of the nodes in FSN. We have no social graph associated with this User at the center that can be analyzed to nd the rst set of subscriptions for our User. Its a Cold Start - where we don't have apriori knowledge about the User's friends and interests. Thus we divide the problem of nding friends in two parts. The rst deals with the cold start to provide the User rst set of subscriptions to interact with. We call this Quick Connect. The second approach known as Delayed Connect deals with analysis of User's social graph and nding prospective friends. 4.1
The idea of Quick Connect is to allow a User to
generate his rst set of connections as fast as possible. One of
the largest data stores of information about the di erent
contacts of a User is the Address Book. An address book
associated with online email services stores the frequently
contacted individuals. Email data can also be parsed to
nd the most contacted friends of a User and to mine their
Social Network [
Address books generally have a particular format which can be parsed to get the information about the contacts. They have various elds which can be of interest to our system. We extract the email address eld from the User's address book for all his contacts and use the Social Graph API to search for the contacts OStatus Subscribable public pro les.
Since most of the address books are easily available from
email service providers, its easy to access such contact lists
and generate a list of email addresses. OAuth [
The User is given a list of email service providers from which the address book information will be retrieved. The User is redirected to the OAuth Authorization page on the service providers OAuth endpoint. After the User delegates authorization, the service provider returns an OAuth Access Token and and OAuth Secret Token. This pair can be used in future to access the address book data without
Users intervention. The User can alternatively revoke an Authorization to stop access.
When returned from delegating authorization, the User is
shown a list of his contacts page by page. Here he is given an
option to email the contact to invite him to create his own
presence on the Federated Social Network. Simultaneously,
the request is en-queued in the StatusNet software's Queue
[
The background process of download the address book additionally queries each email address on the Social Graph API. This returns a list of public pro les of the contact. If these are OStatus Subscribable then the User is noti ed about it. This way User's can directly subscribe to FSN User's whom they already know. Figure 2 shows the OAuth Authorization followed by handing over of OAuth tokens to the StatusNet Queue Handler. The address book is downloaded and Social Graph is queried to check whether it is OStatus Subscribable.
Quick Connect is used partially in many social networking websites. This is the rst instance in which we search for User's not on the same domain. In case a centralized database of social graph as provided by the Social Graph API does not exist, WebFinger protocol can be used to query the contact email address. The Linked Data representation of friends list in the form of FOAF can be parsed to obtain this information.
The method has a disadvantage of many HTTP GET requests to download the address book and to query the prole page of each contact through the Social Graph API. It is a long process for address books containing thousands of contacts. The use of StatusNet background queues coupled with OAuth access token to a User's data allow download of all the contacts without the User's intervention. 4.2
In an online social network, a User tries to expand his social boundaries by connecting to more friends. These maybe his long lost classmates, new friends based on similar interests or connecting to new communities. The graph expands slowly and the Quick Connect provides enough fuel to give him the initial set of connections to interact with. Once all the contacts in the address book are analyzed for their presence on the Internet, the responsibility of further expansion of the User's social graph solely lies with him. This is the section where we illustrate the friend nding algorithm of Talash.
The existing social graph of the User is now analyzed and uses the social graph API to recommend prospective friends. We also de ne the problem of nding connections that might be interesting to the User. The algorithm will try to uncover the prospective social network as seen by a User.
This method is named Delayed Connect because the execution of this mechanism is not instantaneous and is heavy on resources e.g. Bandwidth. We can run this mechanism for any User whenever we have available resources and suspend the completion in its absence. Delayed Connect believes in expanding the social graph of the User very slowly, so as to give him enough time to share his thoughts and interact with his existing network. 4.2.1
A User might be interested in interacting with friends from
same community, geographical location or similar interests.
Interestingness of a pro le is de ned with respect to our
Users pro le information. Interestingness can also be
dened in terms of Similarity between two pro les. If the two
pro les display content on similar topics, if the biographies
of both the User's declare a geographic location close by, or
they are both connected to same set of friends, then we say
that the pro les are similar and they might be connected for
interaction on the social network. Many di erent similarity
functions can be de ned given the various attributes of each
User [
We augment the model given in Section 3.1 to include Pro le attributes. Pro le attributes is a set of attributes declared by the pro le owner as being his own. Formally we augment every node of the FSN by a feature vector F = a1; a2; :::; an where ai is a pro le attribute denoted by a key value pair of fAttribute Name : Attribute Valueg. Since each User on FSN controls his pro le, the number of attributes he declares is his wish. Hence di erent User's may have di erent set of attributes and di erent in number. We assume that Attribute Names are are unique and uniformly used. Hence an attribute of name 'Location' on two di erent pro les will denote the same attribute.
A Similarity function is de ned which takes two pro les
P1 and P2 and returns a similarity score between them. The
function returns a score between the two attribute vectors
provided by each pro le. Various metrics such as common
friends, graph distance, Adamic-Adar [
Since each pro le is not centrally controlled and Attributes
can be newly added by installing plugins [
We now turn our attention to identifying new connections whom we can recommend our User to subscribe to. We return to the mathematical model described in Section 3.1 and remind that a User does not have holistic view of the FSN. The User can only see and access his connections, all his subscriptions and subscribers, and the publicly displayed connections of his friends. This idea is captured in the FSN centered around a User. User does not know anything beyond two hops from the him.
The Social Graph API is used to identify new connections for the User (say Ui). For every Subscription Sij 2 Siout for User Ui we query the Social Graph API for his publicly declared connections. We parse the response from the API to generate a list of Users which are at two hop distance from Ui, let this denote a set F oafi.
For every pro le F oafik in F oafi we use two criterion on which we recommend the pro le to the User.
Friends You Already Know : For every pro le F oafik in F oaf we re-query the Social Graph API to nd all his public pro les and the publicly declared connections on that pro le. If F oafik is connected to Ui on some other social networking service, it is possible that they know each other beforehand and its safe to recommend the pro le to the User. Instances of such a recommendation is when two friends are connected on sites like Twitter or Flickr! and do know about each others OStatus Subscribable accounts. The social graph of prospective connection is queried and its checked whether the User Ui is connected to him on other OSNS. If yes, we can recommend the new connection's OStatus account to Ui for subscription.
Interesting Pro les: For every pro le F oafik the Similarity function is provided with two pro les, F oafik and Ui. The function returns a similarity score based on the attributes of two pro les. A pro le is called Interesting if the score is greater than 0. The score can be also used to rank each connection in F oafik in decreasing order of their similarity scores. The connection with higher similarity score is more interesting than the others. 4.2.3
The number of friends of friends found at two hop distance from a User in FSN grow exponentially. For example, consider a User Ui with 400 subscriptions. Each of the subscription has at least 400 connections. The number of HTTP requests generated to nd interesting friends for Ui is about 160000. Figure 3 shows how the number of Friends and number of Friends of Friends varies for every User. The X axis shows the Users of the FSN and places them in the order they joined the FSN. The Users with higher User ID have lesser number of Friends since they have joined recently. However they have a very high value for Friends of Friends.
We implemented a Cache to store the Social Graph API. For each connection Sij for User Ui, we store its connections in a database with a time-stamp. The tuple stored is of the form fSij , Sjk, TIMESTAMPg, where Sij 2 Siout is set of subscriptions User Ui and Sjk is the set of subscriptions of Uj . The cache served the twin purpose of skipping the HTTP request to Social Graph API in immediate future (Till the entry was invalidated) and allowing interruptions in the Delayed Connect due to network disruption. 4.3
We now outline the algorithm used to identify new connections which can be recommended to the User. 1. Consider the FSN centered at the User. Find the communities to which he belongs by removing the User and nding connected components in this graph. 4.2.3 shows 3 such communities formed. 2. For every friend in the community we can nd his FOAF to nd prospective connections. Top log(n) friends (ranked by number of subscribers) are chosen and their FOAFs are requested. 3. For every FOAF, the similarity function evaluates the score of interestingness between the User and FOAF. 4. Top log(jF OAF j) connections of the FOAF are returned as recommendations.
Experimenting on the system designed and discussed in this paper is a challenging task since the StatusNet software can be con gured by any User of the FSN. User's can select what plugins to run and control the features displayed on their pro le page such as their location, tags and biographies. The results of this system can be only seen when the algorithm runs on the Users StatusNet instance and the network evolves with the help of these algorithms. User's may independently add new friends and connect to newly joined friends and family members.
We experiment on a snapshot of the Federated Social
Network using the network formed on Identi.ca [
A manual feedback is the best test of the system and can gauge the usefulness of our algorithm. The choice of friends a User would like to have is dependent on the User's interests. We used the Similarity function to nd the similarity between the User and the prospective connections and hoped that the User will accept them. We were not able to test Quick Connect for these Users because each one owned their instance and did not have our system installed.
Each User was provided with a set of prospective connections called the recommendation set. The User was asked to mark the connection as accepted on rejected. We call the accepted connections as positives. Figure 5. shows the percentage of positives against the size of the recommendation set. It was seen that the User's accepted not more than 4-5 prospective connections. For a recommendation set of size larger than 10, very few Users accepted all the connections. A User is recommended a set of size larger than 10 when the User is part of many communities (so that each community recommends at least one connection) or belongs to one large community (size of log n). A trend was seen that Users marked at least one positive from each community and tended to discard a majority when most connections came from a single community. This means that the algorithm is able to nd the best recommendable connection in each community to which the User belongs with the quality decreasing with increase in size of community. 5.2
For every community of the User which recommends a new connection we nd out how much the cluster improved in its bonding. The average shortest path length of the cluster are good indications of how the individual communities to which the new User belongs has improved the bonding in the system. The average shortest path length in a cluster quanti es this value with a value of one meaning tighter interaction where everyone in the community knows each other (Clique) and a higher value meaning that the community is loosely interacting (everyone does not know each other). A value lesser than 1 means that some Users are not reachable from some other User in the network.
For a graph G = (V; N ), let d(u; v) be the shortest path length between nodes u an v. The average shortest path is
The motivation for clustering a User's FSN into communities was to nd recommended seeds and to reduce the number of HTTP requests made to the Social Graph API or to WebFinger(if it existed). Figure 6. shows the size of communities to which a particular User belongs. We see that more than 50% of User's belong to a single community. Such User's are either new and have very less subscriptions or tend to interact with a closed group of User's. This reenforces our idea of using recommender seeds from a community to nd newer connections for our User. User's from same community will interact closely and will not overlap signi cantly with other communities. For example, Users from a family may choose to interact only with their family members. A User from that community may be part of another community , say Presley Fan Club. The community nding exercise can also give the User an indication of why the new connection is being recommended.
Figure 7 shows the number of HTTP requests sent to nd new friends for each User on the FSN. The number of such requests is reduced drastically. If all the recommendations are accepted by a User, the size of each community of the FSN centered around the User increases. Hence, the recommendations count will keep increasing and will expose the User to newer prospective friends in every iteration. The log n upper bound for choosing the size of recommendation set gives rise to slow growth of FSN of a User. The feedback collected from the User's of FSN showed a trend of having lesser positives when the recommendation set was very large.
The federated nature of the social network enpowers Friend Finding algorithm to be executed on individual Nodes of the FSN. The network can evolve independently and expand at each node as required by the User. We showed a simple mechanism to nd new friends on this network and show how we can depend on the Friends Of a Friend information alone to extract this information. Clustering of a FSN centered around a User into communities allows expansion of a Users FSN in all the domains he is interested. Community based categorization of recommendations is a valuable addition to our algorithm and can be used in various applications where the community feature can be exploited.
The algorithm makes many heuristic assumptions and exact evaluation of them can be only made by analyzing the behavioral pattern of the User for whom the recommendation is made. This is a rst attempt to experiment a friend nding algorithm on federated networks. The actual impact of this algorithm can be felt only when the network evolves considerably using this system.
We would like to thank Evan Promodrou and his team of StatusNet developers for constant support and interaction during the Google Summer of Code 2010. We would also like to thank Dr. Sanjeev Saxena for his guidance. A part of this work was a result of discussions with him during the work carried out under his supervision for the Masters Program at IIT Kanpur. The authors thank the anonymous referees for their valuable comments that helped improving this paper.