10-04-2017, 09:37 PM
The algorithms known as PageRank and HITS are the two most prominent examples of network-based ranking methods. These methods require only a little bit of mathematics to understand well. The main underlying model is that the rank of any page is dependent on the number and location of backlinks (or in-links) to that page, and the importance or quality of the pages that contain those backlinks. Most explanations of how this is precisely computed uses the language of linear algebra and eigenvalues , which often obscures the relatively simple ideas underlying them.Here is an attempt to make these algorithms more accessible by boiling down the math to the essential details. Let G be a directed graph. We think of the nodes of G as webpages and the directed arcs as hyperlinks. Let A(G)=A be the adjacency matrix where A[i,j] = 1 if (i,j) is an arc, is 0 otherwise. The ith row of A is the (characteristic) vector representing all the out-neighbors of the ith node, and the jth column of A is the vector representing the in-neighbors of the jth node. The transpose matrix A has the roles reversed, where the ith row of A is the vector representing all the in-neighbors of the ith node, and the jth column of A is the vector representing the out-neighbors of the jth node.Matrix multiplication can give simple algebraic representations of graph structures. For example, the square of the adjacency matrix A^2 has as its [i,j]th entry the number of 2-hop paths from ith node to jth node. And the product A A has as its [i,j]th entry the number of nodes that are common in-neighbors to both the ith and jth node. Note how A A is a symmetric matrix, likewise AA is also symmetric. Symmetric matrices have the property that the [i,j]th entry matches the [j,i]th entry for all pairs i,j.