кому слава гугля спать не дает?

Нравится мне питон (язык программирования). И вот на глаза попалось:

.
The Google PageRank Algorithm in 126 Lines of Python
Reading How Google Finds Your Needle in the Web's Haystack I was surprised by the simplicity of the math underlying the google PageRank algorithm, and the ease with which it seemed to be efficiently implementable. Being able to do a google-style ranking seems useful for a wide range of cases, and since I had wanted to take a look at python for numerics for some time, I decided to give it a shot (note that there already exists a python implementation using the numarray module).

© 2006, Vincent Kräutler.

.

The Code

All of the following is done in python, with the numpy library, so don't forget to

from numpy import *

Full source code.

First, we need to transform the matrix of outgoing links into one of incoming links, while preserving the number of outgoing links per page and identifying leaf nodes:

def transposeLinkMatrix(
       outGoingLinks = [[]]
       ):
       """
       Transpose the link matrix. The link matrix contains the pages each page points to.
       However, what we want is to know which pages point to a given page. However, we
       will still want to know how many links each page contains (so store that in a separate array),
       as well as which pages contain no links at all (leaf nodes).

       @param outGoingLinks outGoingLinks[ii] contains the indices of pages pointed to by page ii
       @return a tuple of (incomingLinks, numOutGoingLinks, leafNodes)
       """

       nPages = len(outGoingLinks)
       # incomingLinks[ii] will contain the indices jj of the pages linking to page ii
       incomingLinks = [[] for ii in range(nPages)]
       # the number of links in each page
       numLinks = zeros(nPages, int32)
       # the indices of the leaf nodes
       leafNodes = []

       for ii in range(nPages):
               if len(outGoingLinks[ii]) == 0:
                       leafNodes.append(ii)
               else:  
                       numLinks[ii] = len(outGoingLinks[ii])
                       # transpose the link matrix
                       for jj in outGoingLinks[ii]:
                               incomingLinks[jj].append(ii)
                      
       incomingLinks = [array(ii) for ii in incomingLinks]
       numLinks = array(numLinks)
       leafNodes = array(leafNodes)
                              
       return incomingLinks, numLinks, leafNodes

Next, we need to perform the iterative refinement. Wrapping it up in a generator to hide the state of the iteration behind a function-like interface. Single-precision should be good enough.

def pageRankGenerator(
       At = [array((), int32)],
       numLinks = array((), int32),
       ln = array((), int32),
       alpha = 0.85,
       convergence = 0.01,
       checkSteps = 10
       ):
       """
       Compute an approximate page rank vector of N pages to within some convergence factor.
       @param At a sparse square matrix with N rows. At[ii] contains the indices of pages jj linking to ii.
       @param numLinks iNumLinks[ii] is the number of links going out from ii.
       @param ln contains the indices of pages without links
 @param alpha a value between 0 and 1. Determines the relative importance of "stochastic" links.
 @param convergence a relative convergence criterion. smaller means better, but more expensive.
       @param checkSteps check for convergence after so many steps
       """

       # the number of "pages"
       N = len(At)

       # the number of "pages without links"
       M = ln.shape[0]

       # initialize: single-precision should be good enough
       iNew = ones((N,), float32) / N
       iOld = ones((N,), float32) / N

       done = False
       while not done:

               # normalize every now and then for numerical stability
               iNew /= sum(iNew)

               for step in range(checkSteps):

                       # swap arrays
                       iOld, iNew = iNew, iOld

                       # an element in the 1 x I vector.
                       # all elements are identical.
                       oneIv = (1 - alpha) * sum(iOld) / N

                       # an element of the A x I vector.
                       # all elements are identical.
                       oneAv = 0.0
                       if M > 0:
                               oneAv = alpha * sum(iOld.take(ln, axis = 0)) * M / N

                       # the elements of the H x I multiplication
                       ii = 0
                       while ii < N:
                               page = At[ii]
                               h = 0
                               if page.shape[0]:
                                       h = alpha * dot(
                                               iOld.take(page, axis = 0),
                                               1. / numLinks.take(page, axis = 0)
                                               )
                               iNew[ii] = h + oneAv + oneIv
                               ii += 1

               diff = iNew - iOld
               done = (sqrt(dot(diff, diff)) / N < convergence)

               yield iNew

Finally, we might want to wrap up the above behind a convenience interface like so:

def pageRank(
       linkMatrix = [[]],
       alpha = 0.85,
       convergence = 0.01,
       checkSteps = 10
       ):
       """
       Convenience wrap for the link matrix transpose and the generator.
       """
       incomingLinks, numLinks, leafNodes = transposeLinkMatrix(linkMatrix)

       for gr in pageRankGenerator(incomingLinks, numLinks, leafNodes,
   alpha = alpha,
   convergence = convergence,
   checkSteps = checkSteps):
               final = gr

       return final

.
.