Jon Kleinberg

Assistant Professor
Ph.D. Massachusetts Institute of Technology, 1996

My research is concerned with algorithms that exploit the combinatorial structure of networks and information.

The information we deal with is taking on an increasingly networked

structure; the World Wide Web serves as perhaps the most compelling example of this phenomenon. I have investigated algorithms grounded in spectral graph analysis for locating high-quality information resources in environments like the WWW and for identifying types of “community” structures in the underlying network. I have also been interested in random graph models that can provide insight into the structure of large social networks and have used such a framework, derived from a model of Watts and Strogatz, to study aspects of the “small-world phenomenon.” With Eva Tardos, I have developed algorithms that can use link information to facilitate classification tasks; we have been exploring this approach in the context of computer vision with Yuri Boykov, Olga Veksler, and Ramin Zabih. With Christos Papadimitriou and Prabhakar Raghavan, I have been studying a model of “segmented optimization problems”; this is a computational framework designed to address some of the optimization issues inherent in certain clustering and data mining operations.

Many of the core problems in computational biology require algorithms for analyzing large volumes of data; such data is being generated at an accelerating pace by experimental studies of genomes and proteins across a wide range of species. With Debra Goldberg, Susan McCouch, and David Liben-Nowell, I have been investigating mathematical and computational approaches to the analysis of evolutionary relationships among species at the genomic level, and the connection between this type of analysis and the problem of comparative mapping. I have also developed algorithms for relating sequence information to protein structure and am continuing to look at approaches to this issue based on “threading” methods.

I am also interested in the development of efficient algorithms for problems in network optimization. Two recent directions I have pursued in this area are the development of a model – with David Kempe and Amit Kumar – for the flow of information through a network over time, and the design of algorithms – with A. Kumar, Yuval Rabani, and E. Tardos – for optimization under certain types of fairness requirements.


Fiona Ip Li ’78 and Donald Li ’75 Excellence in Teaching Award, 2000.


David and Lucile Packard Foundation Fellowship, 1999-2004.

ONR Young Investigator Award, 1999-2002. NSF Faculty Early Career Development Award, 1997-2001.

Alfred P. Sloan Research Fellowship, 1997-1999.

Best paper award, ACM Symposium on Principles of Database Systems, 2000.

University Activities

Member: Graduate Admissions Committee.

Member: Fields of Computer Science, Applied Math, and Operations Research.

Professional Activities

Program Committee Member: International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2000; AAAI Workshop on AI for Web Search, 2000.

Invited Participant: National Academies Workshop on the Interface of Three Areas of Computer Science with the Mathematical Sciences, April 2000; ACM SIGACT Panel on Challenges for Theoretical Computer Science, May 2000.


Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. Conference on Foundations of Computational Mathematics, July 1999.

—. Fields Institute Workshop on Approximation Algorithms, September 1999.

—. MIT Theory of Computation Seminar, December 1999.

—. DIMACS Workshop on Data Mining, May 2000. Algorithms for Protein Sequence Design and Evolutionary Fitness Landscapes. IBM T.J. Watson Research Center, October 1999.

—. Yale University Computer Science Dept., November 1999. Fairness in Routing and Load Balancing. IEEE Symposium on Foundations of Computer Science, October 1999.

—. DIMACS Workshop on Approximation Algorithms, February 2000. Information Networks: Some Models and Algorithms. Cornell University Computer Science Dept., February 2000.

The Small-World Phenomenon: An Algorithmic Perspective. MIT Applied Math Colloquium, February 2000.

—. Internet Archive Colloquium 2000, March 2000.

—. Workshop on Web Measurement, Metrics and Mathematical Models at the 9th International World Wide Web Conf., May 2000.

—. ACM Symposium on Theory of Computing, May 2000.


“Authoritative Sources in a Hyperlinked Environment.” Journal of the ACM, 46(5), 604-632 (September 1999).

“Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields.” Proc. 40th IEEE Symposium on Foundations of Computer Science (1999), 14-23 (with E. Tardos).

“Fairness in Routing and Load Balancing.” Proc. 40th IEEE Symposium on Foundations of Computer Science (1999), 568-578 (with Y. Rabani and E. Tardos).

“Mining the Link Structure of the World Wide Web.” IEEE Computer (August 1999), 60-67 (with S. Chakrabarti, B. Dom, D. Gibson, S.R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins).

“The Web as a graph: Measurements, models and methods.” Invited survey at the International Conference on Combinatorics and Computing (1999), 1-17 (with S.R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins).

“Efficient Algorithms for Protein Sequence Design and the Analysis of Certain Evolutionary Fitness Landscapes.” Journal of Computational Biology 6:3-4 (1999), 387-404.

“Fast Detection of Common Geometric Substructure in Proteins.” Journal of Computational Biology 6:3-4 (1999), 313-325 (with L.P. Chew, D. Huttenlocher, and K. Kedem).

“Hubs, Authorities, and Communities.” ACM Computing Surveys: Symposium on Hypertext and Hypermedia (December 1999).

“The Small-World Phenomenon: An Algorithmic Perspective.” Proc. 32nd ACM Symposium on Theory of Computing, 163-170 (2000).

“Connectivity and Inference Problems for Temporal Networks.” Proc. 32nd ACM Symposium on Theory of Computing (2000), 504-513 (with D. Kempe and A. Kumar).

“Query Strategies for Priced Information.” Proc. 32nd ACM Symposium on Theory of Computing (2000), 582-591 (with M. Charikar, R. Fagin, V. Guruswami, P. Raghavan, and A. Sahai).

Random Walks with ‘Back Buttons’.” Proc. 32nd ACM Symposium on Theory of Computing (2000), 484-493 (with R. Fagin, A. Karlin, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, and A. Tomkins).

“Auditing Boolean Attributes.” Proc. 19th ACM Symposium on Principles of Database Systems (2000), 86-91 (with C.H. Papadimitriou and P. Raghavan).

“Clustering Categorical Data: An Approach Based on Dynamical Systems.” VLDB Journal 8:3-4 (2000), 222-236 (with D. Gibson and P. Raghavan).

“Structural Properties and Tractability Results for Linear Synteny.” Proc. 11th Symposium on Combinatorial Pattern Matching (2000) (with D. Liben-Nowell).