Systems and methods for ranking nodes of a graph using random parameters

Abstract

A ranking approach is used to determine rank-based relationships. In connection with various embodiments, the present invention is directed to a method for ranking nodes of a graph. A vector is provided as a function of a set of random parameters, and a probability matrix function is used, relative to nodes of the graph, to assess the statistics of the vector that solves a probability-based system. Certain embodiments are directed to determining a page rank for a web-based search.

1 . A circuit-based method for ranking nodes of a graph, comprising:
 providing a vector, in the form of a signal to a circuit, as a function of a set of random parameters; and   using a probability matrix function based on a Markov chain and relative to nodes of the graph to assess statistics of the vector that solves a probability-based system as a function of the vector and a non-deterministic variable.   
     
     
         2 . The method of  claim 1 , wherein the statistics of the vector include at least one of the following: a function of finite moments of the vector including expectation or standard deviation, covariance matrix, a probability density function, and cumulative distribution function, wherein the non-deterministic variable is used for ranking nodes on the graph. 
     
     
         3 . The method of  claim 1 , wherein the probability matrix function includes a linear system partly defined as a function of an adjusted transition probability matrix of the Markov chain on the graph. 
     
     
         4 . The method of  claim 3 , wherein the linear system is further defined as a function of a probability distribution on the nodes of the graph. 
     
     
         5 . The method of  claim 3 , wherein the linear system is further defined as a function of a random variable. 
     
     
         6 . The method of  claim 1 , wherein the nodes of the graph are indicative of parameters relating to web pages. 
     
     
         7 . The method of  claim 1 , wherein the nodes of the graph are indicative of parameters relating to web-based spam data sets. 
     
     
         8 . The method of  claim 1 , wherein the nodes of the graph are indicative of parameters relating to genes. 
     
     
         9 . The method of  claim 1 , wherein the nodes of the graph are indicative of parameters that represent proteins. 
     
     
         10 . The method of  claim 1 , wherein the nodes of the graph are indicative of parameters that represent graph isomorphisms. 
     
     
         11 . The method of  claim 1 , wherein the system is a linear system, and the vector is used to solve the system based on a stochastic interpretation of at least part of the linear system. 
     
     
         12 . The method of  claim 1 , including the step of modeling with the vector as a random variable distributed according to user behavior for multiple users. 
     
     
         13 . The method of  claim 1 , including the step of quantifying a degree of uncertainty in the vector using at least one of a Monte Carlo sampling algorithm, an algorithm that uses truncated polynomial chaos expansion of the random parameters, an algorithm based on path damping coefficients, and a quadrature approximation. 
     
     
         14 . The method of  claim 1 , including the step of computing the expectation and standard deviation of the nodes. 
     
     
         15 . The method of  claim 1 , wherein the vector represents the underlying user population associated with the nodes, and including quantifying a degree of importance of one of the nodes as a function of the vector. 
     
     
         16 . The method of  claim 1 , including the step of using a standard deviation associated with the graph to generate rankings that are uncorrelated with the vector, and wherein the uncorrelated rankings are used for a machine learning framework to generate a search ranking function. 
     
     
         17 . The method of  claim 1 , including algorithmically computing the statistics of the vector based respectively on at least one of the following: (i) random sampling, (ii) paths along the links of the underlying graph, (iii) a spectral expansion of the vector, and (iv) quadrature formulas; and including using the probability matrix function to assess the statistics of the vector include executing stored computer executable code with a computer to perform the steps. 
     
     
         18 . A computer-based system for ranking nodes of a graph, the system comprising
 a computer circuit configured with software to
 provide a vector as a function of a set of random parameters, and 
 use a probability matrix function based on a Markov chain and relative to nodes of the graph to assess the statistics of the vector that solves a probability-based system as a function of the vector and a non-deterministic variable. 
   
     
     
         19 . The system of  claim 18 , wherein the statistics of the vector include at least one of the following: a function of finite moments of the vector including expectation or standard deviation, covariance matrix, a probability density function, and cumulative distribution function, wherein the non-deterministic variable is used for ranking nodes on the graph. 
     
     
         20 . The system of  claim 18 , wherein the probability matrix function includes a linear system partly defined as a function of an adjusted transition probability matrix of the Markov chain on the graph.