Supervised ranking of vertices of a directed graph

Data processing: database and file management or data structures – Database design – Data structure types

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Reexamination Certificate

active

07617194

ABSTRACT:
A method and system for ranking importance of vertices of a directed graph based on links between the vertices and some prior knowledge of importance of the vertices is provided. A ranking system inputs an indication of the vertices along with an indication of the links between the vertices as the directed graph. The ranking system generates a transition-probability matrix that represents the probability of transitioning from vertex to vertex. The ranking system then generates a ranking of the vertices based on the links between the vertices represented by the stationary distribution of the transition-probability matrix that is minimally perturbed to satisfy the prior knowledge, which may be a partial ranking of the vertices.

REFERENCES:
patent: 6285999 (2001-09-01), Page
patent: 6654742 (2003-11-01), Kobayashi et al.
patent: 6839682 (2005-01-01), Blume et al.
patent: 7024404 (2006-04-01), Gerasoulis et al.
patent: 7026029 (2006-04-01), Kamvar et al.
patent: 7089252 (2006-08-01), Tomlin et al.
patent: 7343374 (2008-03-01), Berkhin
patent: 7464075 (2008-12-01), McSherry et al.
patent: 2004/0024752 (2004-02-01), Manber et al.
patent: 2004/0111412 (2004-06-01), Broder
patent: 2005/0071465 (2005-03-01), Zeng et al.
patent: 2005/0216533 (2005-09-01), Berkhin
patent: 2005/0256860 (2005-11-01), Eiron et al.
patent: 2006/0020607 (2006-01-01), Patterson
patent: 2006/0059119 (2006-03-01), Canright et al.
patent: 2006/0074910 (2006-04-01), Yun et al.
patent: 2006/0248059 (2006-11-01), Chi et al.
patent: 2008/0010281 (2008-01-01), Berkhin et al.
patent: 2008/0114750 (2008-05-01), Saxena et al.
Adamic, Leda A. and Bernardo A. Huberman, “Power-Law Distribution of the World Wide Web,” Technical Comment, Science, vol. 287, Mar. 24, 2000, p. 2115a.
Arasu, Arvind et al., “PageRank Computation and the Structure of the Web: Experiments and Algorithms,” 5 pages.
Boyd, Stephen et al., “Chapter 11—Interior-point methods,” Convex Optimization, © Cambridge University Press 2004, pp. 561-622.
Brinkmeier, Michael, “PageRank Revisited,” ACM Transactions on Internet Technology, vol. 6, No. 3, Aug. 2006, © 2006 ACM, pp. 282-301.
Gyongyi, Zoltan, Hector Garcia-Molina and Jan Pedersen, “Combating Web Spam with TrustRank,” Proceedings of the 30th VLDB Conference, Toronto, Canada, 2004, pp. 576-587.
Kamvar, Sepandar D. et al., “Exploiting the Block Structure of the Web for Computing PageRank,” 2003, 13 pages.
Meila, Marina and Jianbo Shi, “Learning Segmentation by Random Walks,” NIPS, 2001, 7 pages.
Ng, Andrew Y., Alice X. Zheng and Michael I. Jordan, “Link Analysis, Eigenvectors and Stability,” IJCAI, 2001, 8 pages.
Page, L. et al., “The PageRank Citation Ranking: Bringing Order to the Web,” Jan. 29, 1998, Stanford University Technical Report, pp. 1-17.
Qin, Tao, Tie-Yan Liu and Wei-Ying Ma, “Supervised Ranking for Directed Graphs,” 21 pages.
Sobek, Markus, “Additional Factors Influencing PageRank,” eFactory, © 2002/2003 eFactory GmbH & Co. KG Internet-Agentur, 7 pages, http://pr.efactory.de/e-further-factors.shtml [last accessed Nov. 16, 2006].
Zhou, Dengyong et al., “Ranking on Data Manifolds,” 2004, 8 pages.
Peer Review for “Supervised Ranking for Directed Graphs,” authors Qin Liu et al.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Supervised ranking of vertices of a directed graph does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Supervised ranking of vertices of a directed graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Supervised ranking of vertices of a directed graph will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-4055762

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.