先跟版主還有板友們說聲抱歉啊 這不是學校作業啦(囧),只是想研究看看啊 我大致上了解PageRank的演算法啦: PR(pi) = (1-d)/N + Σ( PR(pj)/L(pj) ) PR(pi)為目標網頁i的PR值 PR(pj)為具有指向網頁i連結的網頁j的PR值 L(pj)為網頁j中超連結的數目 N為網頁總數 d為隨機瀏覽的機率,一般設定為0.85 不過在實作上就碰到了滿多困難,例如如何parse之前所講到的紀錄所有連結資訊的txt檔 然後把對所一網頁的inLink outLink資訊作儲存,才有辦法算PageRank 因為八月才開始學java的關係,在寫比較長的程式碼時會碰到很多問題 於是之後找到了一個Package-WebLA http://webla.sourceforge.net/ 首頁 http://webla.sourceforge.net/javadocs/ API documentation 其中包含了許多Link Analysis的演算法如PageRank'HITS和SimRank等等 比較重要的是WebGraph這個Class,可以parse文件檔然後儲存連結資訊 雖然裡面寫的輸入格式跟我現有的資料格式不同,不過在修改和測試後也可以使用了 目前的問題就卡在另一個Class-PageRank上面了 其中的方法PageRank: public Double pageRank(String link) 輸入參數為目標網址,會傳回該網只在計算過後的PR值 計算了手邊紀錄了數十萬筆連結資訊的txt檔後(記憶體加到1G才有辦法算) 出現了以下問題(連結資訊格式為url1 -> url2): 1.出現在右邊的連結(如上一行的url2),傳回值全都會是Infinity 2.出現在左邊的連結(如上一行的url1),傳回值幾乎全部一樣(PR值完全相同, 小部分不相同) 想說應該是計算PR值的方法出了問題吧,但是又一直找不出來問題在哪 因此想麻煩各位大大幫我看看是哪邊寫錯了 謝謝 public void computePagerank(int iter) //iter為重複計算次數 { int n=graph.numNodes(); //WebGraph的方法 numNodes(),傳回總節點(網頁)數 double aux = (1-dampening)/n; //dampening即為d,隨機瀏覽機率(0.85) while((iter--)>0) { Map newScore = new HashMap(); for (int j=0;j<n;j++) { Map inlinks = graph.inLinks(new Integer(j)); //inLinks方法傳回參數型態為map,紀錄所有具有連向網頁pj超連結的網頁url Iterator it = inlinks.keySet().iterator(); Double weight2 = new Double(0); while (it.hasNext()) { Integer link = (Integer)(it.next()); Double weight = (Double)(inlinks.get(link)); if(weight!=null && weight.doubleValue()>0) { int numLinks = 0; Map outlinks = graph.outLinks(link); Iterator it2 = inlinks.keySet().iterator(); while (it.hasNext()) { Integer l = (Integer)(it.next()); Double w = (Double)(outlinks.get(l)); if(w!=null && w.doubleValue()>0) numLinks++; } weight2 = new Double(weight2.doubleValue() + (((Double)(scores.get(link))).doubleValue()/numLinks)); } } weight2 = new Double(aux + dampening*weight2.doubleValue()); newScore.put(new Integer(j),weight2); } for (int j=0;j<n;j++) { scores.put(new Integer(j),(Double)(newScore.get(new Integer(j)))); } } } 整個程式碼太長了所以貼我覺得有問題的部分 如果有需要再把其他部分也貼出來,或是上面網頁也有程式碼可以下載 先謝謝大家了 ※ 引述《willieliao (Willie Liao)》之銘言： : ※ 引述《kians (臨兵鬥者皆陣列在前)》之銘言： : : 如題,Google利用頁面分析+PageRank技術達成了搜尋引擎霸主的地位 : : PageRank就是給予每一個網頁一個value啦,用google自己發展的PageRank演算法 : : 用在搜尋後的網頁排序,越重要的網頁會放在越前面 : : 最近對PageRank滿有興趣的,要如何讓電腦對數以億計的網頁進行運算 : : 一般的電腦根本不可能達成吧,有點想知道演算法是怎麼寫的 : : 還是說關鍵在硬體? 用multiprocess的方式達成? : GOOG是用分散式運算 : : 有人用java寫過PageRank的演算法嘛? : 單純回答你的問題，有（舉手） : 這是我在CARNEGIE MELLON CS大二資料結構的第三還是第四個作業，兩周要寫出來， : 而且包括CRAWLER（讀取網頁並TOKENIZE），INDEXER﹛讓USER搜尋關鍵字），和PAGE : RANKING。我是用JAVA寫的，據說GOOGLE是用RUBY寫的，不過還請板上強者補充。 : 這裡是我的作業的CLASS DIAGRAM，看看是不是你想要的 : http://www.willieliao.com/ooad/src/default.dfPackage.wmf : : 希望能找到範例來參考一下,想對手邊有的幾十萬筆的連結資訊算出所有url的PageRank值 : : (格式(txt): url1->url2 : : url1->url3 : : url2->url3 : : . : : . : : . ) : : 不知道有沒有辦法辦到,先謝謝各位囉 : 既然你只要算PAGERANK，那左邊都不用管，建一個HASHMAP，對每一個右邊的 : URL先去看看MAP裡面有沒有，沒有的話用URL當KEY（假設你是STRING），用一個 : INTEGER HOLDER當DATA丟進去，KEY存在的話就把DATA的VALUE 加一 : 話說我怎麼聞到作業文的味道... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.230.201.125