1 Introduction
Web surfers depend on search engines to locate information on the Web. For most queries, only the first screen of the results is viewed by the searcher [26], typically just the top 
results for a query. Since more traffic to a commercial web site may bring more profit, content providers usually want their web pages to be ranked as high as possible in the search engine results.
Some content providers increase the ranking of their pages by making high quality web pages. Others try to find a shortcut by manipulating web page features on which search engines′ ranking algorithms are based. This behavior is usually called ``search engine spam′′ [24,12]. Henzinger et al. [16] mention that search engine spam is one of the major challenges faced by search engines.
Many kinds of spam have been discovered [24,12,6], but there is no universal method that can detect all kinds of spam at the same time. Gyöngyi et al. [13] present the TrustRank algorithm to combat web spam. The basic idea of this algorithm is that a link between two pages on the Web signifies trust between them; i.e., a link from page A to page B is a conveyance of trust from page A to page B. Initially, human experts select a list of seed sites that are well-known and trustworthy on the Web. Each of these seed sites is assigned an initial trust score. A biased PageRank algorithm is then used to propagate these trust scores to their descendants. After convergence, good sites will have relatively high trust scores, while spam sites will have poor trust scores. 数据挖掘研究院
TrustRank may suffer from the fact that the coverage of the seed set used may not be broad enough. Many different topics exist on the Web and there are good pages within each topic. The seed selection process used in the TrustRank algorithm cannot guarantee that most of these topics are covered. So, it is possible that in using TrustRank to detect spam, we may get good precision but suffer from unsatisfactory recall. 数据挖掘实验室
We will show that TrustRank has a bias towards communities that are heavily represented in the seed set. For example, if more sports pages exist in the seed set than pages related to image processing, then pages related to sports have a better chance of gaining higher trust scores than the pages related to image processing. So, if a spam page successfully fools some pages in the sports community to link to it, it is possible that it may be ranked higher than some good pages in the image processing community.
In order to address the above issues, we propose to introduce topical information into the trust propagation system. For the coverage issue, we propose the use of the pages listed in well-maintained topic directories, such as the dmoz Open Directory Project [21]. For the bias issue, we propose that the trustworthiness of a page should be differentiated by different topics; i.e., the page should be more trusted in the topics that it is relevant to. This relies on the fact that a link between two pages is usually created in a topic-specific context [4].
Our approach, called Topical TrustRank, partitions the set of trusted seed pages into topically coherent groups and then calculates TrustRank for each topic. The final ranking is based on a balanced combination of these individual topic-specific trust scores.
Bigger communities on the web are generally better represented in topic directories. Since TrustRank has a bias towards heavily represented communities and intuitively bigger communities usually attract more spam pages, we want to show that on average, Topical TrustRank can demote spam pages more than TrustRank do. So, we will focus on the performance of spam pages demotion in this paper. 数据挖掘研究院
In this paper we make a number of contributions. First, we show that TrustRank has a bias toward larger communities. Second, we demonstrate that the combination of multiple TrustRanks based on random partitions can produce highly variable results. Third, we propose the use of topicality to determine appropriate partitions. Finally, we show that Topical TrustRank performs significantly better in demoting spam sites, especially highly ranked spam sites, than TrustRank. Compared to TrustRank, our best technique can decrease spam by 43.1% from the top ranked sites by PageRank. Our algorithm uses only the link graph and seed sets from different topics; there is no need for the content of pages or the use of a text classifier. This makes the whole process viable for more than just commercial search engines. 数据挖掘研究院
The rest of this paper is organized as follows: the background and related work are introduced in Section 2 and Section 3, respectively. The motivation of this work is introduced in Section 4. The details of Topical TrustRank are given in Section 5. The experiments and results are shown in Section 6. We finish with discussion and conclusion in Sections 7 and 8. 数据挖掘研究院
2 Background
Gyöngyi et al. [13] introduce TrustRank. It is based on the idea that good sites seldom point to spam sites and people trust these good sites. This trust can be propagated through the link structure on the Web. So, a list of highly trustworthy sites are selected to form the seed set and each of these sites is assigned a non-zero initial trust score, while all the other sites on the Web have initial values of 0. Then a biased PageRank algorithm is used to propagate these initial trust scores to their outgoing sites. After convergence, good sites will get a decent trust score, while spam sites are likely to get lower trust scores. The formula of TrustRank is:
数据挖掘研究院 
where
is the TrustRank score vector, 
is the decay factor, 
is the transition matrix (in which 
is the probability of following the link from page 
to page 
) and 
is the normalized trust score vector for the seed set. Before calculation, is initialized with the value of . Gyöngyi et al. iterated the above equation 20 times with set to 0.85.
As Gyöngyi et al. have pointed out, seed set selection is crucial to the success of the TrustRank algorithm, and so they applied an extremely rigorous process for selecting 
sites from a crawl of pages from 31M sites as the final seed set. For each site, they calculated its PageRank and TrustRank values based on the site graph. They first put all the sites into 
buckets based on the PageRank value and then made the buckets for TrustRank with equal size as the corresponding PageRank bucket. A random sample of 
sites was selected from each bucket and they manually checked if the site was utilizing spam. The results showed that TrustRank improves upon PageRank by keeping good sites in top buckets, while most spam sites are moved to lower buckets. 数据挖掘研究院
3 Related Work
Henzinger et al. [16] mentioned that search engine spam is quite prevalent and search engine results would suffer greatly without measures to combat it. A number of researchers have worked to combat different kinds of web spam, and we list just a few of them here. Fetterly et al. propose using statistical analysis to detect spam [9]. Benczur et al. propose SpamRank [2] in which for each page, the PageRank distribution of all incoming links is checked. If the distribution doesn′t follow a typical pattern, the page will be penalized. Acharya et al. [1] first publicly proposed using historical data to identify link spam pages. Wu and Davison [28] used the intersection of the incoming and outgoing link sets plus a propagation step to detect link farms. Mishne et al. [20] employed a language model to detect comment spam. Drost and Scheffer [8] proposed using a machine learning method to detect link spam. Recently, Fetterly et al. [10] describe methods to detect a special kind of spam that provides pages by stitching together sentences from a repository.While the idea of a focused or custom PageRank vector has existed from the beginning [23], Haveliwala [14] was the first to propose the idea of bringing topical information into PageRank calculation. In his technique, pages listed in the dmoz ODP are used to calculate the biased PageRank values for each of the top categories. Then a similarity value of a query to each of these categories is calculated. A unified score is then calculated for each page containing the given query term(s). Finally, pages are ranked by this unified score. Experiments show that Topic-sensitive PageRank has better performance than PageRank in generating better response lists to a given query. 数据挖掘研究院
Jeh and Widom [19] specialize the global notion of importance that PageRank provides to create personalized views of importance by introducing the idea of preference sets. The rankings of results can then be biased according to this personalized notion. For this, they used the biased PageRank formula. 数据挖掘研究院
Chakrabarti et al. [3] characterized linking behaviors on the Web using topical classification. Using a classifier trained on ODP topics, they generated a topic-topic citation matrix of links between pages that showed a clear dominant diagonal, which meant that pages were more likely to point to pages sharing their topic. 数据挖掘研究院
Recently, Chirita et al. [5] described the method of combining ODP data with search engine results to generate a personalized search result. Based on a predefined user profile, the distance of this file to each URL received from a search engine′s response list is calculated and these URLs are resorted to generate a new output for the user. Our approach makes similar use of human-edited directories, but our goal is to demote spam. 数据挖掘研究院
Guha et al. [11] study how to propagate trust scores among a connected network of people. Different propagation schemes for both trust score and distrust score are studied based on a network from a real social community website.
4 Motivation
Seed set selection is the most important component of the TrustRank algorithm. Different seed selections lead to different results.
The seed selection process employed by the authors of TrustRank may not guarantee a broad coverage of the Web. A natural way to provide broader coverage is by the use of topical information. Human-generated topic directories like the Yahoo! directory and the dmoz Open Directory Project are valuable resources for providing broader seed sets.
Instead of using a single TrustRank score for a site, we propose to calculate TrustRank scores for different topics, with each score representing the trustworthiness of the site within that particular topic. We believe a combination of these scores will present a better measure of the trustworthiness of a site. 数据挖掘研究院
To achieve this, we can partition the seed set on the basis of topic.
Suppose we have a seed set . It can be partitioned into 
subsets, 
, 
, ..., 
, each containing 
( 
) seeds. We use to represent the TrustRank scores calculated by using as the seed set and use 
( ) to represent the TrustRank scores calculated by using 
as the seed set. The following equation is a version of the Linearity theorem proved by Jeh and Widom [19]: 数据挖掘研究院
The above equation shows that the product of TrustRank score and the total number of seeds equals the sum of products of the individual partition-specific scores and the number of seeds in that partition.
A transformation of this equation is:
From the above equation, we observe that larger partitions contribute more to the TrustRank values. 数据挖掘研究院
If the seed set used by TrustRank has a heavily represented topic community then clearly, TrustRank will present a bias towards pages in this community. 数据挖掘研究院
Usually bigger communities are also communities with popular topics. Spammers also have greater interest to spam popular topic pages. Today, spammers are becoming more and more sophisticated and it is not that hard for them to fool some good/seed pages to point to the spam pages. For example, spammers may copy good content from various well-maintained sites but put invisible spam content and/or add advertisements to the pages. Sometimes it is not easy for a non-expert to identify these spam pages. So, it is quite possible that bigger communities will contain more spam pages. An evidence is that Wu and Davison [27] found that pages within a response data set for popular queries utilize cloaking behavior more than twice as often as pages within a response data set for normal queries. 数据挖掘研究院
Hence, the TrustRank bias may inadvertently help spammers that manage to fool pages from a larger community to link to them. And so, we investigate techniques to balance out this bias.
5 Topical TrustRank
As mentioned in Section 1, topical coverage of the seed set may be insufficient for the web with so many topics in existence. Also, we have shown in Section 4 that TrustRank has a bias towards heavily represented communities in the seed set. In order to address these issues, we introduce topical information into the trust propagation system. For the coverage issue, we propose the use of the pages listed in well-maintained topic directories, such as the dmoz Open Directory Project [21]. For the bias issue, we propose that the trustworthiness of a page should be differentiated by different topics, relying on the fact that two linked pages are typically on related topics [4,7].
Our Topical TrustRank approach partitions the set of trusted seed pages into topically coherent groups and then calculates TrustRank for each topic. The final ranking is based on a balanced combination of these individual topic-specific trust scores. 数据挖掘研究院
5.1 Seed set partitioning
For a given seed set, we cut it into different partitions corresponding to different topics.Using each of these partitions as a seed set, we calculate the trust scores for every node in the web graph using the TrustRank algorithm. 数据挖掘实验室
For a simple example, Figure 1 shows a small network that contains 
nodes. Among these nodes, 1,2, and 8 are seed nodes. Suppose node 
is related to one topic, 
, while node 
and are related to another topic, 
. Clearly, is better represented in the seed set. We partition the seed set by topic. The result of the trust scores generated using the two seed sets are shown in columns and of Table 1 respectively.
|
5.2 Combination of different topic scores
In order to present a single measure of trust for a page (Topical TrustRank score) using this approach, we explore two techniques of combining the generated topical trust scores, namely, simple summation and quality bias. 数据挖掘实验室
5.2.1 Simple summation
In this technique, individual topical trust scores are added up to generate the Topical TrustRank score.For the example presented in Figure 1, the simple summation of the topics are shown in the 
column in Table 1. We will refer to these scores as the Topical TrustRank scores of the pages. Also, the scores generated by running TrustRank using the whole seed set is shown in the column.
We see that for both algorithms, seed nodes , , and have high scores. In Topical TrustRank, seed from the smaller community has a higher Topical TrustRank score than seeds , from the bigger community while in TrustRank all of them have equal values. This is because a simple summation of scores implies an equal treatment of communities and as seed node belongs to a smaller community, it ends up with a higher trust score than seed nodes and . For the same reason, the difference between the scores of nodes 
and 
from node 
is reduced by Topical TrustRank.
Let us consider an example where node is a spam page. TrustRank ranks node higher than node 
, which is only one step away from the seed node . We believe that node which is only one step away from the seed set has a lower probability of being a spam site than node which is two steps away from the seed set, i.e., the confidence in the nature of a page decreases as the number of the steps from the seed set increases. 数据挖掘研究院
5.2.2 Quality bias
In this technique, we introduce a ``quality′′ bias in the combination of individual topical trust scores. We propose to weight each of the individual topical trust scores by a bias factor
for topic , hence placing a greater importance on topical trust scores obtained for some communities than others. A possible bias is the average PageRank value obtained by averaging over the PageRank values of the seed pages of the particular community. Hence, the higher the PageRank values of the seed pages of the particular community, the more we trust the score assigned by the algorithm for that community.
5.3 Improvements
We propose the following improvements to the basic Topical TrustRank algorithm. These improvements are related to seed selection. 数据挖掘研究院
5.3.1 Seed weighting
In the TrustRank algorithm, each seed node is assigned an equal value in the initial vector in Equation 1. For each seed page, this value represents that how likely that a surfer will jump to this seed page if the surfer decides not to follow any outgoing links. We study the behavior of the TrustRank and Topical TrustRank algorithms by varying this initial value. Instead of assigning a constant value for each seed node, we assign to each node a value proportional to its importance or quality. In effect we are saying that some seed pages′ trust is more important than that of some other seed pages. Thus, a surfer is more likely to jump to a better trusted seed page. We make use of the normalized PageRank value of each seed node within the seed set as the seed node′s initial value. 数据挖掘研究院
5.3.2 Seed filtering
Low quality pages may exist within the pool of seed pages obtained from topic directories (more specifically, open topic directories). Even spam pages may exist within this pool.
In the latter case, the human editors may not be experts at detecting spam or may still include the page despite its spam nature for its content value. In addition, an expired domain present in the seed set may have been taken by a spammer. 数据挖掘研究院
To alleviate these situations, we employ some techniques of seed filtering. By filtering out low quality pages from the seed set, we expect to improve the performance of the Topical TrustRank algorithm. For the measure of quality of seed pages, we may use their PageRank or their Topical TrustRank scores.
5.3.3 Finer topics hierarchy
Topic directories usually provide a tree structure for each topic. Most existing papers use only the top level topics because calculation is expensive when finer topics are involved.Intuitively, a finer topic hierarchy may be more accurate to categorize pages on the Web. 数据挖掘研究院
For Topical TrustRank, the benefit of introducing finer topics is in producing better partitions. For example, a page may be a good page for sports, but since there are many different kinds of sporting activities this page may not cover all of them. It may make more sense to say that this page is trustworthy for one sport, say tennis, but not some other such as skiing. 数据挖掘研究院
Since we have a reasonably sized data set (the search.ch data set) with finer topics available, which will be introduced below in Section 6.1, we also test the use of finer topics and measure the performance. 数据挖掘研究院
6 Experiments
6.1 Data sets
We used two data sets to evaluate our proposed Topical TrustRank algorithm.
The first data set is a general web crawl from Stanford′s WebBase project [17]. We used the data set for January, 2001 as this data set has been used by several other researchers (e.g., [14,15,19]). We downloaded the link graph, and made use of the Internet Archive [18] to check page content when necessary. The link graph contained about 65M pages that had a viable URL string. We also downloaded the ODP RDF file of January 22, 2001 from dmoz.org [21] for seed page selection.
The second data set is a country-specific web crawl courtesy of search.ch, the Swiss search engine [25]. Since the company also provided us labeled sites and domains employing various spam behavior, we used the site graph for analysis. There are approximately 20M pages within this data set and around 350K sites with the Switzerland country code (.ch). The company also provided us a list of sites or domains which applied various spamming techniques (3,589 sites). We used these sites as the labeled data set for our testing. 数据挖掘实验室
We also used an existing topic directory [25] with 20 different topics, similar to the ODP but which only listed pages primarily within the Switzerland domain. Since we used the site graph in our calculation and the topic directory listed only pages, we used a simple transfer policy: if a site had a page listed in a certain topic directory, we marked the site to be of the same topic. In doing so, we marked 22,000 sites as seeds partitioned by these 20 topics. We found the number of unique sites to be 20,005, as a number of sites were included within several topics.
6.2 Bias of TrustRank
As shown earlier, TrustRank has a bias towards communities with more seeds in the seed set. We verify this behavior of TrustRank experimentally. We applied TrustRank and Topical TrustRank algorithms on the WebBase data.First, we select the top 50 pages based on TrustRank scores, then we decompose their TrustRank scores into the component topical trust scores according to Equation 3 as illustrated in Figure 2. We can see topics, such as ``Reference′′, ``Regional′′ and ``Games′′ dominate the top rankings. These topics are also the most heavily represented ones in the seed set, verifying the bias of TrustRank towards heavily represented communities. 数据挖掘研究院
Similarly, we select the top pages based on the Topical TrustRank score (simple summation) and illustrate the decomposition of these scores into the component topical trust scores in Figure 3. We can see that the dominance of topics such as ``Reference′′, ``Regional′′ and ``Games′′ is reduced with other topics contributing more to the total topical trust score of the page, presenting a more balanced version of combining these individual topical trust scores.
6.3 Results for search.ch data
This section describes the results generated for the Swiss data set provided by search.ch. 数据挖掘研究院
6.3.1 Basic results
Following the same methods described in the TrustRank paper [13], we first calculated the PageRank value on the search.ch site graph. Then, we put these sites into buckets, each bucket containing the sites with the sum of PageRank values equal to 
of the sum of all PageRank values. 数据挖掘研究院
Then we used the 
seed sites from the search.ch topic directory as the single seed list to calculate the TrustRank score for each site. After that, we also put each site into one of the buckets. The criterion for this placement is that each bucket for TrustRank has identical number of sites as the corresponding PageRank bucket.
For Topical TrustRank, we used the seed set for each of the topics to calculate topical trust scores for each site. After this calculation, each site had a vector of topical trust scores, each of which represented how trustworthy this site was within this topic community. To generate the Topical TrustRank score, we apply the simple summation technique. The sites are then ranked by their Topical TrustRank scores. As in the case of TrustRank, we place these sites into one of the buckets. Again, the criterion is that each Topical TrustRank bucket has an identical number of sites as the corresponding PageRank bucket. 数据挖掘研究院
We measured the performance of each ranking algorithm. Considering spam sites within top buckets to be more harmful, we use the number of spam sites within the top buckets as our first metric to measure the performance of an algorithm. Our second metric is the overall movement of these spam sites. It is defined as the sum of the differences in bucket positions of labeled spam sites between the tested ranking algorithm and the PageRank algorithm. The bigger this number, the better the performance of the ranking algorithm in demoting spam sites.
The results obtained for the algorithms are summarized in Table 2(a). There are 
spam sites in the top ten buckets by PageRank. TrustRank moves 
of these spam sites out of the top ten buckets leaving 
. Topical TrustRank moves 
spam sites out of the top ten buckets retaining only 
. The distribution of the spam sites within the top ten buckets for these three algorithms are shown in Figure 4. 数据挖掘研究院
In terms of overall movement, TrustRank has an overall movement of 
while Topical TrustRank has an overall movement of 
. The results shown in the Table 2(a) will used as the baseline for further comparisons. 数据挖掘研究院
