Jon Kleinberg

I am a professor of computer science at Cornell University. My research focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other on-line media. My work has been supported by an NSF Career Award, an ONR Young Investigator Award, a MacArthur Foundation Fellowship, a Packard Foundation Fellowship, a Sloan Foundation Fellowship, and grants from Google, Yahoo!, and the NSF. I am a member of the National Academy of Engineering and the American Academy of Arts and Sciences.

Links to: Contact information; Current and former students.

Teaching

• In Spring 2009, David Easley and I wil be teaching an introductory undergraduate course entitled Networks, covering the expanding role of networks in the study of phenomena across the social, technological, and natural worlds. See also the home page for the Spring 2007 version of the course, when it was first offered, as well as the class blog with posts by students taking the course.

• With Eva Tardos, I've written a book on Algorithm Design (Addison-Wesley, 2005), based on the undergraduate algorithms course that we teach.

• At the graduate level, I've developed two courses that cover topics related to my research:
  The Structure of Information Networks (Fall 2008) (and see also the original Fall 2002 version).
  Randomized and High-Dimensional Algorithms (Spring 2001).

• At the undergraduate level, I've also taught discrete math for computer science.

Research

The papers below are also available in a chronological list. Additional bibliographic information can be found at DBLP.

Web Analysis and Search: Hubs and Authorities

• J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). Also appears as IBM Research Report RJ 10076, May 1997.
• D. Gibson, J. Kleinberg, P. Raghavan. Inferring Web communities from link topology. Proc. 9th ACM Conference on Hypertext and Hypermedia, 1998.
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, P. Raghavan, S. Rajagopalan, Automatic resource list compilation by analyzing hyperlink structure and associated text. Proc. 7th International World Wide Web Conference, 1998.
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Hypersearching the Web. Scientific American, June 1999.
• S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Mining the link structure of the World Wide Web. IEEE Computer, August 1999.

Small-World Phenomena and Decentralized Search

• J. Kleinberg. Navigation in a Small World. Nature 406(2000), 845.
• J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000. Also appears as Cornell Computer Science Technical Report 99-1776 (October 1999). (Also in HTML.)
• J. Kleinberg. Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS) 14, 2001.
• J. Kleinberg. The Small-World Phenomenon and Decentralized Search. A short essay as part of Math Awareness Month 2004, appearing in SIAM News 37(3), April 2004
• J. Kleinberg. Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006.

Cascades, Diffusion, and Community Formation in Social Networks

• D. Liben-Nowell, J. Kleinberg. Tracing Information Flow on a Global Scale Using Internet Chain-Letter Data. Proc. National Academy of Sciences, 105(12):4633–4638, 25 March 2008.
  • We are interested in gathering additional data about the spread of the chain-letter petitions described in this paper. Please visit http://petitions.cs.cornell.edu or http://petitions.cs.carleton.edu to learn more or to help.

  G. Kossinets, J. Kleinberg, D. Watts. The Structure of Information Pathways in a Social Communication Network. Proc. 14th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2008.

  D. Crandall, D. Cosley, D. Huttenlocher, J. Kleinberg, S. Suri. Feedback Effects between Similarity and Social Influence in Online Communities. Proc. 14th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2008.

  J. Kleinberg. Cascading Behavior in Networks: Algorithmic and Economic Issues. In Algorithmic Game Theory (N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani, eds.), Cambridge University Press, 2007.

  J. Kleinberg The Wireless Epidemic. Nature (News and Views) 449(2007), 287-288.

  N. Immorlica, J. Kleinberg, M. Mahdian, T. Wexler. The Role of Compatibility in the Diffusion of Technologies Through Social Networks. Proc. 8th ACM Conference on Electronic Commerce, 2007.

  L. Backstrom, D. Huttenlocher, J. Kleinberg, X. Lan. Group Formation in Large Social Networks: Membership, Growth, and Evolution. Proc. 12th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2006.

  J. Leskovec, A. Singh, J. Kleinberg. Patterns of Influence in a Recommendation Network. Proc. Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2006.

  D. Kempe, J. Kleinberg, E. Tardos. Influential Nodes in a Diffusion Model for Social Networks. Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP), 2005.

  D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. Proc. 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2003.

Word Bursts and Temporal Analysis

• J. Kleinberg. Bursty and Hierarchical Structure in Streams. Proc. 8th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2002.
  • See also some sample results from the burst detection algorithm described in this paper.

  J. Aizen, D. Huttenlocher, J. Kleinberg, A. Novak. Traffic-Based Feedback on the Web. Proceedings of the National Academy of Sciences 101(Suppl.1):5254-5260, 2004. (Also available in pre-print form.)

  J. Kleinberg. Temporal Dynamics of On-Line Information Streams. In Data Stream Management: Processing High-Speed Data Streams, (M. Garofalakis, J. Gehrke, R. Rastogi, eds.), Springer, to appear.

Network-Structured Markets

• J. Kleinberg, E. Tardos. Balanced Outcomes in Social Exchange Networks. Proc. 40th ACM Symposium on Theory of Computing, 2008.
• L. Blume, D. Easley, J. Kleinberg, E. Tardos. Trading Networks with Price-Setting Agents. Proc. 8th ACM Conference on Electronic Commerce, 2007.
• J. Kleinberg, P. Raghavan. Query Incentive Networks. Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.

Privacy in Network Analysis and Data Mining

• L. Backstrom, C. Dwork, J. Kleinberg. Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography. Proc. 16th Intl. World Wide Web Conference, 2007.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. Auditing Boolean Attributes. Proc. 19th ACM Symposium on Principles of Database Systems, 2000.

Spatial Embeddings of Information

• L. Backstrom, J. Kleinberg, R. Kumar, J. Novak. Spatial Variation in Search Engine Queries. Proc. 17th International World Wide Web Conference, 2008.

Network Evolution

• J. Kleinberg, S. Suri, E. Tardos, T. Wexler. Strategic Network Formation with Structural Holes. Proc. 9th ACM Conference on Electronic Commerce, 2008.
• J. Leskovec, J. Kleinberg, C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. Proc. 11th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2005.
• R. Kleinberg, J. Kleinberg, Isomorphism and Embedding Problems for Infinite Limits of Scale-Free Graphs. Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, 2005.
• D. Liben-Nowell, J. Kleinberg. The Link Prediction Problem for Social Networks. Proc. 12th International Conference on Information and Knowledge Management (CIKM), 2003.
• D. Callaway, J. Hopcroft, J. Kleinberg, M. Newman, S. Strogatz. Are randomly grown graphs really random? Physical Review E 64, 041902 (2001).

Gossip Algorithms in Networks

• D. Kempe, J. Kleinberg, A. Demers. Spatial gossip and resource location protocols. Proc. 33rd ACM Symposium on Theory of Computing, 2001. (In PDF.)
• D. Kempe, J. Kleinberg. Protocols and Impossibility Results for Gossip-Based Communication Mechanisms. Proc. 43rd IEEE Symposium on Foundations of Computer Science, 2002.

Surveys on Web Information and Web Structure

• J. Kleinberg, S.R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins. The Web as a graph: Measurements, models and methods. Invited survey at the International Conference on Combinatorics and Computing, 1999.
• J. Kleinberg, S. Lawrence. The Structure of the Web. Science 294(2001), 1849. This version also appears in the on-line edition of Science.
• J. Kleinberg. Analysing the scientific literature in its online context. Nature Web Focus on Access to the Literature, April 2004.

General Surveys on Algorithms and Complexity

• J. Kleinberg. The Mathematics of Algorithm Design. In Princeton Companion to Mathematics, (T. Gowers and J. Barrow-Green, eds.), Princeton Univ. Press, to appear.
• J. Kleinberg, C. Papadimitriou. Computability and Complexity. An essay in Computer Science: Reflections on the Field, Reflections from the Field. National Academies Press, 2004.

Clustering, Indexing, and Data Mining

• A. Dasgupta, J. Hopcroft, J. Kleinberg, M. Sandler. On Learning Mixtures of Heavy-Tailed Distributions. Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
• J. Kleinberg, M. Sandler. Using Mixture Models for Collaborative Filtering. Proc. 36th ACM Symposium on Theory of Computing, 2004.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. Segmentation problems. Journal of the ACM, 51(2), 2004.
• P. Felzenszwalb, D. Huttenlocher, J. Kleinberg. Fast Algorithms for Large-State-Space HMMs with Applications to Web Usage Analysis. Advances in Neural Information Processing Systems (NIPS) 16, 2003. (In PDF.)
• J. Kleinberg, M. Sandler. Convergent Algorithms for Collaborative Filtering. Proc. 4th ACM Conference on Electronic Commerce, 2003. (In PDF.)
• J. Kleinberg. An Impossibility Theorem for Clustering. Advances in Neural Information Processing Systems (NIPS) 15, 2002.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. On the Value of Private Information. Proc. 8th Conf. on Theoretical Aspects of Rationality and Knowledge, 2001.
• J. Kleinberg, E. Tardos. Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. Proc. 40th IEEE Symposium on Foundations of Computer Science, 1999.
• J. Kleinberg, C. Papadimitriou, P. Raghavan. A micro-economic view of data mining. Data Mining and Knowledge Discovery, 2(4), 1998.
• D. Gibson, J. Kleinberg, P. Raghavan. Clustering categorical data: An approach based on dynamical systems. Proc. 24th Intl. Conference on Very Large Databases, 1998.
• J. Kleinberg. Two algorithms for nearest-neighbor search in high dimensions. Proc. 29th ACM Symposium on Theory of Computing, 1997.

Network Analysis, Management, and Routing

• A. Frieze, J. Kleinberg, R. Ravi, W. Debany. Line-of-Sight Networks. Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, 2007.
• A. Krause, C. Guestrin, A. Gupta, J. Kleinberg. Near-optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost. Proc. Information Processing in Sensor Networks (IPSN), 2006.
• J. Kleinberg. An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs. Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
• I. Abraham, Y. Bartal, T-H. Chan, K. Dhamdhere, A. Gupta, J. Kleinberg, O. Neiman, A. Slivkins. Metric Embeddings with Relaxed Guarantees. Proc. 46th IEEE Symposium on Foundations of Computer Science, 2005.
• J. Kleinberg, A. Slivkins, T. Wexler. Triangulation and Embedding using Small Sets of Beacons. Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004.
• E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, T. Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. Proc. 45th IEEE Symposium on Foundations of Computer Science, 2004.
• J. Kleinberg, M. Sandler, A. Slivkins. Network Failure Detection and Graph Connectivity. Proc. 15th ACM-SIAM Symposium on Discrete Algorithms, 2004. (In PDF.)
• A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, B. Yener. Provisioning a virtual private network: A network design problem for multicommodity flow. Proc. 33rd ACM Symposium on Theory of Computing, 2001.
• J. Kleinberg. Detecting a Network Failure. Proc. 41st IEEE Symposium on Foundations of Computer Science, 2000.
• D. Kempe, J. Kleinberg, A. Kumar. Connectivity and inference problems for temporal networks. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
• R. Fagin, A. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, A. Tomkins. Random Walks with `Back Buttons.' Proc. 32nd ACM Symposium on Theory of Computing, 2000.
• J. Kleinberg, A. Kumar. Wavelength conversion in optical networks. Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, 1999.
• M. Charikar, J. Kleinberg, S.R. Kumar, S. Rajagopalan, A. Sahai, A. Tomkins. Minimizing wirelength in zero and bounded skew clock trees. Proc. 10th ACM-SIAM Symposium on Discrete Algorithms, 1999.
• J. Kleinberg. Decision algorithms for unsplittable flow and the half-disjoint paths problem. Proc. 30th ACM Symposium on Theory of Computing, 1998.
• J. Kleinberg, Y. Rabani, E. Tardos. Allocating bandwidth for bursty connections. Proc. 29th ACM Symposium on Theory of Computing, 1997.
• J. Kleinberg. Single-source unsplittable flow. Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
• J. Kleinberg, R. Rubinfeld. Short paths in expander graphs. Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
• A. Aggarwal, J. Kleinberg, D. Williamson. Node-disjoint paths on the mesh, and a new trade-off in VLSI layout. Proc. 28th ACM Symposium on Theory of Computing, 1996.
• J. Kleinberg, E. Tardos. Disjoint paths in densely embedded graphs. Proc. 36th IEEE Symposium on Foundations of Computer Science, 1995.
• J. Kleinberg, E. Tardos. Approximations for the disjoint paths problem in high-diameter planar networks. Proc. 27th ACM Symposium on Theory of Computing, 1995.
• J. Kleinberg. Approximation Algorithms for Disjoint Paths Problems. Ph.D Thesis, Dept. of EECS, MIT, 1996.

Dynamic Network Algorithms and Adversarial Queueing Theory

• A. Borodin, J. Kleinberg, P. Raghavan, M. Sudan, D. Williamson. Adversarial queueing theory. Proc. 28th ACM Symposium on Theory of Computing, 1996.
• D.M. Andrews, B. Awerbuch, A. Fernandez, J. Kleinberg, F.T. Leighton, Z. Liu. Universal stability results for greedy contention-resolution protocols. Proc. 37th IEEE Symposium on Foundations of Computer Science, 1996.
• E. Anshelevich, D. Kempe, J. Kleinberg. Stability of Load Balancing Algorithms in Dynamic Adversarial Systems. Proc. 34th ACM Symposium on Theory of Computing, 2002.

Fairness in Optimization

• A. Kumar, J. Kleinberg. Fairness measures for resource allocation. Proc. 41st IEEE Symposium on Foundations of Computer Science, 2000.
• J. Kleinberg, Y. Rabani, E. Tardos. Fairness in routing and load balancing. Proc. 40th IEEE Symposium on Foundations of Computer Science, 1999.

Comparative Genomics and Evolutionary Models

• L. Meyerguz, J. Kleinberg, R. Elber. The network of sequence flow between protein structures. Proceedings of the National Academy of Sciences 10.1073, 27 June 2007.
• L. Meyerguz, D. Kempe, J. Kleinberg, R. Elber. The Evolutionary Capacity of Protein Structures. Proc. ACM RECOMB Intl. Conference on Computational Molecular Biology, 2004.
• I. V. Yap, D. Schneider, J. Kleinberg, D. Matthews, S. Cartinhour, S. R. McCouch. A Graph-Theoretic Approach to Comparing and Integrating Genetic, Physical and Sequence-Based Maps. Genetics, Vol. 165(2003).
• D. Goldberg, S. McCouch, J. Kleinberg. Constructing comparative maps with unresolved marker order. Proc. Pacific Symposium on Biocomputing, 2002.
• D. Goldberg, S. McCouch, J. Kleinberg. Algorithms for Constructing Comparative Maps. Conference on Gene Order Dynamics, Comparative Maps, and Multigene Families, 2000. (In PDF.)
• J. Kleinberg, D. Liben-Nowell. The Syntenic Diameter of the Space of N-Chromosome Genomes. Conference on Gene Order Dynamics, Comparative Maps, and Multigene Families, 2000.
• J. Kleinberg. Efficient Algorithms for Protein Sequence Design and the Analysis of Certain Evolutionary Fitness Landscapes. Proc. 3rd ACM RECOMB Intl. Conference on Computational Molecular Biology, 1999.

Protein Structure Analysis

• L.P. Chew, D. Huttenlocher, K. Kedem, J. Kleinberg. Fast Detection of Common Geometric Substructure in Proteins. Proc. 3rd ACM RECOMB Intl. Conference on Computational Molecular Biology, 1999.
• B. Berger, J. Kleinberg, F.T. Leighton. Reconstructing a Three-Dimensional Model with Arbitrary Errors. Proc. 28th ACM Symposium on Theory of Computing, 1996.

On-Line Algorithms

• M. Charikar, R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan, A. Sahai. Query strategies for priced information. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
• J. Kleinberg, R. Motwani, P. Raghavan, S. Venkatasubramanian. Storage management for evolving databases. Proc. 38th IEEE Symposium on Foundations of Computer Science, 1997.
• J. Kleinberg. The localization problem for mobile robots. Proc. 35th IEEE Symposium on Foundations of Computer Science, 1994.
• J. Kleinberg. On-line search in a simple polygon. Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994.
• J. Kleinberg. A lower bound for two-server balancing algorithms. Information Processing Letters 51(1994).
• R. El-Yaniv, J. Kleinberg. Geometric two-server algorithms. Information Processing Letters 53(1995).

Algorithms for NP-hard problems

• E. Dantsin, A. Goerdt, E. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schoning, A deterministic algorithm for satisfiability based on local search. Theoretical Computer Science, 289(2002).
• J. Kleinberg, M. Goemans. The Lovasz theta function and a semi-definite programming relaxation of vertex cover. SIAM J. Discrete Math, 11(1998).
• M. Goemans, J. Kleinberg. An improved approximation ratio for the minimum latency problem. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 1996.

Geometric Pattern Matching

• D. Huttenlocher, J. Kleinberg. Comparing point sets under projection. Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, 1994.
• D. Huttenlocher, K. Kedem, J. Kleinberg. On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane. Proc. 8th ACM Symposium on Computational Geometry, 1992.
• D. Huttenlocher, J. Kleinberg, Invariants of set of points or line segments under projection. Cornell University Computer Science Technical Report TR 92-1292, July 1992.

Fault-tolerance in Distributed Computing

• J. Kleinberg, H. Attiya, N. Lynch. Trade-offs between message delivery and quiesce times in connection management protocols. Proc. 3rd Israel Symposium on Theory of Computing and Systems, 1995.
• J. Kleinberg, S. Mullainathan. Resource bounds and combinations of consensus objects. Proc. 12th ACM Symposium on Principles of Distributed Computing, 1993.

Current and Former Ph.D. students

• Elliot Anshelevich (Ph.D. 2005; now at RPI).
• Lars Backstrom.
• Debra Goldberg (Ph.D. 2001; now at CU Boulder).
• David Kempe (Ph.D. 2003; now at USC).
• Amit Kumar. (Ph.D. 2002; now at IIT Dehli).
• Mark Sandler (Ph.D. 2006; now at Google).
• Alex Slivkins (Ph.D. 2006; now at Brown, then Microsoft Research).

Some Cornell Links

• Cornell University.
• CUinfo.
• Cornell Computer Science.
• Cornell CS Department Course Home Pages.
• Cornell Operations Research.
• Cornell Center for Applied Math.
• Ithaca Weather.

Contact Information