# A Model Based on Cocitation for Web Information Retrieval

Authors: Yue Xie; Ting-Zhu Huang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

According to the relationship between authority and cocitation in HITS, we propose a new hyperlink weighting scheme to describe the strength of the relevancy between any two webpages. Then we combine hyperlink weight normalization and random surfing schemes as used in PageRank to justify the new model. In the new model based on cocitation (MBCC), the pages with stronger relevancy are assigned higher values, not just depending on the outlinks. This model combines both features of HITS and PageRank. Finally, we present the results of some numerical experiments, showing that the MBCC ranking agrees with the HITS ranking, especially in top 10. Meanwhile, MBCC keeps the superiority of PageRank, that is, existence and uniqueness of ranking vectors.


---

## Body

## 1. Introduction

In the past, search engines ranked pages by using word frequency or similar measures. However, the relevancy of webpages returned by this traditional web information retrieval is still lacking, because the webpages are created with varying qualities. Recently, some new algorithms have been created that greatly improve rankings. One of the popular ideas is to use hyperlinks to determine the value of different webpages. This hyperlink graph contains useful information: if webpagei has a link pointing to webpage j, it usually indicates that the creator of i considers j to contain relevant information for i. Such useful opinions and knowledge are therefore registered in the form of adjacency matrix which is denoted by L. Lij=1 if there is a link from i to j, or 0, otherwise.Two most popular ranking algorithms based on hyperlink analysis are the PageRank algorithm [1, 2] and the HITS (Hyper-text Induced Topic Selection) algorithm [3]. Generally, PageRank considers the hyperlink weight normalization and the equilibrium distribution of random surfers as the citation score. For more information about the calculation methods of PageRank refer to [4–6]. HITS makes the distinction between hubs and authorities and then computes them in a mutually reinforcing way. For each of these two algorithms, the ranking vector is the dominant eigenvector of some matrix describing the network. How this matrix is defined differs in each method. There are other works which have recognized that the hyperlink structure can be very valuable for locating information [3, 7, 8].This paper is organized as follows. In Section2, we introduce the PageRank and HITS algorithms and briefly discuss the limitations in HITS. Then in Section 3, we emphasize the role of cocitation (Figure 1) and provide a hyperlink weighting scheme to describe the strength of the relevancy between any two webpages. In order to ensure the existence of solutions and uniqueness of solutions in the new model (MBCC), we also combine ideas from PageRank. In Section 4, some experiments are presented. The result shows that the MBCC ranking is close well to the HITS ranking. Conclusions are given in Section 5.Figure 1
Webpagesi, j are cocited by webpage k.


## 2. PageRank and HITS

We treat the web as a directed graphD=(V,E): the nodes in V correspond to the pages, and a directed edge (i,j)∈E indicates the existence of a link from i to j. We say that the out-degree of a node i denoted by dout(i) is the number of nodes it has links point to, and the in-degree of i denoted by din(i) is the number of nodes that have links point to it. We also denote that
(1)dout=(dout(1),…,dout(n))T,din=(din(1),…,din(n))T.


### 2.1. Review of PageRank

PageRank [1, 2] uses a web surfing model based on a random walk process. Suppose there is a link from page i to page j; that is, (i,j)∈E. Consider a random surfer visiting page i at time t. Then at the next time t+1, the surfer lands at page j with probability 1/dout(i). Once the above is done, the PageRank algorithm assigns a rank value xi for the page i as a function of the rank of the pages that point to it:
(2)xi=∑(j,i)∈E‍ridout(j).If the pagei has no outlink, that is, dout(i)=0, then, at time t+1, the surfer chooses any page with probability 1/n. Thus, we replace dout(i)=0 with dout(i)=n. Then the stationary distribution x is determined by the following matrix form:
(3)x=PTx,PT=(L+deT)TDout-1.Herex=(x1,…,xn)T, L is the adjacency matrix of the directed web graph, Dout=diag⁡(dout), and e=(1,…,1)T. In the vector d, the element di=1 if the ith row of L corresponds to a dangling node (dout(i)=0), or 0, otherwise.In order to calculate the above recursive equation and get a unique stationary probability distribution, it is important to guarantee that (3) is convergent. This problem can be solved if the directed graph D is strongly connected, which is generally not the case for the directed graph. In the context of computing PageRank, the standard way of ensuring this property is to add a new set of complete outgoing transitions, with small transition probabilities (in this work, we set each of them as 1/n), to all nodes in D. Then the modified transition probability called Google matrix is
(4)GT=α(L+deT)TDout-1+(1-α)(1n)eeT,
where α=0.8~0.9. Here e=(1,…,1)T; thus eeT is a matrix of all 1’s. The PageRank algorithm is to solve the eigenvector of the Google matrix GT(5)x=GTx,∑i=1nxi=1,
where GT is stochastic and irreducible.PageRank models two types of random jumps on the Internet. With probability1-α a surfer randomly chooses a new page. Otherwise, the surfer follows one of directed edges from the present node.


### 2.2. Review of HITS

In the HITS algorithm [3], each webpage i has both a hub score yi (based on the links going from the page) and an authority score xi (based on the links going to the page). Let x=(x1,…,xn)T denote the vector of all authority weights, let y=(y1,…,yn)T denote the vector of all hub weights, and let L be the adjacency matrix of the directed web graph. In HITS, there are two operations at each iteration. One is defined as operation ℐ which sets the authority vector to x=LTy. It indicates that a good authority is pointed by many good hubs. Another is defined as operation 𝒪 which sets the hub vector to y=Lx. It indicates that a good hub points to many good authorities. This mutually reinforcing relationship can be written in the following matrix representations:
(6)x=1λ*LTLx,∑i=1nxi2=1,y=1λ*LLTy,∑i=1nyi2=1.The final authority and hub scores are the principal eigenvectors ofLTL and LLT which are corresponding to the dominant eigenvalue λ*. Since LTL and LLT determine the authority ranking and hub ranking, we call LTL the authority matrix and LLT the hub matrix.In the fields of citation analysis and bibliometrics, it has shown that the authority matrix has interesting connections to cocitation [3]. Here cocitation is defined as the number of webpages that cocite i, j [9]. In the authority matrix, (LTL)ii=Σk=1nLkiLki=Σk=1nLki is the in-degree of page i; that is,
(7)(LTL)ii=din(i).
This implies that
(8)diag⁡(LTL)=Din.Fori≠j, (LTL)ij=Σk=1nLkiLkj is the number of webpages that cocite i, j that is denoted by Cij. Therefore the authority matrix LTL is the sum of in-degree and cocitation [10, 11]
(9)LTL=Din+C.
The self cocitation Cii in C is not defined and is usually set to 0.


### 2.3. Existence and Uniqueness of Ranking Vectors

In this section, we present the existence and uniqueness of ranking vectors in the above two algorithms.Since the Google matrixGT in (4) is stochastic and irreducible, for the PageRank algorithm, the PageRank ranking vector exists, and it is unique and positive. See the equivalent theorem in [12, Theorem 3.8]. For the HITS algorithm, it has been proved that the hub and authority ranking vectors exist but may not be unique. In [12], they show that the HITS algorithm badly behaved on certain networks, meaning that (i) it can return ranking vectors that are not unique but depend on the initial seed vector or (ii) it can return ranking vectors that inappropriately assign zero weights to parts of the network.There are also other limitations for HITS; see [12, 13]. Thus, to address these limitations, a modification for HITS is needed, for example, exponentiated input method in [12]. In the next section, we combine both features of HITS and PageRank. The ranking produced by the new model is expected to be unique and close to the HITS ranking.


## 2.1. Review of PageRank

PageRank [1, 2] uses a web surfing model based on a random walk process. Suppose there is a link from page i to page j; that is, (i,j)∈E. Consider a random surfer visiting page i at time t. Then at the next time t+1, the surfer lands at page j with probability 1/dout(i). Once the above is done, the PageRank algorithm assigns a rank value xi for the page i as a function of the rank of the pages that point to it:
(2)xi=∑(j,i)∈E‍ridout(j).If the pagei has no outlink, that is, dout(i)=0, then, at time t+1, the surfer chooses any page with probability 1/n. Thus, we replace dout(i)=0 with dout(i)=n. Then the stationary distribution x is determined by the following matrix form:
(3)x=PTx,PT=(L+deT)TDout-1.Herex=(x1,…,xn)T, L is the adjacency matrix of the directed web graph, Dout=diag⁡(dout), and e=(1,…,1)T. In the vector d, the element di=1 if the ith row of L corresponds to a dangling node (dout(i)=0), or 0, otherwise.In order to calculate the above recursive equation and get a unique stationary probability distribution, it is important to guarantee that (3) is convergent. This problem can be solved if the directed graph D is strongly connected, which is generally not the case for the directed graph. In the context of computing PageRank, the standard way of ensuring this property is to add a new set of complete outgoing transitions, with small transition probabilities (in this work, we set each of them as 1/n), to all nodes in D. Then the modified transition probability called Google matrix is
(4)GT=α(L+deT)TDout-1+(1-α)(1n)eeT,
where α=0.8~0.9. Here e=(1,…,1)T; thus eeT is a matrix of all 1’s. The PageRank algorithm is to solve the eigenvector of the Google matrix GT(5)x=GTx,∑i=1nxi=1,
where GT is stochastic and irreducible.PageRank models two types of random jumps on the Internet. With probability1-α a surfer randomly chooses a new page. Otherwise, the surfer follows one of directed edges from the present node.


## 2.2. Review of HITS

In the HITS algorithm [3], each webpage i has both a hub score yi (based on the links going from the page) and an authority score xi (based on the links going to the page). Let x=(x1,…,xn)T denote the vector of all authority weights, let y=(y1,…,yn)T denote the vector of all hub weights, and let L be the adjacency matrix of the directed web graph. In HITS, there are two operations at each iteration. One is defined as operation ℐ which sets the authority vector to x=LTy. It indicates that a good authority is pointed by many good hubs. Another is defined as operation 𝒪 which sets the hub vector to y=Lx. It indicates that a good hub points to many good authorities. This mutually reinforcing relationship can be written in the following matrix representations:
(6)x=1λ*LTLx,∑i=1nxi2=1,y=1λ*LLTy,∑i=1nyi2=1.The final authority and hub scores are the principal eigenvectors ofLTL and LLT which are corresponding to the dominant eigenvalue λ*. Since LTL and LLT determine the authority ranking and hub ranking, we call LTL the authority matrix and LLT the hub matrix.In the fields of citation analysis and bibliometrics, it has shown that the authority matrix has interesting connections to cocitation [3]. Here cocitation is defined as the number of webpages that cocite i, j [9]. In the authority matrix, (LTL)ii=Σk=1nLkiLki=Σk=1nLki is the in-degree of page i; that is,
(7)(LTL)ii=din(i).
This implies that
(8)diag⁡(LTL)=Din.Fori≠j, (LTL)ij=Σk=1nLkiLkj is the number of webpages that cocite i, j that is denoted by Cij. Therefore the authority matrix LTL is the sum of in-degree and cocitation [10, 11]
(9)LTL=Din+C.
The self cocitation Cii in C is not defined and is usually set to 0.


## 2.3. Existence and Uniqueness of Ranking Vectors

In this section, we present the existence and uniqueness of ranking vectors in the above two algorithms.Since the Google matrixGT in (4) is stochastic and irreducible, for the PageRank algorithm, the PageRank ranking vector exists, and it is unique and positive. See the equivalent theorem in [12, Theorem 3.8]. For the HITS algorithm, it has been proved that the hub and authority ranking vectors exist but may not be unique. In [12], they show that the HITS algorithm badly behaved on certain networks, meaning that (i) it can return ranking vectors that are not unique but depend on the initial seed vector or (ii) it can return ranking vectors that inappropriately assign zero weights to parts of the network.There are also other limitations for HITS; see [12, 13]. Thus, to address these limitations, a modification for HITS is needed, for example, exponentiated input method in [12]. In the next section, we combine both features of HITS and PageRank. The ranking produced by the new model is expected to be unique and close to the HITS ranking.


## 3. A Model Based on Cocitation (MBCC)

In HITS, according to (9), the authority ranking value xi can be expressed as
(10)xi=1λ*din(i)xi+1λ*∑j=1nCijxj,
revealing the close relationship between authorities and cocitations. It also implies that, if two distinct webpages i, j are cocited by many other webpages k as shown in Figure 1, then i, j are likely to be related in some sense. In this paper, we present a property for HITS corresponding to (10).Property 1 (relationship between authority value and cocitation).
If the number of webpages that cocite webpagesi and j, that is, Cij, is larger, the page i could receive more authority value from the page j, even though there are no links between i and j.The fact that the webpages cocite two distinct webpagesi and j indicates that i, j have certain commonality. Therefore, we say that the number of cocitations represents the relevancy among the pages. Then, in the following, we focus on the use of cocitation for analyzing the relevancy among the pages.Note that, in Section2.1, the rank of a page in PageRank is divided among its forward links evenly; see (2); that is, a web surfer could chose the forward outlinks randomly. However, this process of dividing the rank equally may seem unrealistic; that is, a web surfer may have a priori idea of the value of pages, favoring pages from the relevant sites. Since it shows that the number of cocitations could represent the relevancy among the pages, we say that the number of cocitations between two pages can impact the behavior of web surfers. Therefore, we define a new hyperlink weighting scheme based on cocitation as follows:Definition 2 (hyperlink weighting scheme based on cocitation).
LetQij be the number of webpages that cocite two webpages i, j. Specially, Qii=din(i), and din(i) is the in-degree of webpage i. Then we define the following function as the value of j which will receive form i:
(11)Wij=Qij∑k∈V‍Qik=QijQi,
where Qi=∑k∈VQik.Under this assignment method, the rank value for the pagej is determined by
(12)xj=∑m∈V‍Wmjxm.The matrix form of above equation isx=Wx, where x=(x1,…,xn)T. The problem is that, if at least one page has zero in-degree, that is, no in-links and Qi=0, then the matrix W is absorbing and its dominant eigenvector does not exist. In order to resolve this, similarly to PageRank, we assume that, if the page i has no link that points to it, then at time t+1, the page i divides its value equally to any other page with probability 1/n. The modified matrix W is given by
(13)W=(L′L+veT)TDQ-1=(L′L+evT)DQ-1,
where we replace Qi=0 with Qi=n, DQ=diag⁡(Q~) and Q~=(Q1,…,Qn)T. Q~ can be computed as
(14)Q~=(L′L+veT)e.
In the vector v, the element vi=1 if the i-th row of L corresponds to a page with no in-degree, or 0, otherwise. Therefore, the modified matrix W becomes a stochastic matrix, that is, each column in W sum to 1.In order to get a unique stationary probability distribution, it is important to guarantee thatW is strongly connected. Similarly to PageRank, we add a new set of complete outgoing transitions. The final transition probability matrix based on using cocitation as a hyperlink weighting scheme is
(15)W=β(L′L+evT)DQ-1+(1-β)(1n)eeT,
where 0<β<1 and e=(1,…,1)T. The model based on cocitation (MBCC) is to solve the following function:
(16)x*={β(L′L+evT)DQ-1+(1-β)(1n)eeT}x*,∑i=1nxi=1.We assume that the solution of (16) denoted by x*=(x1*,…,xn*) is the MBCC authority ranking vector, and y=LLTx* is the MBCC hub ranking vector. Since the matrix W in (15) is stochastic and irreducible, just like the Google matrix G in PageRank, the solution of (16) exists, and it is unique and positive.


## 4. Numerical Experiments

First, we present an example to describe the assignment process in Definition2.Example 1.
Suppose that there are six webpagesV=(j1,j2,j3,a,b,c), and the directed graph is shown in Figure 2. The conclusion can be found from Table 1 and Figure 2. In Table 1, Q(i,j) is the number of webpages that cocite webpages i and j; W(i,j) is obtained by (11). In Figure 2, the left one is the original link structure of PageRank where the value of the page j1 is divided equally to the pages that it points to, and the right one divides the value of j1 based on cocitation.Table 1
The data of Example1.
(
j
1
,
j
1
)
(
j
1
,
j
2
)
(j1,j3)
Q
3
3
1
W
3/7
3/7
1/7(a) Link structure of PageRank. (b) Resigned link structure of MBCC.
(a)
(b)Then, we compare the MBCC model with HITS and PageRank, experimenting with dataset fromhttp://www.cs.toronto.edu/~tsap/experiments/datasets/. The dataset is about the topic computational geometry which contains a total of 1100 webpages. We set β=0.9. Meanwhile, we use τ=10-10 as the convergence tolerance and measure the convergence rates of the three algorithms using the L1 norm of the residual vector. Table 2 shows the list of the top 20 authorities with HITS, MBCC, and PageRank. Table 3 shows the list of the top 20 hubs with HITS and MBCC. It shows that MBCC authority ranking is closer to HITS authority ranking than PageRank ranking which is close to HITS authority ranking. The comparison between MBCC and HITS ranking vectors in Table 4 indicates that MBCC ranking agrees well with HITS ranking, especially in top 10.Table 2
HITS authority ranking, MBCC authority ranking, and PageRank ranking in top 20.
HITS
MBCC
PageRank
URL
1
1
9
http://www.ics.uci.edu/~eppstein/geom.html
2
2
10
http://www.geom.uiuc.edu/software/cglist/
3
3
6
http://www.cs.uu.nl/CGAL
4
4
18
http://www.ics.uci.edu/~eppstein/junkyard
5
6
14
http://www.scs.carleton.ca/~csgs/resources/cg.html
6
7
20
http://www.geom.uiuc.edu/
7
5
>20
http://www.ics.uci.edu/~eppstein
8
8
>20
http://www.mpi-sb.mpg.de/LEDA/leda.html
9
10
>20
http://www.inria.fr/prisme/personnel/bronnimann/cgt
10
9
>20
http://www.cs.sunysb.edu/~algorith/
11
13
>20
http://graphics.lcs.mit.edu/~seth/pubs/taskforce/techrep.html
12
11
>20
http://www.cs.smith.edu/~orourke
13
12
>20
http://www.cs.brown.edu/people/rt
14
18
>20
http://www.geom.uiuc.edu/~nina/
15
>20
>20
http://compgeom.cs.uiuc.edu/~jeffe/compgeom
16
14
>20
http://www.cs.princeton.edu/~chazelle
17
>20
>20
http://www.dcc.unicamp.br/~guialbu/geompages.html
18
16
8
http://www.yahoo.com
19
>20
>20
http://www.ics.uci.edu/~eppstein/gina/authors.html
20
>20
>20
http://www.cs.brown.edu/people/rt/sdcr/report.htmlTable 3
HITS hub ranking and MBCC hub ranking in top 20.
HITS
MBCC
URL
1
2
http://mother.lub.lu.se/ae/bytitle/043501-043550.html
2
1
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/preprehistory.html
3
3
http://www.dcc.unicamp.br/~guialbu/geompages.html
4
4
http://www.softlab.ece.ntua.gr/~cfrag
5
5
http://corelab.cs.ntua.gr/courses/compgeom
6
6
http://compgeom.cs.uiuc.edu/~jeffe/compgeom/direct.html
7
7
http://mother.lub.lu.se/ae/bydomain/010101-010150.html
8
9
http://www-sop.inria.fr/prisme/personnel/bronnimann/cgt/WWW.html
9
10
http://members.tripod.com/~GeomWiz/develop.html
10
11
http://geomwiz.tripod.com/develop.html
11
8
http://www.scs.carleton.ca/~csgs/resources/cg.html
12
13
http://www.ams.sunysb.edu/~jsbm/hotlist.html
13
14
http://www.graphics.lcs.mit.edu/~fredo/Book/geoAlgo.html
14
16
http://www.cs.uwaterloo.ca/~yganjali/r_links.html
15
12
http://cs.smith.edu/~streinu/bookmarks.html
16
15
http://www.cs.umn.edu/scg98
17
>20
http://forum.swarthmore.edu/library/topics/comp_geom
18
19
http://www.geom.umn.edu/~mucke/GeomDir/people.html
19
>20
http://cis.poly.edu/~aronov
20
20
http://intra.cmkos.cz/~honza/osvr/odkazy.htmlTable 4
Comparison between MBCC and HITS ranking vectors, for example, top 10 represents a ranking vector agreeing with another ranking vector in top 10.
Top 10
Top 20
Top 30
Top 40
Top 50
Authority (HITS  MBCC)
100%
80%
96.7%
85%
90%
Hub (HITS  MBCC)
90%
90%
90%
92.5%
96%


## 5. Conclusion

In this work, we emphasize the role of cocitation in defining authorities. First, we observe that, in the HITS algorithm, if two distinct webpagesi, j are cocited by many other webpages k, then i, j are likely to be related in some sense or have certain commonality. According to this close relationship, we come to the conclusion that the higher the number of webpages that cocite webpages i and j, the stronger the relevancy between the two pages. The page j with stronger relevancy should obtain more values from page i. Therefore, we develop a hyperlink weighting scheme for extracting information from the link structure. Then we combine hyperlink weight normalization and random surfing schemes as used in PageRank to justify the model.The experimental results show that the MBCC authority (hub) ranking is close well to the HITS authority (hub) ranking in top 20, and in general a surfer seldomly browses beyond these webpages in top 20 [11]. Moreover, MBCC keeps the superiority of PageRank: the authority vector of MBCC in (16) exists, and it is unique and positive, while the authority and hub vectors of HITS may not be unique. Therefore, we can use the authority (hub) ranking vector of MBCC as the authority (hub) ranking vector of HITS.



---

*Source: 418605-2014-02-27.xml*