[information retrieval] link analysis

(1). Reading materials 《Introduction to Information Retrieval》 The first 464-470 page 21.2 As described in section PageRank computing method （ adopt power iteration To achieve ）, use Java Language or other commonly used languages to implement the algorithm . Take the structure shown in the following figure as an example to calculate each document Of PageRank value , among teleportation rate=0.05.

Preset some program parameters ：

Create adjacency matrix according to the graph given in the title ：


For this question , The adjacency matrix is shown below ：
linkMatrix[i][j]=1 It indicates that there is a slave node i Point to the node j The directed side of .

Then start to calculate the transition probability matrix ：
There are three steps ：

1. Use 1 Take out each 1
2. The processed result matrix is multiplied by 1-α
3. Add alpha/N
   
   Finally, the transition probability matrix corresponding to the ontology can be obtained ：
   

Perform power iteration ：
Initialize the probability distribution vector ：

Then iterate according to the following formula , Until the probability distribution vector converges ：


The final calculation results are as follows ： It can converge after one iteration

namely Pagerank(d1)=0.017,Pagerank(d2)=0.492,Pagerank(d3)=0.492. A simple analysis shows that ,d2 And d3 It's symmetrical . At the same time, because there is no document Point to d1, Only when you encounter random jump, you will jump to document1, therefore Pagerank(d1) Will be significantly smaller than the other two values .

(2). In another way （ No power iteration The way ） Calculate with pen （ No program calculation ） topic (1) Each of them document Of PageRank value . Detailed description and calculation process are required .（10 branch ）

It can be calculated according to algebraic algorithm ：
PageRank The definition of ：

therefore ：

among M Is the transition probability matrix （ No random jump ）,1 by [1*N] The holonomic matrix of ,I Is the unit matrix

And that gives us ,Pagerank(d1)=0.017,Pagerank(d2)=0.492,Pagerank(d3)=0.492, The results are obtained by the power iteration method .

(3). Reading materials 《Introduction to Information Retrieval》 The first 474-477 page 21.3 As described in section HITS computing method （ adopt power iteration To achieve ）, use Java Language or other commonly used languages to implement the algorithm . Take the structure shown in the following figure as an example to calculate each document Of authority Values and hub value .

Preset some program parameters ：

Then label the nodes in the graph , And generate the corresponding adjacency matrix , As shown below ：

Adjacency matrix ：

initialization hub as well as authority vector ：

Start the iteration according to the following formula , At the same time, after each iteration, the vector needs to be normalized , until hub And authority Vector convergence ：

The final running results are as follows ：


Final hub The largest value is the node 8（ be in base set） , node 8 Pointing to the node 7 and 9, meanwhile 7 and 9 It is pointed to by multiple nodes （authority High value ）, So nodes 8 Of hub The highest value is very reasonable .
authority The largest value is the node 7 （ be in root set）, node 7 By node 2,3,8 Point to , At the same time node 2,3,8 Of hub High value , So nodes 7 Of authority The highest value is very reasonable .

hub/authority Value can reflect the navigation and authority of a web page . Different website purposes should focus on different indicators , For example, navigation websites should focus on hub value , This can point more accurately ; Portal websites should focus on authority value , Let more navigation websites point to it , Improve Authority .