PageRank是搜索引擎结果排序的重要算法，其依赖的方式是链接结构分析，大致解释就是一个网页A有一个指向另一个网页B的链接，就相当于A给B投票，获得投票越多的网页的PageRank值越高。并不是每个网页的投票权重都是一样的，自己PageRank越大的网页投票权重越大，所以PageRank的计算公式是递归的，需要迭代计算，直到结果收敛。

我使用Go语言对真实网页的数据WT2g进行了PageRank的计算，计算出的结果分布如下图：

观察发现，PageRank的分布服从齐普夫分布(Zipf Distribution)，其中32%的网页的PageRank为最小值9.459×10^-7，超过一半的网页的PageRank的值小于6.600×10^-6，而PageRank的最大值为1.885×10^-3。

值得一提的是Go语言，推荐一个对Go语言特性的介绍：Go在Google：以软件工程为目的的语言设计。使用Go语言最大的感受是它的函数可以有多返回值，而且在各种API中这个特性被大量使用，而且约定多返回值的最后一个参数是error类型，表示是否有错误发生。这种错误处理的方法和C++、Java、Python、JavaScript使用的异常不同，倒是与C语言的错误处理相似。C语言习惯于把函数的返回值作为「是否有错误发生」的标记，如果有错误再通过其他的手段（如全局变量error）来获取，Go语言直接把错误作为了一个返回值。Go语言还支持一等函数(First Class Function)和闭包，因此方便用来实现yield功能，下面代码中的lineReader函数就是返回了一个生成器，用来按行读取文件，每调用一次读取一行，读完以后释放内存。Go语言还是一个显式有指针的语言，同时也提供了垃圾回收，省去了手动维护内存的麻烦。

以下是用Go语言计算PageRank的代码：

package main

import (
    "bufio"
    "errors"
    "fmt"
    "io"
    "math"
    "os"
    "strings"
)

type vertex struct {
    inDegree  int
    outDegree int
    pagerank  float64
}

type edge struct {
    start int
    end   int
}

var vertexs []vertex
var edges []edge
var vertexID map[string]int = make(map[string]int)
var numVertex int = 0

func lineReader(filename string) (func() (string, error), error) {
    f, err := os.Open(filename)
    if err != nil {
        return nil, err
    }
    buf := bufio.NewReaderSize(f, 64)
    return func() (string, error) {
        line, isPrefix, err := buf.ReadLine()
        if err != nil {
            if err == io.EOF {
                if err := f.Close(); err != nil {
                    return "", err
                }
            }
            return "", err
        }
        if isPrefix {
            return "", errors.New("buffer size to small")
        }
        return string(line), nil
    }, nil
}

func addVertex(vertexName string) int {
    var ID int
    var ok bool
    if ID, ok = vertexID[vertexName]; !ok {
        ID = numVertex
        vertexID[vertexName] = ID
        vertexs = append(vertexs, vertex{})
        numVertex++
    }
    return ID
}

func read() {
    readline, err := lineReader("wt2g_inlinks.source")
    if err != nil {
        panic(err)
    }
    for {
        line, err := readline()
        if err != nil {
            if err == io.EOF {
                break
            }
            panic(err)
        }
        // Line format is like "ID1\tID2"
        sections := strings.Split(line, "\t")
        if len(sections) != 2 {
            panic(errors.New("Illegal line format"))
        }
        start := addVertex(sections[0])
        end := addVertex(sections[1])
        edges = append(edges, edge{start, end})
    }
}

func calcPagerank(alpha float64, numIterations int) {
    // Initialize out degree of every vertex
    for i := range edges {
        edge := &edges[i]
        vertexs[edge.start].outDegree++
        vertexs[edge.end].inDegree++
    }
    var I = make([]float64, numVertex)
    var S float64
    for i := 0; i < numVertex; i++ {
        vertexs[i].pagerank = 1 / float64(numVertex)
        I[i] = alpha / float64(numVertex)
    }
    // Calculate pagerank repeatedly until converge (numIterations times)
    for k := 0; k < numIterations; k++ {
        for i := range edges {
            edge := &edges[i]
            I[edge.end] += (1 - alpha) * vertexs[edge.start].pagerank / float64(vertexs[edge.start].outDegree)
        }
        S = 0
        for i := 0; i < numVertex; i++ {
            if vertexs[i].outDegree == 0 {
                S += (1 - alpha) * vertexs[i].pagerank / float64(numVertex)
            }
        }
        for i := 0; i < numVertex; i++ {
            vertexs[i].pagerank = I[i] + S
            I[i] = alpha / float64(numVertex)
        }
    }
}

func main() {
    read()
    calcPagerank(0.15, 30)
    fmt.Println("Done")
}

BYVNotes是一个我用Go语言实现的简单在线记事本网站，使用了Revel框架。