Node ranking in labeled directed graphs

ABSTRACT

Our work is motivated by the problem of ranking hyper-linked documents for a given query. Given an arbitrary directed graph with edge and node labels, we present a new flow-based model and an efficient method to dynamically rank the nodes of this graph with respect to any of the original labels. Ranking documents for a given query in a hyper-linked document set and ranking of authors/articles for a given topic in a citation database are some typical applications of our method. We outline the structural conditions that the graph must satisfy for our ranking to be different from the traditional <i>PageRank</i>.

We have built a system using two indices that is capable of dynamically ranking documents for any given query. We validate our system and method using experiments on a few datasets: a crawl of the IBM Intranet (12 million pages), a crawl of the <b>www</b> (30 million pages) and the DBLP citation dataset. We compare our method to existing schemes for topic-biased ranking that require a classifier and the traditional <i>PageRank</i>. In these experiments, we demonstrate that our method is well suited for fine-grained ranking and that our method performs better than the existing schemes. We also demonstrate that our system can obtain an improved ranking with very little impact on query time.

REFERENCES

• 1: E. Amitay, D. Carmel, A. Darlow, M. Herscovici, A. S. L. Lempel, R. Kraft, and J. Zien. Juru at trec 2003 - topic distillation using query-sensitive tuning and cohesiveness filtering. In Proceedings of The Twelfth Text Retrieval Conference (TREC 2003), Gaithersburg, Maryland, USA, 2003.
• 2: G. Bhalotia, C. Nakhe, A. Hulgeri, S. Chakrabarti, and S. Sudarshan. Keyword searching and browsing in databases using BANKS. In ICDE, 2002.
• 3: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 4: P. Bonacich. Power and centrality: A family of measures. American Journal of Sociology, 92, 1987.
• 5: S. Brin, R. Motwani, L. Page, and T. Winograd. What can you do with a web in your pocket? Data Engineering Bulletin, 21(2):37--47, 1998.
• 6: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 7: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
• 8: Soumen Chakrabarti , Byron E. Dom , S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins , David Gibson , Jon Kleinberg, Mining the Web's Link Structure, Computer, v.32 n.8, p.60-67, August 1999 [doi>10.1109/2.781636 ]
• 9: N. E. Friedkin. Theoretical foundations for centrality measures. American Journal of Sociology, 96(6):1478--1504, 1991.
• 10: T. Haveliwala. Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. IEEE Transactions on Knowledge and Data Engineering, July/Aug 2003.
• 11: Monika R. Henzinger, Hyperlink Analysis for the Web, IEEE Internet Computing, v.5 n.1, p.45-50, January 2001 [doi>10.1109/4236.895141 ]
• 12: C. Hubbell. An input-output approach to clique identification. Sociometry, 28, 1965.
• 13: L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18, 1953.
• 14: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 15: Massimo Marchiori, The quest for correct information on the Web: hyper search engines, Selected papers from the sixth international conference on World Wide Web, p.1225-1235, September 1997, Santa Clara, California, United States
• 16: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 17: G. Pinski and F. Narin. Citation influence for journal aggregates of scientific publications: Theory, with application to the literature of physics. Information Processing and Management, 12:297--312, 1976.
• 18: Davood Rafiei , Alberto O. Mendelzon, What is this page known for? Computing Web page reputations, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.823-835, June 2000, Amsterdam, The Netherlands
• 19: John A. Tomlin, A new paradigm for ranking pages on the world wide web, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775202]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Experimentation, Theory

Keywords:
citation graph, context-sensitive ranking, flow-based, intranet search, link structure, model, pagerank, random surfer model, search, search in context, web graph