Systems and methods for ranking nodes of a graph using random parameters
View Patent ↗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 wherein the vector represents a probability distribution on the nodes of the graph and can solve a linear system;
using a probability matrix function based upon a Markov chain on the graph and relative to the nodes of the graph to assess statistics of the vector for solving a probability-based system that is based on the vector and based on a non-deterministic variable; and
ranking the nodes of the graph based upon the assessed statistics of the vector.
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, covariance matrix, a probability density function, and cumulative distribution function, the function of finite moments of the vector including at least one of expectation and standard deviation, wherein the non-deterministic variable is used for ranking the nodes of 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 represented based on the nodes 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 relating to proteins.
10. The method of claim 1 , wherein the nodes of the graph are indicative of parameters relating to 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 , wherein the steps involve modeling with the vector as a random variable distributed according to user behavior for multiple users.
13. The method of claim 1 , wherein the steps involve 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 , wherein the steps involve computing the expectation and standard deviation of the nodes.
15. The method of claim 1 , wherein the vector models an underlying user population associated with the nodes.
16. The method of claim 15 , wherein the steps involve quantifying an importance of one of the nodes as a function of the vector.
17. The method of claim 1 , wherein the steps involve using a standard deviation associated with the graph to generate rankings that are uncorrelated with the vector.
18. The method of claim 17 , wherein the uncorrelated rankings are used for a machine learning framework to generate a search ranking function.
19. The method of claim 1 , wherein the steps involve 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.
20. The method of claim 1 , wherein the steps of providing a vector and using a probability matrix function to assess the statistics of the vector include executing stored computer executable code with a computer to perform the steps.
21. The method of claim 1 , further including storing, in a data storage medium, results based on the assessed statistics.
22. The method of claim 1 , further including storing, in a data storage medium, parameters indicative of the random parameters.
23. The method of claim 1 , further including using a data storage medium for accessing data useful for the steps of providing a vector and using a probability matrix function to assess the statistics of the vector.
24. The method of claim 1 , wherein
providing a vector includes providing a non-deterministic vector for solving a linear system, and
the linear system is based upon an adjusted transition probability matrix of a Markov chain on the graph, a random variable, and a probability distribution on the nodes of the graph.
25. The method of claim 1 , wherein the vector is characterized in that it can solve the probability-based system in which a vector x that solves a linear system (1−αP)x =(1−α)v, in which
P is the probability matrix function,
v is the vector, and
the parameter α is the non-deterministic variable.
26. The method of claim 1 , wherein the vector for solving the probability-based system is a stochastic vector x that solves a linear system (1−αP)x =(1−α)v, in which
P is the probability matrix function,
the vector v is a function of the probability matrix function, and
the parameter α is a constant.
27. 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 wherein the vector represents a probability distribution on the nodes of the graph and can solve a linear system, and
use a probability matrix function based upon a Markov chain on the graph and relative to the nodes of the graph to assess statistics of the vector for solving a probability-based system that is based on the vector and based on a non-deterministic variable; and
rank the nodes of the graph based upon the assessed statistics of the vector.
28. The method of claim 25 , in which the parameter a describes the probability of a web surfer that at least one of:
follows the links of a web page uniformly at random, and
jumps to a different page according to a given probability distribution over web pages.
29. The system of claim 27 , wherein
the computer circuit is configured and arranged to provide the vector by providing a non-deterministic vector that solves a linear system, and
the linear system is based upon an adjusted transition probability matrix of a Markov chain on the graph, a random variable, and a probability distribution on the nodes of the graph.
30. The system of claim 27 , wherein the computer circuit is configured and arranged to provide the vector that solves the probability-based system by providing a vector x that solves a linear system (1−αP)x =(1−α)v, in which
P is the probability matrix function,
the vector is v, and
the parameter α is the non-deterministic variable.