Beyond the Void
BYVoid
用Go語言計算PageRank

PageRank是搜索引擎結果排序的重要算法,其依賴的方式是鏈接結構分析,大致解釋就是一個網頁A有一個指向另一個網頁B的鏈接,就相當於A給B投票,獲得投票越多的網頁的PageRank值越高。並不是每個網頁的投票權重都是一樣的,自己PageRank越大的網頁投票權重越大,所以PageRank的計算公式是遞歸的,需要迭代計算,直到結果收斂。

我使用Go語言對真實網頁的數據WT2g進行了PageRank的計算,計算出的結果分佈如下圖:

PageRank Distribution

觀察發現,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框架。


上次修改時間 2017-03-16

相關日誌