Calculating Web Page Importance
AssigneeMicrosoft Corporation
InventorsBin Gao, Tie-Yan Liu
Life of this patent
Estimating the term…
Abstract
The page ranking technique described herein employs a Markov Skeleton Mirror Process (MSMP), which is a particular case of Markov Skeleton Processes, to model and calculate page importance scores. Given a web graph and its metadata, the technique builds an MSMP model on the web graph. It first estimates the stationary distribution of a EMC and views it as transition probability. It next computes the mean staying time using the metadata. Finally, it calculates the product of transition probability and mean staying time, which is actually the stationary distribution of MSMP. This is regarded as page importance.
Claims20
A computer-implemented process for calculating page importance of a page on a mobile website, comprising:
- inputting a web graph and its associated metadata;
- building a Mirror Semi-Markov Process Model (MSMP) using the input web graph;
- based on a transition probability matrix extracted from the web graph, computing a stationary distribution of an Embedded Markov Chain associated with the MSMP;
- computing a mean staying time of a random web surfer on a web page;
- and
- calculating a product of the transition probability and mean staying time as the page importance.
A computer-implemented process for calculating page importance of a page on a mobile website, comprising,
- using a computer for,
- generating a transition probability matrix of an Embedded Markov Chain associated with a Mirror Semi-Markov Process and a mobile graph;
- calculating a stationary distribution of the Embedded Markov Chain;
- for each page j of the mobile graph, extracting the number of inlink websites mi and the number of inlink pages, njk;
- for each inlink page in the kth website of the mobile graph, extracting the outlink number ojkl, to compute a contribution probability of a web surfer coming from the kth website;
- for each page of the mobile website, setting the exponential distribution of the average staying time on a page;
- calculating the expectation of staying time for each page using the calculated contribution probabilities and exponential distribution of the average staying time;
- computing the page importance scores for the mobile graph using the expectation of staying time for all pages and the stationary distribution.
A system for determining web page importance, comprising:
- a general purpose computing device;
- a computer program comprising program modules executable by the general purpose computing device, wherein the computing device is directed by the program modules of the computer program to,
- input a web graph and associated metadata;
- create a Mirror Semi-Markov Process Model (MSMP) that depends on a previous state and a current state of the web graph;
- compute an Embedded Markov Chain associated with the web graph and associated meta data;
- using the Embedded Markov Chain to compute a transition probability;
- computing a mean staying time using the metadata or the web graph;
- computing the page importance as the product of the transition probability and the mean staying time.
Dependencies are inferred from the claim text.