Algorithms for estimating relative importance in networks

ABSTRACT

Large and complex graphs representing relationships among sets of entities are an increasingly common focus of interest in data analysis---examples include social networks, Web graphs, telecommunication networks, and biological networks. In interactive analysis of such data a natural query is "which entities are most important in the network relative to a particular individual or set of individuals?" We investigate the problem of answering such queries in this paper, focusing in particular on defining and computing the importance of nodes in a graph relative to one or more root nodes. We define a general framework and a number of different algorithms, building on ideas from social networks, graph theory, Markov models, and Web graph analysis. We experimentally evaluate the different properties of these algorithms on toy graphs and demonstrate how our approach can be used to study relative importance in real-world networks including a network of interactions among September 11th terrorists, a network of collaborative research in biotechnology among companies and universities, and a network of co-authorship relationships among computer science researchers.

REFERENCES

• 1: Allan Borodin , Gareth O. Roberts , Jeffrey S. Rosenthal , Panayiotis Tsaparas, Finding authorities and hubs from link structures on the World Wide Web, Proceedings of the 10th international conference on World Wide Web, p.415-429, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372096]
• 2: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 3: Huan Chang , David Cohn , Andrew McCallum, Learning to Create Customized Authority Lists, Proceedings of the Seventeenth International Conference on Machine Learning, p.127-134, June 29-July 02, 2000
• 4: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: Freeman, L. (1979) Centrality in social networks: I. conceptual clarification. Social Networks, 1, pp. 215--239.
• 6: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 7: Hoff, P. D., Raftery, A. E. Handcock, M. S. (2002) Latent space approaches to social network analysis. Journal of The American Statistical Association, 97, pp. 1090--1098.
• 8: Jeh, G. and Widom J. (2002) Scaling personalized Web search. Stanford University, Computer Science Department Technical Report.
• 9: Katz, L. (1953) A new status index derived from sociometric analysis. Psychometrika, 18, pp. 39--43.
• 10: Kemeny, J. and Snell, J. (1976) Finite Markov Chains. Springer Verlag.
• 11: 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]
• 12: Krebs, V. E. (2001) Mapping networks of terrorist cells. Connections, 24(3), pp. 43--52.
• 13: Steve Lawrence , C. Lee Giles , Kurt Bollacker, Digital Libraries and Autonomous Citation Indexing, Computer, v.32 n.6, p.67-71, June 1999 [doi>10.1109/2.769447]
• 14: R. Lempel , S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.387-401, June 2000, Amsterdam, The Netherlands
• 15: Page, L., Brin, S., Motwani, R., Winograd, T. (1998) The PageRank citation ranking: bringing order to the web. Stanford University, Computer Science Department Technical Report.
• 16: Powell, W. W., White, D. R., Koput, K. W., and Owen-Smith, J. (2002) Network dynamics and field evolution: the growth of interorganizational collaboration in the life sciences. Submitted.
• 17: Stephenson, K., and Zelen, M. (1989) Rethinking centrality: methods and examples. Social Networks, 11, pp. 1--37.
• 18: Wasserman, S., and Faust, K. (1994) Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Keywords:
Markov chains, PageRank, graphs, relative importance, social networks