Link Analysis, Eigenvectors and Stability

1 Introduction

Recent years have seen growing interest in algorithms for identifying "authoritative" or "influential" articles from webpage hyperlink structures or from other citation data. In particular, the HITS algorithm of Kleinberg [1998] and Google's PageRank algorithm [Brin and Page, 1998] have attracted the attention of many researchers (see also [Osareh, 1996] for earlier developments in the bibliometrics literature). Both of these algorithms use eigenvector calculations to assign "authority" weights to articles, and while originally designed in the context of link analysis on the web, both algorithms can be readily applied to citation patterns in academic papers and other citation graphs.

There are several aspects to the evaluation of a link analysis algorithm such as HITS or PageRank. One aspect relates to the specific notion of "authoritativeness" embodied by an algorithm. Thus specific users may have an understanding of what constitutes an authoritative web page or document in a given domain, and the output of HITS or PageRank can be evaluated by such users. While useful, such analyses often have a rather subjective flavor. A more objective criterionthe focus of the current paper-concerns the stability of a link analysis algorithm. Does an algorithm return similar results upon a small perturbation of the link structure or the document collection? We view stability as a desirable feature of a link analysis algorithm, above and beyond the particular notion of authoritativeness that the algorithm embodies. If an Michael I. Jordan CS Div. & Dept. of Statistics U.C. Berkeley Berkeley, CA 94720

article is truly authoritative or influential, then surely the addition of a few links or a few citations should not make us change our minds about these sites or articles having been very influential. Moreover, even in the context of a fixed link structure, a dynamic, unreliable infrastructure such as the web may give us different views of the structure on different occasions. Ideally, a link analysis algorithm should be insensitive to such perturbations.

In this paper, we use techniques from matrix perturbation theory and coupled Markov chain theory to characterize the stability of the ranks assigned by HITS and PageRank. Some ways of improving the stability of HITS are also briefly metioned; these algorithmic changes are studied in more detail in [Ng et al., 2001].

2 An Example

Let us begin with an empirical example. The Cora database [McCallum et al., 2000] is a collection containing the citation information from several thousand papers in AI.

We ran the HITS and PageRank algorithms on the subset of the Cora database consisting of all its Machine Learning papers. To evaluate the stability of the two algorithms, we also constructed a set of five perturbed databases in which 30% of the papers from the base set were randomly deleted. ("Since Cora obtained its database via a web crawl, what if, by chance or mishap, it had instead retrieved only 70% of these papers?") If a paper is truly authoritative, we might hope that it would be possible to identify it as such with only a subset of the base set.

The results from HITS are shown in the following table. In this table, the first column reports the rank from HITS on the full set of Machine Learning papers, whereas the five rightmost columns report the ranks in runs on the perturbed databases. We see substantial variation across the different runs:

Although it might be thought that this variability is intrinsic to the problem, this is not the case, as shown by the results from the PageRank algorithm, which were much more stable:

These results are discussed in more detail in Section 6. It should be stated at the outset, however, that our conclusion is not that HITS is unstable while PageRank is not. The issue is more subtle than that, involving considerations such as the relationships between multiple eigenvectors and invariant subspaces. We do wish to suggest, however, that stability is indeed an issue that needs attention. We now turn to a brief description of HITS and PageRank, followed by our analysis.

3 Overview of HITS and PageRank

Given a collection of web pages or academic papers linking to/citing each other, the HITS and PageRank algorithms each (implicitly) construct a matrix capturing the citation patterns, and determines authorities by computing the principal eigenvector of the matrix. 1

3.1 HITS algorithm

The HITS algorithm [Kleinberg, 1998] posits that an article has high "authority" weight if it is linked to by many pages with high "hub" weight, and that a page has high hub weight if it links to many authoritative pages. More precisely, given a set of D2 web pages (say, retrieved in response to a search query), the HITS algorithm first forms the D2-by-D2 adjacency matrix BT, whose B4CXBN CYB5-element is 1 if page CX links to page CY, and 0 otherwise. 2 It then iterates the following equations:

1 It is worth noting that HITS is typically described as running on a small collection of articles (say retrieved in response to a query), while PageRank is described in terms of the entire web. Either algorithm can be run in either setting, however, and this distinction plays no role in our analysis.

2 Kleinberg [1998] discusses several other heuristics regarding issues such as intra-domain references, which are ignored in this section for simplicity (but are used in our experiments). See also Bharat and Henzinger [1998] for other improvements to HITS. It should be noted that none of these fundamentally change the spirit of the eigenvector calculations underlying HITS.

-

-

-

-

(where "CX AX CY" means page CX links to page CY) to obtain the fixed-points CP A3 BP D0CXD1 D8AXBD CP B4D8B5 and CW A3 BP D0CXD1 D8AXBD CW B4D8B5 (with the vectors renormalized to unit length). The above equations can also be written:

When the iterations are initialized with the vector of ones CJBDBN BM BM BM BN BDCL CC , this is the power method of obtaining the principal eigenvector of a matrix [Golub and Van Loan, 1996], and so (under mild conditions) CP A3 and CW A3 are the principal eigenvectors of BT CC BT and BTBT CC respectively. The "authoritativeness" of page CX is then taken to be CP A3 CX , and likewise for hubs and CW A3 .

3.2 PageRank algorithm

Given a set of D2 web pages and the adjacency matrix BT (defined previously), PageRank [Brin and Page, 1998] first constructs a probability transition matrix  by renormalizing each row of BT to sum to BD. One then imagines a random web surfer who at each time step is at some web page, and decides which page to visit on the next step as follows: with probability BDA0AF, she randomly picks one of the hyperlinks on the current page, and jumps to the page it links to; with probability AF, she "resets" by jumping to a web page picked uniformly and at random from the collection. 3 Here, AF is a parameter, typically set to 0.1-0.2. This process defines a Markov chain on the web pages, with transition matrix AFCD B7 B4BD A0 AFB5, where CD is the transition matrix of uniform transition probabilities (CD CXCY BP BDBPD2 for all CXBN CY). The vector of PageRank scores D4 is then defined to be the stationary distribution of this Markov chain. Equivalently, D4 is the principal eigenvector of the transition matrix B4AFCD B7 B4BD A0 AFB5B5 CC (see, e.g. Golub and Van Loan, 1996), since by definition the stationary distribution satisfies

The asymptotic chance of visiting page CX, that is, D4 CX , is then taken to be the "quality" or authoritativeness of page CX.

4 Analysis of Algorithms

We begin with a simple example showing how a small addition to a collection of web pages can result in a large change to the eigenvectors returned. Suppose we have a collection of web pages that contains 100 web pages linking to http://www.algore.com, and another 103 web pages linking to http://www.georgewbush.com. The adjacency matrix BT has all zeros except for the two columns corresponding to these two web pages, therefore the principal eigenvector CP A3 will have non-zero values only for algore.com and georgewbush.com. Figure 1(a) presents a jittered scatterplot of links to these two web pages, along with the first two eigenvectors. (Only the non-zero portions of the eigenvectors are shown.) Now, suppose five new web pages trickle into our collection, which happen to link to both algore.com and georgewbush.com. Figure 1(b) shows the new plot, and we see that the eigenvectors have changed dramatically, with the principal eigenvector now near the BGBH Æ line. Thus, a relatively small perturbation to our collection has caused a large change to the eigenvectors. 4 If this phenomenon is pervasive, then it needs to be addressed by any algorithm that uses eigenvectors to determine authority. In the next two sections, we give characterizations of whether and when algorithms can be expected to suffer from these problems.

3 There are various ways to treat the case of pages with no outlinks (leaf nodes). In this paper we utilize a particularly simple approach-upon reaching such a page, the web surfer picks the next page uniformly at random. This means that if a row of BT has all zero entries, then the corresponding row of  is constructed to have all entries equal to BDBPD2. The PageRank algorithm described in [Page et al., 1998] utilizes a different reset distribution upon arriving at a leaf node. It is possible to show, however, that every instantiation of our variant of the algorithm is equivalent to an instantiation of the original algorithm on the same graph with a different value of the reset probability.

4.1 Analysis of HITS

HITS uses the principal eigenvector of CB BP BT CC BT to determine authorities. In this section, we show that the stability of this eigenvector under small perturbations is determined by the eigengap of CB, which is defined to be the difference between the largest and the second largest eigenvalues.

Here is an example that may shed light on the importance of the eigengap. Figure 2 plots the contours associated with two matrices CB BD and CB BE before (with solid lines) and after (with dashed lines) the same additive perturbation have been made to them. 5 The eigenvalues of the matrices are indicated by the directions of the principal axes of the ellipses. The matrix CB BD shown in Figure 2a has eigengap Æ BD AP BC, and a small perturbation to CB BD (and hence the ellipse) results in eigenvectors BGBH Æ away from the original eigenvectors; the matrix CB BE shown in Figure 2b has eigengap Æ BE BP BE, and the perturbed eigenvectors are nearly the same as the original eigenvectors. So, we see how, in this example, the size of the eigengap directly affects the stability of the eigenvectors. (Readers familiar with plots of multivariate Gaussians can also think of these as the contours of a Gaussian with small perturbations imposed on the (inverse) covariance matrix.)

4 There is nothing special about the number 5 here; a smaller number also results in relatively large swings of the eigenvectors. Replacing 5 with 1, 2, 3, and 4 causes the principal eigenvector to lie at 73, 63, 58 and 55 degrees, respectively.

5 More precisely, these are contours of the quadratic form DC CC CB CX DC.

Figure 2: Contours of two matrices with different eigengaps.

In the sequel, we use a tilde to denote perturbed quantities. (For instance, DI CB denotes a perturbed version of CB.) We now give our first, positive result, that so long as the eigengap Æ is large, then HITS is insensitive to small perturbations. 6

Theorem 1. Let CB BP BT CC BT be given. Let CP A3 be the principal eigenvector and Æ the eigengap of CB. Assume the maximum out-degree of every web page is bounded by CS. For any AY BQ BC, suppose we perturb the web/citation graph by adding or deleting at most CZ links from one page, where CZ BO B4 D4 CS B7 AB A0 D4 CSB5 BE , where AB BP AYÆBPB4BG B7 D4 BEAYB5. Then the perturbed principal eigenvector DI CP A3 of the perturbed matrix DI CB satisfies:

So, if the eigengap is big, HITS will be insensitive to small perturbations. This result is proved by showing i) the direction of the principal eigenvector does not change too much, and ii) the magnitudes of the relevant eigenvalues do not change too much, so the second eigenvector does not "overtake" the first and become the new principal eigenvector.

Proof. Let CYCY A1 CYCY BY denote the Frobenius norm. 7 We apply Theorem V.2.8 from matrix perturbation theory [Stewart and Sun, 1990]: Suppose CB BE CA D2A2D2 is a symmetric matrix with principal eigenvalue AL A3 and eigenvector CP A3 , and eigengap Æ BQ BC. Let BX be a symmetric perturbation to CB. Then the following inequalities hold for the old principal eigenpair B4AL A3 BN CP A3 B5 and some new eigenpair ( DI ALBN DI CPB5.

(assuming that the denominator in (3) is positive). Let the complementary eigenspace to B4AL A3 BN CP A3 B5 be represented by B4 BE BNCG BE B5, i.e. CG BE is orthonormal, and its columns contain all the eigenvectors of CB except CP A3 ;  BE is diagonal and contains the corresponding eigenvalues, all of which are at least Æ less than AL A3 ; and CBCG BE BP CG BE  BE . A bound similar to Equation (4) holds for  BE :

6 Our analyses also apply directly to hub-weight calculations, simply by reversing link directions and interchanging BT and BT CC .

7 The Frobenius norm is defined by CYCYCGCYCY BY BP B4  CX  CY B4CG CXCY B5 BE B5 BDBPBE .

Let DI AL BE be the largest eigenvalue of DI  BE . Using Corollary IV.3.6 from Stewart and Sun [1990], one can show that Equation (5) implies

If in turn D4 BECYCYBXCYCY BY BO ÆBPBE, then Equations (4) and (6) together will ensure that DI AL BQ DI AL BE , i.e. B4 DI ALBN DI CPB5 is the principal eigenpair of DI CB.

Since we are adding or deleting links from only one page, let BY denote the perturbation to one row of BT, so that DI CB BP B4BTB7BYB5 CC B4BTB7BYB5. It is straightforward to show CYCYBY CC BYCYCY BY AK CZ and CYCYBT CC BY CYCY BY BP CYCYBY CC BTCYCY BY AK D4 CSCZ. We can thus bound the norm of the perturbation to CB:

Using Equations (3) and (7) to determine when we may guarantee Equation (2) to hold, we arrive at the bound CZ BO B4 D4 CS B7 AB A0 D4 CSB5 BE , where AB BP AYÆBPB4BG B7 D4 BEAYB5. One can easily verify that the same bound on CZ also ensures D4 BECYCYBXCYCY BY BO ÆBPBE (which also guarantees that the denominator in (3) is positive), hence DI CP A3 BP DI CP as previously stated.

Next we give the converse of this result, that if the eigengap is small, then eigenvectors can be sensitive to perturbations.

Theorem 2. Suppose CB is a symmetric matrix with eigengap Æ. Then there exists a B4ÆB5 perturbation 8 to CB that causes a large (AAB4BDB5) change in the principal eigenvector.

Proof. Since CB BP CB CC , it can be diagonalized:

where CD is orthogonal, and whose columns are the CB's eigenvectors. Let D9 CX denote the CX-th column of CD. We pick DI CB BP CB B7 BEÆD9 BE D9 CC BE . Since CYCYD9 BE CYCY BE BP BD, the norm of the perturbation is only CYCYBEÆD9 BE D9 CC BE CYCY BY BP BEÆ. Moreover,

As DI AL BE BP AL BE B7 BEÆ BQ AL BD , B4 DI AL BE BN D9 BE B5 is the new principal eigenpair. But D9 BE is orthogonal to D9 BD , so CYCYD9 BE A0 D9 BD CYCY BE BP AAB4BDB5.

To ground these results and illustrate why Theorem 1 requires a bound CS on out-degrees, we give another example of where a small perturbation-adding a single link-can have a large effect. In this example we use the fact that if a graph has multiple connected components, then the principal eigenvalue will have non-zero entries in nodes only from the "largest"

8 More formally, there exists a perturbed version of CB, denoted DI CB, so that CYCYCB A0 DI CBCYCY BY BP B4ÆB5.

20 Nodes

20 Nodes

Figure 3: Picture of a web community.

connected component (more formally the component with the largest eigenvalue). 9

Consider the web/citation-graph shown in Figure 3, which we imagine to be a small subset of a much larger graph. Solid arrows denote the original set of hyperlinks; the dashed arrow represents the link we will add. The original principal eigenvalue for each of the two connected components shown is AL BP BEBC; with the addition of a single link, it is easy to verify that this jumps to DI AL BP BEBH. Suppose that the community shown is part of a larger web/citation graph with multiple subcommunities, and that originally the biggest subcommunity had eigenvalue BEBC BO AL BD BO BEBH. By adding one link, the graph shown in Figure 3 becomes the biggest subcommunity, and the principal eigenvector now has positive values only for nodes shown in this figure, and zeros elsewhere.

4.2 Analysis of PageRank

We now analyze the sensitivity of PageRank's authority scores D4 to perturbations of the web/citation-graph.

Theorem 3. Let  be given, and let D4 be the principal right eigenvector of B4AFCD B7 B4BD A0 AFB5B5 CC . Let articles/pages CX BD BN CX BE BN BM BM BM BN CX CZ be changed in any way, and DI  be the corresponding (new) transition matrix. Then the new PageRank scores DI D4 satisfies:

Thus, assuming AF is not too close to 0, this shows that so long as the perturbed/modified web pages did not have high overall PageRank scores (as measured with respect to the unperturbed PageRank scores D4), then the perturbed PageRank scores DI D4 will not be far from the original.

Proof. We construct a coupled Markov chain CUB4CG D8 BN CH D8 B5 BM D8 AL BCCV over pairs of web pages/documents as follows. CG BC BP CH BC is drawn according to the probability vector D4, that is, from the stationary distribution of the PageRank "random surfer" model. The state transitions work as follows: On step D8, we decide with probability AF to "reset" both chains, in which case we set CG D8 and CH D8 to the same page chosen uniformly at random from the collection. If no "reset" occurs, and if CG D8A0BD BP CH D8A0BD and CG D8A0BD is one of the unperturbed pages, then CG D8 BP CH D8 is chosen to be a random page linked to by the page CG D8A0BD . In all other cases, CG D8 is chosen to be a random page linked to by page CG D8A0BD , and independently of it, CH D8 is chosen to be a random page linked to by page CH D8A0BD .

9 See, e.g. Chung [1994]. A connected component of a graph is a subset whose elements are connected via length AL BD paths to each other, but not to the rest of the graph. The eigenvalue of a connected component BV is the largest eigenvalue of BT CC BV BT BV (cf. BT CC BT used by HITS), where BT BV , a submatrix of BT, is the adjacency matrix of BV.

Thus, we now have two "coupled" Markov chains CG D8 and CH D8 , the former using the transition probabilities B4AFCD B7 B4BD A0 AFB5B5 CC , and latter B4AFCD B7 B4BD A0 AFB5 DI B5 CC , but so that their transitions are "correlated." For instance, the "resets" to both chains always occur in lock-step. But since each chain is following its own state transition distribution, the asymptotic distributions of CG D8 and CH D8 must respectively be D4 and DI D4. Now, let CS D8 BP B4CG D8 BIBP CH D8 B5. Note CS BC BP BC, since CG BC BP CH BC always. Letting  denote the set of perturbed pages, we have:

where to derive the first inequality, we used the fact that by construction, the event "CG D8B7BD BIBP CH D8B7BD BNCG D8 BP CH D8 " is possible only if CG D8 is one of the perturbed pages. Using the fact that CS BC BP BC and by iterating this bound on CS D8B7BD in terms of CS D8 , we obtain an asymptotic upper-bound: CS BD AK B4  CXBE D4 CX B5BPAF. Thus, if B4CG BD BN CH BD B5 is drawn from the stationary distribution of the correlated chains-so the marginal distributions of CG BD and CH BD are respectively given by D4 and DI D4-then B4CG BD BIBP CH BD B5 BP CS BD AK B4  CXBE D4 CX B5BPAF. But if two random variables have only a small CS BD chance of taking different values, then their distributions must be similar. More precisely, by the Coupling Lemma (e.g., see Aldous, 1983) the variational distance B4BDBPBEB5  CX CYD4 CX A0 DI D4 CX CY between the distributions must also be bounded by the same quantity CS BD . This shows CYCYD4 A0 DI D4CYCY BD AK BECS BD , which concludes the proof.

5 LSI and HITS

In this section we present an interesting connection between HITS and Latent Semantic Indexing [Deerwester et al., 1990] (LSI) that provides additional insight into our stability results (see also Cohn and Chang, 2000). In LSI a collection of documents is represented as a matrix BT, where BT CXCY is 1 if document CY contains the CX-th word of the vocabulary, and 0 otherwise. LSI computes the left and right singular vectors of BT (equivalently, the eigenvectors of BTBT CC and BT CC BT). For example, the principal left singular vector, which we denote DC, has dimension equal to the vocabulary size, and DC CY measures the "strength" of word CY's membership along the DC-dimension. The informal hope is that synonyms will be grouped into the same singular vectors, so that when a document (represented by a column of BT) is projected onto the subspace spanned by the singular vectors, it will automatically be "expanded" to include synonyms of words in the document, leading to improved information retrieval.

Now consider constructing the following citation graph from a set of documents. Let there be a node for each document and for each word. The node of a word links to the

(c)

(d)

Figure 4: Results on random corpora.

CM

document nodes it appears in. Let BT be the adjacency matrix of this graph. If we apply HITS to this graph, we find only the word-nodes have non-zero hub weights (since none of the document-nodes link to anything) and only the documentnodes have non-zero authority weights. Moreover, the vector of HITS hub weights of the word-nodes is exactly DC, the first left singular vector found by LSI.

This connection allows us to transfer insight from experiments on LSI to our understanding of HITS. In this vein, we conducted an experiment in which random corpora were generated by sampling from a set of English, French, and Italian documents. 10 Given that these random corpora are combinations of three distinct languages, the solution to Information Retrieval problems such as clustering or synonymidentification are exceedingly simple. The issue that we are interested in, however, is stability. To study stability, we generated 15 such collections and examined the direction of the principal eigenvectors found by HITS.

The principal eigenvector lies in the high dimensional joint-vocabulary space of the three languages. To display our results, we therefore defined English, French, and Italian "directions," and measured the degree to which the eigenvector lies in each these directions. 11 Fifteen independent repetitions of this process were carried out, and the results plotted in Figure 4a. As we see, despite the presence of clear clusters in the corpora, the eigenvectors are highly variable. Moreover, this variability persists in the second and third eigenvectors (Figures 4b,c).

10 The corpora were generated by taking paragraphs from novels in the three languages. Typical "documents" had 25-150 words, and the vocabulary consisted of the most common 1500 words per language. The collection was also manually "balanced" to equally represent each language.

11 This was done by picking a vector DC CT of unit-norm and whose CX-th element is proportional to the frequency of word CX in the English collection-thus, DC CT should be thought of as the "canonical" English direction-and taking the amount that CW A3 lies in the English direction to be the absolute magnitude of the dot-product between DC CT and CW A3 , and similarly for French and Italian.

Note that the variability is not an inherent feature of the problem. In Figure 4d, we display a run of a different algorithm (a variant of the HITS algorithm that we briefly describe in Section 7, and is studied in more detail in [Ng et al., 2001]). Here the results are significantly less variable.

6 Further Experiments

In this section we report further results of perturbation experiments on the Cora database. We also describe an experiment using web pages.

Recall our methodology in the experiments with the Cora database: We choose a subset of papers from the database and generate a set of perturbations to this subset by randomly deleting 30% of the papers. Our first experiment used all of the AI papers in Cora as the base set. Our results largely replicated those of Cohn and Chang [2000]-HITS returned several Genetics Algorithms (GA) papers as the top-ranked ones. With the database perturbed as described, however, these results were very variable, and HITS often returned seminal papers from broader AI areas as its top-ranked documents. Repeating the experiment excluding all the GA papers, HITS did slightly better; the results on five independent trials are shown below:

We see that, apart from the top 2-3 ranked papers, the remaining results are still rather unstable. For example, Pearl's book was originally ranked 8th; on the second trial, it dropped to rank 459. Similarly, Brooks' paper was rank 282, and jumped up to rank 9 on trial 3. However, this variability is not intrinsic to the problem, as shown by our PageRank results (all PageRank results in this section were generated with AF BP BCBMBE):

The largest change in a document's rank was a drop from 10 to 12-these results are much more stable than for HITS.

Closer examination of the HITS authority weights reviews that its jumps in rankings are indeed due to large changes in authority weights, whereas the PageRank scores tended to remain fairly stable. 12

We also carried out experiments on web pages. Given a query, Kleinberg [1998] describes a method for obtaining a collection of web pages on which to run HITS. We use exactly the method described there, and perturbed it in a natural way. 13 For the sake of brevity, we only give the results of two experiments here. On the query "mp3 players", HITS' results were as follows (long URLs are truncated):

While PageRank's rankings undergo small changes, HITS' rankings display a mass "flipping" behavior. Similar perturbation patterns to this (and the example below) for PageRank and HITS are observed in fourteen out of nineteen queries. Furthermore, HITS' results displayed such mass "flips" in roughly 20% of the trials, which is in accordance with the 20% removal rate.

Here is another typical web result, this time on the query "italian recipes." Note that "*" means that the page was removed by that trial's perturbation, and therefore has no rank. HITS' results were:

12 Examination of the second and higher eigenvectors in HITS shows that they, too, can vary substantially from trial to trial.

13 Kleinberg [1998] first uses a web search engine (www.altavista.com in our case) to retrieve 200 documents to form a "root set," which is then expanded (and further processed) to define the web-graph on which HITS operates. Our perturbations were arrived at by randomly deleting 20% of the root set (i.e. imagining that the web search engine had only returned 80% of the pages it actually did), and then following Kleinberg's procedure.

7 Discussion

It is well known in the numerical linear algebra community that a subspace spanned by several (e.g. the first CZ) eigenvectors may be stable under perturbation, while individual eigenvectors may not [Stewart and Sun, 1990]. Our results-both theoretical and empirical-reflect this general fact.

If the output of an algorithm is a subspace, then the stability considerations that we have discussed may not be a matter of primary concern. Such is the case, for example, for the LSI algorithm, where the goal is generally to project a data set onto a lower-dimensional subspace.

If we wish to interpret specific eigenvectors, however, then the stability issue becomes a matter of more serious concern. This is the situation for the basic HITS algorithm, where primary eigenvectors have been interpreted in terms of a set of "hubs" and "authorities." As we have seen, there are theoretical and empirical reasons for exercising considerable caution in making such interpretations.

Given that the principal eigenvector may not have a reliable interpretation, one can consider variations of the HITS approach that utilize multiple eigenvectors. Indeed, Kleinberg [1998] suggested examining multiple eigenvectors as a way of obtaining authorities within multiple communities. Again, however, it may be problematic to interpret individual eigenvectors, and in fact in our experiments we found significant variability in second and third eigenvectors. An alternative approach may be to automatically combine multiple eigenvectors in a way that explicitly identifies subspaces within the HITS framework. This is explored in [Ng et al., 2001]

The fact that the PageRank algorithm appears to be relatively immune to stability concerns is a matter of considerable interest. It is our belief that the "reset-to-uniformdistribution" aspect of PageRank is a critical feature in this regard. Indeed, one can explore a variation of the HITS algorithm which incorporates such a feature. Suppose that we construct a Markov chain on the web in which, with probability BD A0 AF, we randomly follow a hyperlink from the current page in the forward direction (on odd time steps), and we randomly follow a hyperlink in the backwards direction (on even time steps). With probability AF, we reset to a uniformly chosen page. The asymptotic web-page visitation distribution on odd steps is defined to be the authority weights, and on even steps the hub weights. As in Theorem 3, we can show this algorithm is insensitive to small perturbations (but unlike PageRank, we obtain hub as well as authority scores). The results of running this algorithm on the "three languages" problem are shown in Figure 4d, where we see that it is indeed significantly more stable than the basic HITS algorithm. This algorithm is also explored in more detail in [Ng et al., 2001].

Acknowledgments

We thank Andrew McCallum for providing the Cora citation data used in our experiments. We also thank Andy Zimdars for helpful comments. This work was supported by ONR MURI N00014-00-1-0637 and NSF grant IIS-9988642.