Kleinberg, Jon M
Tisch University Professorresearch
research and scholarship focus
- Algorithms that exploit the combinatorial structure of networks and information
- Techniques for analyzing and modeling link structure in the World Wide Web and related information networksÂ
- Discrete optimization and network algorithms
- Algorithmic approaches to clustering, indexing, and data mining
- Geometric and combinatorial methods for computational problems in molecular biology
co investigator of
- ITR: NETWORKS OF STRATEGIC AGENTS: THEORY AND ALGORITHMS | Research Grant
- PETABYTE STORAGE SERVICES FOR DATA-DRIVEN SCIENCE | Research Grant
- VERY LARGE SEMI-STRUCTURED DATASETS FOR SOCIAL SCIENCE RESEARCH | Research Grant
research areas
- complex systems and networks | strategic research area (Engineering)
- computational biology | research concentration area (Engineering)
- theory of computing | research concentration area (CS)
affiliations
faculty appointment in
- Computer Science (COM S) | Cornell department
member of graduate field
- Applied Mathematics | graduate field
- Computational Biology | graduate field
- Computer Science | graduate field
- Information Science | graduate field
- Operations Research and Information Engineering | graduate field
- Sociology | graduate field
other Cornell affiliations
- Center for Applied Mathematics (CAM) | research center
- Computational and Statistical Genomics | NLSI/Genomics focus area
- Human-Computer Interaction Group (HCI) | research program
teaching
teaches
- CS 4999 - Independent Reading and Research (TBA -) | fall 2009 class
- CS 6820 - Analysis of Algorithms (MWF 02:30:PM-03:20:PM) | fall 2009 class
- CS 7999 - Independent Research (TBA -) | fall 2009 class
- CS 2850 - Networks (MWF 11:15:AM-12:05:PM) | spring 2009 class
- CS 4999 - Independent Reading and Research (TBA -) | spring 2009 class
- CS 7999 - Independent Research (TBA -) | spring 2009 class
- ECON 2040 - Networks (MWF 11:15:AM-12:05:PM) | spring 2009 class
- INFO 2040 - Networks (MWF 11:15:AM-12:05:PM) | spring 2009 class
- SOC 2090 - Networks (MWF 11:15:AM-12:05:PM) | spring 2009 class
- CS 6850 - The Structure of Information Networks (MWF 01:25:PM-02:15:PM) | fall 2008 class
- INFO 6850 - The Structure of Information Networks (MWF 01:25:PM-02:15:PM) | fall 2008 class
service
event organizer
event host
background
educational background
- Ph.D., Massachusetts Institute of Technology, 1996
awards and distinctions
-
- Packard Foundation fellowship
-
- John D. and Catherine T. MacArthur Foundation's "genius award"
-
- National Academy of Engineering, 2008
- National Academy of Engineering, 2008
-
- Rolf Nevanlinna Prize from the International Mathematics Union, 2006
-
- American Association for the Advancement of Science, 2007
- American Association for the Advancement of Science, 2007
-
- U.S. National Academy of Sciences Initiatives in Research AwardÂ
-
- Sloan Foundation fellowship
featured in
- Jon Kleinberg elected to the National Academy of Engineering | Cornell Chronicle feature
- Kavli symposium looks at the future of computing | Cornell Chronicle feature
- Kleinberg wins $150,000 computer science prize | Cornell Chronicle feature
- Research Without Boundaries, College of Engineering | magazine
- Tracking the life and death of news | Cornell Chronicle feature
- With hundreds of degrees of separation, the Internet doesn't always resemble a 'small world' | Cornell Chronicle feature
publications
selected publications (listing in progress)
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- L. Backstrom, J. Kleinberg, R. Kumar, J. Novak. Spatial Variation in Search Engine Queries. Proc. 17th International World Wide Web Conference, 2008.
- 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).
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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).
- 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.
- 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.
- 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.