nach oben

Discover Computing

Erschienen in:

01.10.2011

Page importance computation based on Markov processes

verfasst von: Bin Gao, Tie-Yan Liu, Yuting Liu, Taifeng Wang, Zhi-Ming Ma, Hang Li

Erschienen in: Discover Computing | Ausgabe 5/2011

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Improving document clustering using Okapi BM25 feature weighting

Nächster Artikel Blog feed search with a post index

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

According to recent study, US companies paid a record $14.2 billion for paid keyword-driven contextual ads in 2009. Meanwhile, click fraud rates rose to 17.4 to 29.4% in the first 3 months of 2010. That is, we will observe a great number of transitions from the content pages (e.g., blogs and forums) to the landing pages of the click fraud ads. cf. http://lastwatchdog.com/botnet-driven-click-fraud-steals-millions-advertisers/

It can also be called as the skeleton process of the Web Markov Skeleton Process.

In some algorithms, the random surfer sometimes does not follow the edges but performs random resets. In such case, we regard the graph as containing virtual edges corresponding to the resets.

Note that we briefly discussed BrowseRank Plus in a short paper (Gao et al. 2009).

Lattice distribution is a discrete distribution of a random variable such that every possible value can be represented in the form a + bn, where a, b ≠ 0 and n is an integer.

Note that we briefly discussed MobileRank in a short paper (Gao et al. 2009).

For privacy consideration, we do not list the name of this website in the paper.

Berberich, K., Vazirgiannis, M., & Weikum, G. (2004). Time-aware authority ranking. In Algorithms and Models for the Web-Graph: Third International Workshop, WAW’04 (pp. 131–141). Springer.

Bianchini, M., Gori, M., & Scarselli, F. (2005). Inside pagerank. ACM Transactions on Interet Technology, 5(1), 92–128.CrossRef

Boldi, P., Santini, M., & Vigna, S. (2005). Pagerank as a function of the damping factor. In WWW ’05. ACM.

Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7), 107–117.

Chen, Z., Tao, L., Wang, J., Liu, W., & Ma, W. (2002). A unified framework for web link analysis. In WISE’02.

Ding, C., He, X., Husbands, P., Zha, H., & Simon, H. (2001). PageRank, HITS, and a unified framework link analysis. LBNL Tech Report 49372, Nov 2001 (updated September 2002).

Golub, G. H., & Loan, C. F. V. (1996). Matrix computations (3rd ed.). Baltimore, MD, USA: Johns Hopkins University Press.MATH

Gao, B., Liu, T., Ma, Z., Wang, T., & Li, H. (2009). A general markov framework for page importance computation. In the Proceedings of the 18th ACM conference on information and knowledge management (CIKM 2009) (pp. 1835–1838).

Gyongyi, Z., & Garcia-Molina, H. (2004). Web spam Taxonomy. Technical report, Stanford Digital Library Technologies Project.

Gyongyi, Z., Garcia-Molina, H., & Pedersen, J. (2004). Combating web spam with trustrank. In VLDB ’04 (pp. 576–587). VLDB Endowment.

Haveliwala, T. (1999). Efficient computation of pageRank. Technical Report 1999–31.

Haveliwala, T., & Kamvar, S. (2003). The second eigenvalue of the google matrix.

Haveliwala, T., Kamvar, S., & Jeh, G. (2003). An analytical comparison of approaches to personalizing pagerank.

Haveliwala, T. H. (May 2002). Topic-sensitive pagerank. In WWW ’02, Honolulu, Hawaii.

Hou, Z., & Liu, G. (2005). Markov Skeleton processes and their applications. USA: Science Press and International Press

Hou, Z., Liu, Z., & Zou, J. (June 1998). Markov Skeleton Processes. Chinese Science Bulletin, 43(11), 881–889.

Jeh, G., Widom, J. (2002). SimRank: A measure of structural-context similarity. In KDD ’02.

Jindal, A., Crutchfield, C., Goel, S., Kolluri, R., & Jain, R. (2008). The mobile web is structurally different. In the Proceedings of the 11th IEEE global internet symposium.

Kleinberg, J. M. (1998). Authoritative sources in a hyperlinked environment. In SODA ’98 (pp. 668–677). Philadelphia, PA, USA: Society for Industrial and Applied Mathematics.

Langville, A. N., & Meyer, C. D. (2004). Deeper inside pagerank. Internet Mathematics, 1(3), 335–400.MathSciNetMATHCrossRef

Liu, Y., Gao, B., Liu, T., Zhang, Y., Ma, Z., He, S., et al. (2008). BrowseRank: Letting users vote for page importance. In SIGIR ’08 (pp. 451–458).

McSherry, F. (2005). A uniform approach to accelerated pagerank computation. In WWW ’05 (pp. 575–582). New York, NY, USA: ACM.

Nie, Z., Zhang, Y., Wen, J., & Ma, W. (2005). Object-level ranking: Bringing order to web objects. In WWW’05.

Page, L., Brin, S., Motwani, R., & Winograd, T. (1998). The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project.

Papoulis, A., & Pillai, S. U. (2001). Probability, random variables and stochastic processes. New York: McGraw-Hill Science/Engineering/Math.

Poblete, B., Castillo, C., & Gionis, A. (2008). Dr. Searcher and Mr. Browser: A unified hyperlink-click graph. In CIKM ’08: Proceeding of the 17th ACM conference on information and knowledge mining (pp. 1123–1132).

Richardson, M., & Domingos, P. (2002). The intelligent surfer: Probabilistic combination of link and content information in PageRank. In Advances in neural information processing systems 14. Cambridge: MIT Press.

Yu, P. S., Li, X., & Liu, B. (2005). Adding the temporal dimension to search—A case study in publication search. Proceedings of the 2005 IEEE/WIC/ACM international conference on web intelligence.

Titel: Page importance computation based on Markov processes
verfasst von: Bin Gao
Tie-Yan Liu
Yuting Liu
Taifeng Wang
Zhi-Ming Ma
Hang Li
Publikationsdatum: 01.10.2011
Verlag: Springer Netherlands
Erschienen in: Discover Computing / Ausgabe 5/2011
Print ISSN: 2948-2984
Elektronische ISSN: 2948-2992
DOI: https://doi.org/10.1007/s10791-011-9164-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"