Web search engines are traditionally focused on textual content of data. Emergence of social networks and Web 2.0 applications makes it interesting to see how social data can be used in improving the conventional textual search on the web. In this paper, we focus on how to improve the effectiveness of web search by utilizing social data available from users, users actions and their underlying social network on the web. We de ne and formalize the problem of social-textual (socio-textual ) search and show how social aspect of the web can be e ectively integrated into the textual search engines. We propose a new social relevance ranking based on several parameters including relationship between users, importance of each user and actions users perform on web documents (objects). We show how the proposed social ranking can be combined with the conventional textual relevance ranking. We have conducted an extensive set of experiments on the data from online radio website last.fm to evaluate the e ectiveness of our proposed approaches. Our experimental results are very promising and show a signi cant improvement for socio-textual ranking over textual only and social only approaches.
Social networks on the web have grown signi cantly over the past few years. People have started to reconstruct their friendship networks in the virtual world and many of these virtual relationships are good representatives of their actual (friendship) networks in the real world. At the same time and with the emergence of Web 2.0, many web users have started to engage more with the web. In contrast to the traThis research is supported in part by the NSF grant IS-1115153, the USC Integrated Media Systems Center (IMSC), and also by unrestricted cash and equipment gifts from Google, Microsoft and Qualcomm. The opinions, ndings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily re ect the views of the National Science Foundation.
Copyright c 2012 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors.
CrowdSearch 2012 workshop at WWW 2012, Lyon, France ditional web where users are often in read-only mode, Web 2.0 have enabled users to be in read-write mode. In other words, users have started to express themselves in the forms of generating and publishing content (e.g., writing a tweet), re-sharing interesting content by others (e.g., re-tweeting) and rating/evaluating the existing content (e.g., choosing a favorite tweet). This emergence of social networks and Web 2.0 resulted in huge amount of data available that can be utilized in many domains.
In this paper, we focus on taking advantage of this
information in the domain of (textual) web search. We argue that
by integrating information from users' social networks and
their activities on the web, we can improve the conventional
textual search and ranking. In today's web, we can know the
existence and degree of relationships among people and also
at the same time have the knowledge of people's interests
derived from their actions/activities on the web. It is both
intuitive and proven [
We rst review the few existing studies regarding social search and utilization of social networks in the web search.
Then, we de ne and formalize our problem. Next, we present
new scoring methods to calculate social relevance between
users and documents (objects). We show how the
importance of users, di erent relationships among users and ac- or +1ed that result. Their algorithms are not public and it
tions they perform on objects can impact the nal relevance seems that they only show the likes and +1s and the actual
ranking. After proposing the new social relevance model, we ranking is not a ected.
present a novel socio-textual relevance ranking technique to There exists a relevant but somehow di erent topic of
folkcombine textual and social relevance rankings. Finally, in sonomies. Tags and other conceptual structures in social
our experimental section, we evaluate the e ectiveness of tagging networks are called folksonomies. A folksonomy is
our proposed models and show that our new relevance rank- usually interpreted as a set of user-tag-resource triplets.
Exing methods are e ective and improve the accuracy of the isting work for social search on folksonomies is mainly on
returned results. improving search process over social data (tags and users)
gathered from social tagging sites [
There are two groups of related work on the application tags themselves are of signi cant importance.
of social networks in search. With the rst group, people Finally, there are few studies on the role of collaborative
through their social networks are identi ed and contacted ltering in this new social context. Role of social networks
directly to answer web queries. In other words, queries are on collaborative ltering is studied in [
The main focus of the second group is on the search pro- late documents (movies) authorities based on users' ratings
cess over social data (tags, users and objects) from sites/application(using collaborative ltering) instead of pagerank and other
with social aspect such as social tagging sites and (some) link-based authority measures. Social networks of users are
Web 2.0 applications. In [
In a set of similar papers [
Most of their experiments are limited to a small number of queries on YouTube videos with 3 users, 15 queries and small number of textual keywords. Relevant (interesting) result is a result (video) whose category is simialr/equal to the dominant category of videos that searcher has uploaded.
In a relatively older paper [
In this section, we formally de ne and formalize the problem of socio-textual search.
Objects: We assume a collection O = fo1,o2,...ong of n objects (documents). An object can be a traditional web document such as a news page or a business home page or a Web 2.0 object such as a YouTube video, a tweet, a Facebook status or any other similar entity. An object o is composed of a set of textual keywords Ko and a set of users Uo associated with it. Uo is a set of users with some type of actions on the object o (see actions below).
Users and Social Network: There is a set U = fu1,u2,...umg of m users using the system. We also assume a social network modeled as a directed graph G = (V; E) whose nodes represent the users of the system and edges represent the ties (relationship) among the users. The most common type of relationship is the friendship relationship but other type of relationships can be also applied (e.g. follow relationship in Twitter).
Actions: There is a set A = fa1,a2,...alg of l actions that users can perform on the objects. These actions represent the relationship between users and objects. For instance, in Twitter, users can perform the following actions on objects (tweets): publish a tweet, retweet a tweet or make a tweet as their favorite tweet.
Socio-Textual Query: A socio-textual query is de ned as Q = hKq; Sqi, where Kq is the textual part of query speci
ed as a set of keywords in the query and Sq is the social part of query speci ed as the user uq issuing the query and the social network G. Since our social network is always G, it is su cient to de ne the socio-textual query as hKq; uqi. Note that while the textual part of the query is always explicit in the query, the social part is often implicit. In other words, we can safely assume that the system (search engine) knows the user issuing the query and also the underlying social network, hence the social part of the query can be automatically added to the textual part by the search engine.1
User relevance: User ui is relevant to user uj if the network distance from the node corresponding to ui to the node corresponding to uj is less than or equal to a system de ned threshold value . The less the distance between two nodes, the more (user) relevant are those two nodes (users) 2. Network distance can be any of the existing network distances in the literature. Two users with the network distance more than are considered non-relevant to each other.
Social relevance: Social relevance between the object o and the query q is de ned based on the social relationship that exists between the querying user (uq) and users associated with the object o (Uo). Object o and query q are socially relevant if at least one of the object's users (Uo) is user relevant with the user issuing the query. The larger the user relevance is, the more socially relevant o and q are. We denote social relevance of object o to query q by socRel(o; q).
We de ne social relevance in more details in Section 4.
Textual relevance: Object o is textually relevant to the query q if there exists at least one keyword belonging to both o and q, i.e., Kq \ Ko 6= ;. We represent textual relevance of object o to query q by texRel(o; q). 3
Socio-textual relevance: Object o is social-textual (sociotextual) relevant to the query q if it is both socially and textually relevant to the query q. Socio-textual relevance can be de ned by a monotonic scoring function F of textual and social relevances. For example, F can be the weighted sum of the social and textual relevances:
F (o; q) = :socRel(o; q) + (1 ):texRel(o; q)
(1) . is a parameter assigning relative weights to social and textual relevances. The output of function F (o; q) is the socio-textual relevance score of the object o for the query q, and is denoted by stRel(o; q). In Section 4 we show how to calculate socio-textual relevance.
Socio-textual search: A socio-textual search identi es and ranks all the objects that are socio-textual relevant to the query q. The result is the top-k objects sorted based on objects' socio-textual relevance scores. The parameter k is determined by the user.
1Naturally, here and in other parts of this paper, we consider only users who willingly make their social information public to the system. 2For simplicity of presentation, from now on, we assume that users' social network is implemented as an undirected graph. Hence, user relevance and other relationships between users will be symmetric. 3In this paper, we do not focus on textual relevance models. We use popular tf-idf model when we need to calculate textual relevance.
In this section, we propose a new social relevance model to calculate the social relevance between users and objects. We also show how to combine the proposed social relevance model with an existing textual relevance model and introduce our socio-textual relevance ranking.
We rst propose a new scoring approach to calculate the social relevance between an object o and a query q (issued by user qu). Our social relevance ranking creates a new scoring framework to retrieve and rank objects based on the social dimension of the query and objects. In order to have an accurate scoring function and retrieve the most socially relevant results to the user, we consider three important factors: (1) relevance of each user to the query's user, (2) importance of each user in general, and (3) relationship between users and actions they perform on each object. In the following we discuss each measure.
User Relatedness. We measure the relatedness of a user to the querying user (and hence to the query itself) by the user relatedness function urf (uq; ui). There are several measures to calculate the relatedness/closeness of two nodes in a graph/social network. Some of the approaches consider the distance between nodes, some look at the behaviors of users in a social network and some take into consideration number of mutual neighbors of two nodes. While the required data is available, any of the above methods or other exiting methods can be used for the user relatedness function as long as the following three constraints are satis ed: (1) urf (ui; ui) = 1, (2) 0 urf (ui; uj) 1 and the more relevant the users, the higher the value, and (3) urf (ui; uj) = 0 when urf (ui; uj) < . The rst constraint states that each user is the most related user to herself. The second constraint normalizes this measure and also ensures that the more related users are assigned higher scores. Finally, third constraint lters out all relationships that their signi cance is below a certain threshold ( ). As a simple example satisfying all the above constraints and also capturing the relatedness among users, we can use an inverse of distance between users (nodes) in the social network (graph) as follows:
1 urf (ui; uj) = dist(ui;uj) where dist(ui; uj) is the number of edges in a shortest path connecting ui and uj.
User Weight. We quantify the overall (global)
importance of each user by the user weight function uwf (ui). This
measure quanti es the signi cance of a user in its social
network. For instance, for Twitter, a user with many followers
should be assigned a higher weight than a user with only
few followers, or for Facebook, a user with more friends is
more important to the social network than a user with fewer
friends. In the eld of graph theory and social networks this
value is called centrality and there exist several approaches
to measure it. Four popular methods to compute centrality
are: degree centrality, betweenness, closeness, and
eigenvector centrality. [
m 1 where deg(ui) is the number of edges incident upon ui and m is number of nodes (users).
User Action. The importance of each user for each object is directly related to the action(s)4 user perform on each object. Publishing/owning an object by a user shows a higher weight/relevance between the object and the user than only commenting on the object. For instance, a user uploading (and thus owning) a YouTube video is more signi cant to that video than a user who only comments on that video. The importance/relevance of each user to an object is measured by the user action function uaf (ui; ok) and is dependant on the type of action user ui performs on object ok. For each system, weight/signi cance of each action should be determined based on speci c characteristics of that system. We normalize the value of uaf by assigning values between 0 and 1 (inclusive) to it. The higher the value is, the more important/relevant is the user to the object. With some systems, there exist actions that can be performed multiple times by a user on an object, and the more the action is performed the higher is the relevance between the user and that object. For instance, in an online radio website (e.g. last.fm5), action listening to a track can be done multiple times by a user. The more the user chooses to listen to a track, the more relevant/signi cant is that track to the user. Below, we show examples of di erent actions and their corresponding weights for four popular web 2.0. objects. Note that the assigned weights are only our suggestion, they can (and should) be easily changed for di erent applications and/or settings. Examples are as follows:
YouTube videos: Actions = fown(publish) : 1; f avorite : 0:9; like : 0:7; comment : 0:4g.
Twitter tweets: Actions = ftweet(publish) : 1; f avorite : 0:9; retweet : 0:5g.
Facebook objects: Actions = fown(publish) : 1; like : 0:8; share : 0:6; comment : 0:4g. last.fm tracks (songs): Actions = flike : 0:8; tag : playcount 0:5; comment : 0:4; listen : max playcount g.
vi2Uo Note that for last.fm, we see an example of an action (listen) that can be performed multiple times (keep in mind that many other actions in our examples also can be performed multiple times). The above model can be applied to other object types for di erent web, web 2.0 and non-web objects. It is simple, exible and easy to update/change based on di erent applications and purposes. It shows and quanti es what users are important/relevant for each object and how much is this relevance/importance for each user/object.
Now, we propose the nal scoring function to calculate the social relevance between object o and query q as follows: socRel(o; q) = X urf (uq; vi) uaf (vi; o) uwf (vi) (2)
In Equation 2, uq is the user issuing the query and Uo is the set of users with some actions on the object o. While in classical textual relevance models such as tf-idf, more weight is given to the objects (documents) with 1) more number of 4for simplicity, we assume that each user can perform at most one action on each object. However, our model can easily be generalized for multiple actions per user. 5http://www.last.fm/ query keywords (tf), and 2) more important query keywords (idf), in our social relevance model, more weight is given to the objects with 1) more important actions 2) performed by more important users 3) whom are more related (closer) to the querying user. 4.1
In this section, we combine social relevance with an existing textual relevance model (tf-idf) to calculate the overall socio-textual relevance of the object o with query q with regards to both social and textual dimensions. Socio-textual relevance ranking considers both the textual relevance of the objects to the query and also the social relevance of the objects to the query. We formulate the socio-textual relevance ranking as follows: stRel(o; q) = socRel(o; q) + (1 ) texRel(o; q) = +
X urf (uq; vi) vi2Uo uaf (vi; o)
uwf (vi) (1 )
X tf (o; tj) idf (tj) tj2Kq (3) where stRel(o; q) is the socio-textual relevance of object o to query q where user uq is the query issuer; socRel and texRel are corresponding social and textual relevances for object o; urf , uaf and uwf are user-related functions as described above; Kq is set of query keywords (tags) and tjs are individual query keywords (tags); tf (o; tj) is term frequency function determining relevance of term tj to object o; idf (tj) is inverted document frequency function determining the importance of keyword tj in the entire collection; and is a parameter giving relative weights to social and textual importance. Not only the implementation of urf , uaf and uwf functions are exible (see Section 4), also the implementation of texRel is exible. Although, we used the conventional tf-idf model for capturing the textual relevancy, any other textual relevance (similarity) function can be also used. Equation 3 provides the general framework for calculating socio-textual relevance and implementation and/or importance of each weight can be changed based on the context and users/applications needs. 5.
In this section, we evaluate the e ectiveness of our proposed approaches. First, we describe the dataset, the settings and the queries used for the experiments. Next, we show and discuss the results.
Data. There are very few publicly available datasets for
experimentation that include both friendships (social
network) and textual keywords (tags). One very good dataset
is a dataset generated by [
Queries. For each query, we randomly chose 1 to 3 textual keywords (tags) from the list of all the tags in our dataset, and one random user from the list of all users with the minimum of 4 friends in the system. We ltered out queries that did not generate any results. Queries are performed in rounds. Each round consists of 100 queries and is conducted for each input setting.
Ground Truth. To evaluate our results, we have to compare them with a ranking that is the most relevant ranking to the user (ground truth). Since playcount indicates the real interest of each user to each track, we leverage playcount to construct the most relevant list (ranking) for each query as follows: for each query, we return list of all textually relevant tracks (tracks contain one or more of the query keywords), order them based on the querying user's playcount values and return the top k results.
Approaches. We computed top-k query results for each query using the following ve approaches: soc, text, sotext, socBinary and sotextBinary. soc approach generates the results based on the social relevance model only (presented in Section 4). text approach generates the results based on the conventional tf-idf relevance model only. sotext ap5.1
5.1.1
With the rst set of experiment, we evaluate the e ectiveness of the proposed approaches by varying number of requested results k. We report the average nDCG for each round. Here, we x the number of keywords at 1, alpha at 0.5 and the threshold value at 2. The value of k varies from 1 to 20. The results for three settings are shown in Figures 1(a), 1(b) and 1(c), respectively. The rst observation is that sotext is the most e ective approach among all the three settings. This is very promising since it shows that soc sotext sotextBinary soc sotext sotextBinary combining the textual relevance and social relevance using our model generates more relevant/accurate results in comparison with using only textual relevance or social relevance. The second observation is that sotext and soc are superior to their corresponding binary approaches (sotextBinary and socBinary). This implies that using a more detailed action model will improve the accuracy of the results. The third observation is that the results for our approaches are getting better from setting1 to setting2 and from setting2 to setting3. This shows that 1) social-related approaches are even better for more realistic settings, and 2) socially-related approaches generate more accurate results when users have more neighbors (more socially connected). 5.1.2
In the second set of our experiments, we evaluate the impact of changing the threshold value . For di erent rounds, we set the threshold value to 1,2,3 and 4. In this set of experiments, we x the number of query keywords at 1, k at 5 and alpha at 0.5. The results for three settings are shown in Figures 2(a), 2(b), and 2(c), respectively. Again, for all cases sotext easily outperforms the other four approaches. As expected, the accuracy increases for socially-related approaches as the threshold value increases (and obviously no change for text approach). Again, these gures con rm the observation that sotext and sotextBinary are superior than sotextBinary and socBinary approaches. 5.1.3
In the nal set of our experiments, we evaluate the impact of changing the value of alpha (relative weight of social and textual relevances) on the e ectiveness of the proposed approaches. We vary the value of alpha from 0 (social only) to 1 (textual only). In this set of experiments, we x the number of query keywords at 1, k at 5 and at 2. The results for all three settings are shown in Figures 3(a), 3(b), and 3(c), respectively. The obvious observation is that the results do not change for textual or social only approaches. The more interesting observation is the behavior of the two socio-textual approaches. While both show their poorest results on the boundaries (only social or only textual), they present their best accuracy in the middle of the range (when both textual and social relevance are considered almost equally). We have to note that for most cases, the best accuracy is achieved when the social relevance has a little more weight. Again, this set of experiments con rm the above observations regarding the superiority of sotext and also the improved accuracy of setting2 and setiing3.
In this paper, we introduced the problem of ranking web documents based on both their social and textual features. We proposed a new scoring model to calculate social relevance between documents and users. The proposed social relevance ranking utilizes the querying user's social network and actions her friends perform on web documents (objects) to generate more accurate results for her (textual) searches. We also showed how to combine the new social relevance with the textual relevance model. We performed a set of experiments on the real dataset of last.fm and proved that the new approach is superior to the existing approaches.