Applying probabilistic model for ranking Webs in multi-context
Main Article Content
Abstract
The PageRank algorithm, used in the Google search engine, greatly improves the
results o f Web search by applying probabilistic model on the link structure o f Webs to evaluate
the “ importance” o f Webs. In PageRank probabilistic niodel, the links and webs are uniíòrm,
so the rank score o f vvebs are quite independent from their content. In practice, the researchers
often hope that the web results can be ranked by their proposed topics. Moreover, vvhen
computer’s techniques solve given problems ineffectively, it*s necessary to do better research
in theoretical problems. From this judgement, in this paper, we introduce and describe the
MPageRank based on a nevv probabilistic model supporting multi-context for ranking Webs. A
Web now has diíĩerent ranking scores, which depends on the given multi topics. The basic idea
in establishing the new MPageRank model is that partition our Web graph into smaller-size
sub Web graph. As a consequence o f evaluation and rejection about pages iníluence weakly to
other pages, the rank score o f pages o f the original Web graph can be approximated from the
rank score of pages in the nevv partition Web graph. Similar to the PageRank, the multi ranking
scores in the MPageRank are pre-computed and reílect the hyperlink o f Web environment.
References
[2] L. Page, s. Brin, R. Motvvani, T. NVindograd, The PageRank Cilation Ranking: Đring Ordcr to the Web\ Technical
report, Staníòrd Digital Library Technologies Prọịect 1999-0120, 1998.
[3] M. Richardson, p. Domingos, The intelligent suríer: Probabilistic combination of link and contcnt information in
PageRank, In Proceedings o f Advances in Neural Information Processing Systems 14, Cambridgc, Massachusctts, Dcc.
2002.
[ 4 ] T. H a v e l i w a l a , T o p i c - S e n s i t i v e P agcRank, In Proceedings o f the Elevertth International Worỉd Wide Web Conference,
Honolulu, Havvaii, May 2002.
[5| s. Kamvar, T. Havelivvala, c . Manning, G. Golub, Extrapolation mcthods for acceleraling PageRank computations, In
Proceedings o f the Twelfth International World Wide Web Conferencey 2003.
[6 ] s. Kamvar, T. Havelivvala, c . Manning, G. Golub, Expỉoiting the Bỉock Structure o f the Web f o r Computing PageRank%
Stanĩord Univcrsity Technical Report, 2003.
[7] B. Boỉlobâs. Random GraphSy CAMBRIDGE Univcrsity Press, 2001.
[8 | R. Albert, A. Barabâsi, Statistical mcchanics of complex networks, Reviews oỊ Mode rn Physics, Vol 74, January 2002.
[9] D. Callavvay, J. Hopcrort, J. Kleinberg, M. Ncwman, s. Stragatz, Are randomly grown graphs rcally random?, Phys.
Rev. £ 6 4 (2001) 041902.
[10| J. Kleinbcrg, Dctecting a Netvvork Pailurc Proc. 4ỉst Annual IEEE Symposium on Foundations o f Computer Science,
2002.
[11] J. Fakcharoenphol, An Improved VC-Dimension Bound f o r Finding Nehvork Failures% Master’s thcsis, u . c . Berkeley,
2001
[ 1 2 ] F. Ch u n g, L a p l a c i a n s and thc C h c e g c r i n c q u a l i t y f o r d i r ec l ed graphs, Annals o f Combinaỉorics, 2002.
[13] F. Chung, Spectral Graph Theory, American Mathcmatical Society, No.92 in the Regional Conĩcrcnce Serics in Malh-
cmatics, Providcnce, RI, 1997.
[14] VVilliam Fellcr. An Introduction to Probability Theory and Its Applications. Vol. 1, 3rđ eđ. John Wiley & Sons, Inc.
Ncvv York, 1968.
[15] p. Baldi, p. Frasconi, p. Smyth, Modeling the Internet and the Web, John Wilcy & Sons, Inc. Ncw York, 2003.
116] Le T r u n g K i e n , The probabilitic models f o r ranking Webs% G r a d u a t e ’ s thes i s, H u e U n i v e r s i t y o f Sciences, M a y 2005.