請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9606
標題: | 利用網路中的強連結單元計算個人化網頁排序 Computing Personalized PageRank Using Strongly Connected Components in Web |
作者: | Rung-Guo Tzeng 曾榮國 |
指導教授: | 陳銘憲(Ming-Syan Chen) |
共同指導教授: | 鄭士康(Shyh-Kang Jeng) |
關鍵字: | 演算法,搜尋引擎,鏈結分析,線性系統,網頁排序, Algorithm,Search Engine,Linkage Analysis,Linear System,PageRank, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | 網頁排序是搜尋引擎中一項重要的排序技術。藉由不同的個人化向量,搜尋引擎公司可以為不同群組的使用者計算出特殊及適合的網頁排序向量。然而,僅計算單一網頁排序向量便需花費許多時間。為了解決這個問題,我們提出了SCC (Strongly Connected Component)網頁排序演算法。SCC 網頁排序演算法的主要精神在於利用舊的網頁排序向量推導出新的網頁排序向量。我們將網頁排序模組中原先的線性系統拆解為線性子系統。利用這些線性子系統間的相依關係,我們將原本的計算轉變為階層式架構。在計算個人化網頁排序向量時,我們檢查重覆計算的必要性。因此,我們可以避免一些迭代的重覆計算並達到效能上的改進。根據我們的實驗成果顯示,在計算諸多個人化網頁排序向量時,SCC 網頁排序演算法的表現在許多情況下可優於已知的加速演算法。 PageRank is an important ranking technique used in search engines. By using different personalization vectors, search engine companies can compute specific and adaptive PageRank vectors for different classes of users. However, computing even one PageRank vector consumes a lot of time. To address this problem, we propose the SCC (Strongly Connected Component) PageRank algorithm. The main spirit of SCC PageRank is utilizing the old PageRank vector to deduce the new one. We decompose the original linear system of PageRank model into linear subsystems. By using the dependency relation between these linear subsystems, we translate the original computation into a hierarchical manner. While computing personalized PageRank vectors, we check the necessity of recomputation. Thus, we can prevent some iterative recomputations and achieve an improvement of efficiency. As shown by our experimental results, while computing several personalized PageRank vectors, SCC PageRank performs better than the known accelerating algorithms in most cases. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9606 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf | 1 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。