Page importance computation based on Markov processes
文献类型：期刊论文
| 作者 | Gao, Bin1; Liu, Tie-Yan1; Liu, Yuting2; Wang, Taifeng1; Ma, Zhi-Ming3 ; Li, Hang1
|
| 刊名 | INFORMATION RETRIEVAL
 |
| 出版日期 | 2011-10-01 |
| 卷号 | 14期号:5页码:488-514 |
| 关键词 | Page importance PageRank BrowseRank Web Markov skeleton process Mirror semi-Markov process |
| ISSN号 | 1386-4564 |
| DOI | 10.1007/s10791-011-9164-x |
| 英文摘要 | This paper is concerned with Markov processes for computing page importance. Page importance is a key factor in Web search. Many algorithms such as PageRank and its variations have been proposed for computing the quantity in different scenarios, using different data sources, and with different assumptions. Then a question arises, as to whether these algorithms can be explained in a unified way, and whether there is a general guideline to design new algorithms for new scenarios. In order to answer these questions, we introduce a General Markov Framework in this paper. Under the framework, a Web Markov Skeleton Process is used to model the random walk conducted by the web surfer on a given graph. Page importance is then defined as the product of two factors: page reachability, the average possibility that the surfer arrives at the page, and page utility, the average value that the page gives to the surfer in a single visit. These two factors can be computed as the stationary probability distribution of the corresponding embedded Markov chain and the mean staying time on each page of the Web Markov Skeleton Process respectively. We show that this general framework can cover many existing algorithms including PageRank, TrustRank, and BrowseRank as its special cases. We also show that the framework can help us design new algorithms to handle more complex problems, by constructing graphs from new data sources, employing new family members of the Web Markov Skeleton Process, and using new methods to estimate these two factors. In particular, we demonstrate the use of the framework with the exploitation of a new process, named Mirror Semi-Markov Process. In the new process, the staying time on a page, as a random variable, is assumed to be dependent on both the current page and its inlink pages. Our experimental results on both the user browsing graph and the mobile web graph validate that the Mirror Semi-Markov Process is more effective than previous models in several tasks, even when there are web spams and when the assumption on preferential attachment does not hold. |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000294960300003 |
| 出版者 | SPRINGER |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/11270]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Gao, Bin |
| 作者单位 | 1.Microsoft Res Asia, Sigma Ctr, Beijing 100190, Peoples R China 2.Beijing Jiaotong Univ, Beijing 100044, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China |
| 推荐引用方式 GB/T 7714 | Gao, Bin,Liu, Tie-Yan,Liu, Yuting,et al. Page importance computation based on Markov processes[J]. INFORMATION RETRIEVAL,2011,14(5):488-514. |
| APA | Gao, Bin,Liu, Tie-Yan,Liu, Yuting,Wang, Taifeng,Ma, Zhi-Ming,&Li, Hang.(2011).Page importance computation based on Markov processes.INFORMATION RETRIEVAL,14(5),488-514. |
| MLA | Gao, Bin,et al."Page importance computation based on Markov processes".INFORMATION RETRIEVAL 14.5(2011):488-514. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。