Methods and apparatus for ranking a node in a network having a plurality of interconnecting nodes
First Claim
1. A method of ranking a node within a network of a plurality of interconnected nodes, each node having a connection with at least one other node in the network, the method including the steps of:
- constructing a representation matrix, wherein each element of the representation matrix represents the connection between each of the interconnected nodes;
obtaining a flow matrix by multiplying the representation matrix by itself, wherein each element of the flow matrix represents a flow dimension of the respective node;
calculating flow capacity of each node based on the flow dimension, wherein the flow capacity of each node represents the number of connections to a particular node versus the distance or number of node interconnections required to access said particular node from all other nodes of the network; and
ranking each node according to its respective flow capacity.
1 Assignment
0 Petitions
Accused Products
Abstract
PageRank (PR) is used by web search engine Google in ranking individual web pages. However, it is known that this value is also easily manipulated by methods known as spoofing. Further, the calculation of PR will require iterative cycles of computations to achieve a “steady” value. This would mean that huge computation resources are required to obtain reasonably reliable PR values for various web pages. This invention provides relatively accurate and simple methods for ranking the importance of a node in a network. The web graph or the network is first represented by an incidence matrix or a representation matrix W. The matrix W is then self-multiplied to obtain flow matrix. The flow capacity, or the rank of each node, is then obtained from the flow matrix.
-
Citations
12 Claims
-
1. A method of ranking a node within a network of a plurality of interconnected nodes, each node having a connection with at least one other node in the network, the method including the steps of:
-
constructing a representation matrix, wherein each element of the representation matrix represents the connection between each of the interconnected nodes; obtaining a flow matrix by multiplying the representation matrix by itself, wherein each element of the flow matrix represents a flow dimension of the respective node; calculating flow capacity of each node based on the flow dimension, wherein the flow capacity of each node represents the number of connections to a particular node versus the distance or number of node interconnections required to access said particular node from all other nodes of the network; and ranking each node according to its respective flow capacity. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. An apparatus for ranking a node within a network of a plurality of interconnected nodes, each node having a connection to at least one of other nodes in the network, the apparatus including a processor and an algorithm operating according to the steps of:
-
constructing a representation matrix, wherein each element of the representation matrix represents the connection between each of the interconnected nodes; obtaining a flow matrix by multiplying the representation matrix by itself, wherein each element of the flow matrix represents a flow dimension of the respective node; calculating flow capacity of each node based on the flow dimension, wherein the flow capacity of each node represents the number of connections to a particular node versus distances or number of node interconnections required to access said particular node from all other nodes; and ranking each node according to its respective flow capacity. - View Dependent Claims (8, 9, 10, 11, 12)
-
Specification