iT邦幫忙

2021 iThome 鐵人賽

DAY 28
0
自我挑戰組

一個月的演算法挑戰系列 第 28

Day28:網頁排名演算法(PageRank)

PageRank

PageRank是一種連結分析演算法,它通過對超連結集合中的元素用數字進行權重賦值,實現「衡量集合範圍內某一元素的相關重要性」的目的。著名例子:Google利用PageRank分析網頁相關性和重要性,在搜尋引擎最佳化(SEO)中經常被用來作為評估網頁最佳化的成效因素之一。


搜尋引擎最佳化(Search Engine Optimization,SEO)

透過搜尋引擎的運算規則來調整網站排名,將網站曝光度提高可以增加網站的流量,當使用者在進行搜尋時,往往注意力會放在前面的搜尋結果,所以網站為了提高曝光度,會使用各種方式提高排名。

「針對搜尋引擎作最佳化的處理」,是指為了要讓網站更容易被搜尋引擎接受。搜尋引擎會將網站彼此間的內容做一些相關性的資料比對,然後再由瀏覽器將這些內容以最快速且接近最完整的方式,呈現給搜尋者。


用Python實現PageRank

#how we update the PageRank
def PageRank_one_iter(graph, d):
    node_list = graph.nodes
    for node in node_list:
        node.update_pagerank(d, len(graph.nodes))

#Calculate new PageRank
def update_pagerank(self, d, n):
  in_neighbors = self.parents
  pagerank_sum = sum((node.pagerank / len(node.children)) for node in in_neighbors)
  random_walk = d / n
  self.pagerank = random_walk + (1-d) * pagerank_sum

參考資料:PageRank: Link Analysis Explanation and Python Implementation from Scratch

用JavaScript實現PageRank

Matrix.prototype.row_stochastic = function(damping_factor) {
 
    var row_length = this.elements[0].length;
    var d = (1 - damping_factor) / row_length;
 
    var row_total = [];
 
    for (var x = 0; x < row_length; x++) {
        row_total.push(0);
        for (y = 0; y < row_length; y++) {
            row_total[x] += this.elements[x][y];
        }
    }
 
    var a1 = this.elements.clone();
 
    for (var x = 0; x < row_length; x++) {
        for (var y = 0; y < row_length; y++) {
            if (row_total[x] > 0) {
                a1[x][y] = a1[x][y]/row_total[x] + d;
            }
            else {
                a1[x][y] = (1/row_length) + d;
            }
        }
    }
 
    return $M(a1);
 
}

參考資料:PageRank Explained with Javascript


上一篇
Day27:質數判定法(Primality Test)
下一篇
Day29:輾轉相除法(Euclidean algorithm)
系列文
一個月的演算法挑戰30

尚未有邦友留言

立即登入留言