Beyond Google’s PageRank: A Novel Link Analysis Algorithm without a Damping Factor
Keita Sugihara
This presentation proposes an alternative centrality measure to Google’s PageRank, which is a widely used algorithm for internet search engines that scores a page based on link relations of the sites. PageRank uses the traditional adjacency matrix. The proposed method overcomes the challenges faced by Google’s algorithm by using the Hermitian adjacency matrix.
First, the presenter points out three characteristics of Google’s PageRank: (a) a page receives a high score when it has an inlink from a node with a high score; (b) a page receives a high score when it has many inlinks; and (c) a page receives a high score when it has an inlink from a node with few outlinks.
Second, the presenter focuses on the damping factor and its associated problems in PageRank. Google needs the damping factor to solve the eigenvalue problem of the Google Matrix using the power method, where the absolute maximal eigenvalue’s multiplicity of the matrix needs to be one. This condition is equivalent to the strongly connected connectedness of the graph corresponding to the matrix, which is not realized using internet hyperlink relations. The damping factor assures this condition by transforming the real hyperlink relations into a presupposed strongly connected graph. In PageRank, an arbitrary value of the damping factor can be selected from 0 to 1, which leads to a problem where the behavior of PageRank scores with respect to the damping factor values is not obvious. Generally, a damping factor value of 0.85 is widely used.
Third, the presenter introduces the Hermitian centrality score using the Hermitian adjacency matrix. Guo defines the matrix using the imaginary unit i (the square root of -1) as follows: for a graph X=(V, E), the Hermitian adjacency matrix H is a matrix with entries Huv = 1 if uv and vu are in E, i if uv is in E and vu is not in E, -i if uv is not in E and vu is in E, and 0 otherwise. Trials suggest that if the connectedness of the graph corresponding to the Hermitian adjacency matrix is weak, the multiplicity of the Hermitian matrix is one and the eigenvalue problem of the matrix can be solved using the power method. Therefore, the damping factor is not required in the Hermitian centrality score for weakly connected graphs.
Fourth, this presentation shows details of the Hermitian centrality score, which is an algorithm for weakly connected graphs that uses the complex plane to calculate the score of a node in the graph. Moreover, this algorithm can also be applied to non-weakly connected graphs.
Fifth, the presenter points out that the Hermitian centrality score can reproduce the result of PageRank with a damping factor value of 0.85. Moreover, the proposed algorithm can employ three parameters: k1, k2, and k3, which correspond to the three characteristic of PageRank given previously. Hermitian scores are systematically possible in operation by changing these three parameters. Moreover, this presentation includes the inventions of the acquired patent. 
← Schedule