Patent ID: 7493320

Claim:
A computerized method for ranking documents using link analysis, comprising: describing an original graph with a plurality of nodes and links, where said nodes represent information documents and said links represent pointers from one document to another; forming a metagraph from said original graph by identifying a set of strongly connected components (SCC), replacing each SCC with a metanode, and retaining links between metanodes; determining a gain for each SCC; determining from said metagraph which SCCs are source SCCs; increasing the gain of at least one source SCC by modifying an adjacency matrix representing link weights of the original graph, until the following three conditions are satisfied, thus creating a modified adjacency matrix: (i) all source SCCs whose gain have been increased have a common gain; (ii) the common gain is greater than that of any non-source SCC; and (iii) said common gain is greater than a gain of any source SCC whose gain has not been so increased; determining an importance measure for said plurality of nodes by performing a link analysis of said original graph using said modified adjacency matrix to compute link analysis node weights; ranking two of the plurality of nodes with said importance measure; and one of outputting or displaying a result relating to said importance measure, wherein said step of determining the gain of each SCC comprises, for each SCC: determining a second adjacency matrix representing intra-SCC link weights for a corresponding SCC; and determining a dominant eigenvalue of said adjacency matrix; and setting the gain based on said dominant eigenvalue.