Jon Kleinberg

I am a professor at Cornell University. My research focuses on the interaction of algorithms and networks, and the roles they play in large-scale social and information systems. My work has been supported by an NSF Career Award, an ONR Young Investigator Award, a MacArthur Foundation Fellowship, a Packard Foundation Fellowship, a Simons Investigator Award, a Sloan Foundation Fellowship, and grants from Facebook, Google, Yahoo, the MacArthur Foundation, the ARO, and the NSF. I am a member of the National Academy of Sciences, the National Academy of Engineering, and the American Academy of Arts and Sciences.

Link to: Contact information.

Books and Teaching

• D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.
  • This book is based on an inter-disciplinary course that we teach entitled Networks. The book, like the course, is designed at the introductory undergraduate level with no formal prerequisites. To support deeper explorations, most of the chapters are supplemented with optional advanced sections.
• J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.
  • This book is based on the undergraduate algorithms course that we both teach. We also use the more advanced parts for our graduate algorithms course.
• An on-line course on edX entitled Networks, Crowds, and Markets, with David Easley and Eva Tardos.
• Recent courses at Cornell:
  • Networks (with David Easley and Eva Tardos; ECON 2040 / SOC 2090 / CS 2850 / INFO 2040).
  • The Structure of Information Networks (CS 6850).
  • Algorithms (CS 6820).

Advising

• Current and former Ph.D. students: Maithra Raghu, Rediet Abebe, Manish Raghavan, Anna Evtushenko, Katherine Van Koevering, Kate Donahue, Rahmtin Rotabi (Google), Isabel Kloumann (Facebook), Johan Ugander (Stanford), Sigal Oren (Ben-Gurion Univ), Daniel Romero (U. Michigan), Lars Backstrom (Facebook), Alex Slivkins (Microsoft Research), Mark Sandler (Google), Elliot Anshelevich (RPI), David Kempe (USC), Amit Kumar. (IIT Dehli), Debra Goldberg (CU Boulder).

• Current and former postdocs: Austin Benson (Cornell), Flavio Chierichetti (Sapienza University of Rome), Jure Leskovec (Stanford), Sid Suri (Microsoft Research), Gregory Kossinets. (Google), Mohammad Mahdian (Google), Frank McSherry (Microsoft Research) Anupam Gupta (CMU).

Research Papers

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

Recent Papers

• J. Kleinberg, J. Ludwig, S. Mullainathan, C. Sunstein. Discrimination in the Age of Algorithms. Journal of Legal Analysis, 2019. Also appears as NBER Working Paper Number 25548, February 2019.
• J. Kleinberg, S. Mullainathan. Simplicity Creates Inequity: Implications for Fairness, Stereotypes, and Interpretability. Proc. 20th ACM Conference on Economics and Computation (EC), 2019.
• J. Kleinberg, M. Raghavan. How Do Classifiers Induce Agents To Invest Effort Strategically? Proc. 20th ACM Conference on Economics and Computation (EC), 2019.
• M. Raghu, K. Blumer, R. Sayres, Z. Obermeyer, R. Kleinberg, S. Mullainathan, J. Kleinberg. Direct Uncertainty Prediction for Medical Second Opinions. Proc. 36th Intl. Conf. on Machine Learning (ICML), 2019. See also the accompanying blog post by Maithra Raghu.
• A. Benson, J. Kleinberg. Core-fringe link prediction. Proc. 28th International World Wide Web Conference, 2019. See also the code and data accompanying the paper.
• M. Yeomans, A. Shah., S. Mullainathan, J. Kleinberg. Making Sense of Recommendations. Journal of Behavioral Decision Making, 2019.
• M. Raghavan, S. Barocas, J. Kleinberg, K. Levy Mitigating Bias in Algorithmic Employment Screening: Evaluating Claims and Practices. arXiv/1906.09208, 2019.
• K. Donahue, J. Kleinberg. Fairness and Utilization in Allocating Resources with Uncertain Demand. arXiv/1906.09050, 2019.
• M. Raghu, K. Blumer, G. Corrado, J. Kleinberg, Z. Obermeyer, S. Mullainathan. The Algorithmic Automation Problem: Prediction, Triage, and Human Effort. arXiv/1903.12220, 2019.
• M. Raghu, C. Zhang, J. Kleinberg, S. Bengio. Transfusion: Understanding Transfer Learning with Applications to Medical Imaging. arXiv/1902.07208, 2019.
• R. Abebe, L. Adamic, J. Kleinberg. Mitigating Overexposure in Viral Marketing. Proc. 32nd AAAI Conference on Artificial Intelligence (AAAI-18), 2018.
• A. Benson, R. Abebe, M. Schaub, A. Jadbabaie, J. Kleinberg. Simplicial Closure and Higher-order Link Prediction. Proc. National Academy of Sciences, 115(48) E11221-E11230, 27 November 2018. See also links for code and data accompanying the paper.

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 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.

Interactions of Algorithmic and Human Decision-Making

• J. Kleinberg, H. Lakkaraju, J. Leskovec, J. Ludwig, S. Mullainathan. Human Decisions and Machine Predictions. Quarterly Journal of Economics (QJE) volume 133:1, February 2018. Also appears as NBER Working Paper Number 23180, February 2017.
• H. Lakkaraju, J. Kleinberg, J. Leskovec, J. Ludwig, S. Mullainathan. The Selective Labels Problem: Evaluating Algorithmic Predictions in the Presence of Unobservables. Proc. 23rd ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2017.
• J. Kleinberg, A. Liang, S. Mullainathan. The Theory is Predictive, but is it Complete? An Application to Human Perception of Randomness. Proc. 18th ACM Conference on Economics and Computation (EC), 2017.
• J. Kleinberg, J. Ludwig, S. Mullainathan. A Guide to Solving Social Problems with Machine Learning. Harvard Business Review, December 2016.
• M. Luca, J. Kleinberg, S. Mullainathan. Algorithms Need Managers, Too. Harvard Business Review, 94:1(Jan/Feb 2016).
• A. Anderson, J. Kleinberg, S. Mullainathan. Assessing Human Error Against a Benchmark of Perfection. Proc. 22nd ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2016.
• J. Kleinberg, J. Ludwig, S. Mullainathan, Z. Obermeyer. Prediction Policy Problems. American Economic Review: Papers and Proceedings 105:5(2015).
• H. Lakkaraju, J. Leskovec, J. Kleinberg, S. Mullainathan. A Bayesian Framework for Modeling Human Evaluations. Proc. 15th SIAM International Conference on Data Mining (SDM), 2015.
• J. Kleinberg, S. Mullainathan. We Built Them, But We Don't Understand Them. In What to Think About Machines That Think: Today's Leading Thinkers on the Age of Machine Intelligence. (J. Brockman, editor), Harper Perennial 2015.

Fairness in Algorithms

• J. Kleinberg, M. Raghavan. Selection Problems in the Presence of Implicit Bias. Proc. 9th Conf. on Innovations in Theoretical Computer Science (ITCS), 2018.
• J. Kleinberg, J. Ludwig, S. Mullainathan, A. Rambachan. Algorithmic Fairness. AEA Papers and Proceedings 108:22-27, 2018.
• J. Kleinberg, S. Mullainathan, M. Raghavan. Inherent Trade-Offs in the Fair Determination of Risk Scores. Proc. 8th Conf. on Innovations in Theoretical Computer Science (ITCS), 2017.
• G. Pleiss, M. Raghavan, F. Wu, J. Kleinberg, K. Weinberger. On Fairness and Calibration. Advances in Neural Information Processing Systems 31, 2017.
• R. Abebe, J. Kleinberg, D. Parkes. Fair Division via Social Comparison. Proc. 16th Intl. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), 2017 .
• J. Kleinberg, M. Raghu. Team Performance with Test Scores. Proc. 16th ACM Conference on Economics and Computation (EC), 2015.
• J. Kleinberg, S. Oren. Mechanisms for (Mis)Allocating Scientific Credit. Proc. 43rd ACM Symposium on Theory of Computing, 2011.
• 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.

Information Flow and Dynamic Behavior in Networks

• M. Raghavan, A. Anderson, J. Kleinberg. Mapping the Invocation Structure of Online Political Interaction. Proc. 27th International World Wide Web Conference, 2018.
• R. Abebe, J. Kleinberg, D. Parkes, C. Tsourakakis. Opinion Dynamics with Varying Susceptibility to Persuasion. Proc. 24th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2018.
• J. Cheng, J. Kleinberg, J. Leskovec, D. Liben-Nowell, B. State, K. Subbian, L. Adamic. Do Diffusion Protocols Govern Cascade Growth? Proc. 12th International AAAI Conference on Weblogs and Social Media (ICWSM), 2018.
• R. Rotabi, C. Danescu-Niculescu-Mizil, J. Kleinberg. Tracing the Use of Practices through Networks of Collaboration. Proc. 11th International AAAI Conference on Weblogs and Social Media (ICWSM), 2017.
• R. Rotabi, C. Danescu-Niculescu-Mizil, J. Kleinberg. Competition and Selection Among Conventions. Proc. 26th International World Wide Web Conference, 2017.
• R. Rotabi, K. Kamath, J. Kleinberg, A. Sharma. Cascades: A view from Audience. Proc. 26th International World Wide Web Conference, 2017.
• D. Romero, B. Uzzi, J. Kleinberg. Social Networks Under Stress. Proc. 25th International World Wide Web Conference, 2016.
• J. Cheng, L. Adamic, J. Kleinberg, J. Leskovec. Do Cascades Recur?. Proc. 25th International World Wide Web Conference, 2016.
• R. Rotabi, J. Kleinberg. The Status Gradient of Trends in Social Media. Proc. 10th International AAAI Conference on Weblogs and Social Media, 2016.
• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Global Diffusion via Cascading Invitations: Structure, Growth, and Homophily. Proc. 24th International World Wide Web Conference, 2015.
• I. Kloumann, L. Adamic, J. Kleinberg, S. Wu. The Lifecycles of Apps in a Social Ecosystem. Proc. 24th International World Wide Web Conference, 2015.
• J. Cheng, L. Adamic, A. Dow, J. Kleinberg, J. Leskovec. Can Cascades Be Predicted? Proc. 23rd International World Wide Web Conference, 2014.
  • See also the Facebook Data Science blog post about this work.

  L. Backstrom, J. Kleinberg, L. Lee, C. Danescu-Niculescu-Mizil. Characterizing and Curating Conversation Threads: Expansion, Focus, Volume, Re-entry. Proc. 6th ACM Conference on Web Search and Data Mining, 2013.

  F. Chierichetti, J. Kleinberg, S. Oren. On discrete preferences and coordination. Proc. 14th ACM Conference on Electronic Commerce, 2013.

  D. Kempe, J. Kleinberg, S. Oren, A. Slivkins. Selection and Influence in Cultural Dynamics. Proc. 14th ACM Conference on Electronic Commerce, 2013.

  J. Ugander, L. Backstrom, C. Marlow, J. Kleinberg. Structural Diversity in Social Contagion. Proc. National Academy of Sciences, 109(16) 5962-5966, 17 April 2012.

  K. Bhawalkar, J. Kleinberg, K. Lewi, T. Roughgarden, A. Sharma. Preventing Unraveling in Social Networks: The Anchored k-Core Problem, Proc. 39th International Colloquium on Automata, Languages and Programming (ICALP), 2012.

  F. Chierichetti, J. Kleinberg, A. Panconesi. How to schedule a cascade in an arbitrary graph. Proc. 13th ACM Conference on Electronic Commerce, 2012.

  L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, E. Tardos. Which Networks Are Least Susceptible to Cascading Failures? Proc. 52nd IEEE Symposium on Foundations of Computer Science, 2011.

  L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, E. Tardos. Network Formation in the Presence of Contagious Risk. Proc. 12th ACM Conference on Electronic Commerce, 2011.

  F. Chierichetti, J. Kleinberg, D. Liben-Nowell. Reconstructing Patterns of Information Diffusion from Incomplete Observations. Advances in Neural Information Processing Systems 24, 2011.

  D. Romero, B. Meeder, J. Kleinberg. Differences in the Mechanics of Information Diffusion Across Topics: Idioms, Political Hashtags, and Complex Contagion on Twitter. Proc. 20th International World Wide Web Conference, 2011.

  S. Wu, C. Tan, J. Kleinberg, M. Macy. Does Bad News Go Away Faster? Proc. 5th International AAAI Conference on Weblogs and Social Media, 2011.

  D. Cosley, D. Huttenlocher, J. Kleinberg, X. Lan, S. Suri. Sequential Influence Models in Social Networks. Proc. 4th International AAAI Conference on Weblogs and Social Media, 2010.

  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.

Network Structure and Network Evolution

• A. Benson, J. Kleinberg. Found Graph Data and Planted Vertex Covers. Advances in Neural Information Processing Systems 32, 2018. See also links for code and data accompanying the paper.
• I. Kloumann, J. Ugander, J. Kleinberg. Block Models and Personalized PageRank. Proc. National Academy of Sciences, 114(1) 33-38, 3 January 2017.
• R. Rotabi, K. Kamath, J. Kleinberg, A. Sharma. Detecting Strong Ties Using Network Motifs. Proc. 26th International World Wide Web Conference, 2017.
• L. Backstrom, J. Kleinberg. Romantic Partnerships and the Dispersion of Social Ties: A Network Analysis of Relationship Status on Facebook. Proc. 17th ACM Conference on Computer Supported Cooperative Work and Social Computing (CSCW), 2014.
• I. Kloumann, J. Kleinberg. Community membership identification from small seed sets. Proc. 20th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2014.
• J. Ugander, L. Backstrom, J. Kleinberg. Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections. Proc. 22nd International World Wide Web Conference, 2013.
  • See also the companion Web page by Johan Ugander, including R code.

  J. Ugander, B. Karrer, L. Backstrom, J. Kleinberg. Graph cluster randomization: network exposure to multiple universes. Proc. 19th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2013.

  J. Tang, T. Lou, J. Kleinberg. Inferring Social Ties across Heterogenous Networks. Proc. 5th ACM Conference on Web Search and Data Mining, 2012.

  L. Backstrom, J. Kleinberg. Network Bucket Testing. Proc. 20th International World Wide Web Conference, 2011.

  L. Backstrom, E. Bakshy, J. Kleinberg, T. Lento, I. Rosenn. Center of Attention: How Facebook Users Allocate Attention across Friends. Proc. 5th International AAAI Conference on Weblogs and Social Media, 2011.

  D. Romero, B. Meeder, V. Barash, J. Kleinberg. Maintaining Ties on Social Media Sites: The Competing Effects of Balance, Exchange, and Betweenness. Proc. 5th International AAAI Conference on Weblogs and Social Media, 2011.

  J. Cheng, D. Romero, B. Meeder, J. Kleinberg. Predicting Reciprocity in Social Networks. Proc. 3rd IEEE Conference on Social Computing, 2011.

  D. Romero, J. Kleinberg. The Directed Closure Process in Hybrid Social-Information Networks, with an Analysis of Link Formation on Twitter. Proc. 4th International AAAI Conference on Weblogs and Social Media, 2010.

  S. Arbesman, J. Kleinberg, S. Strogatz. Superlinear Scaling for Innovation in Cities. Physical Review E 79(1), 2009.

  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).

Incentives and Game-Theoretic Analysis

• J. Kleinberg, R. Kleinberg. Delegated Search Approximates Efficient Search. Proc. 19th ACM Conference on Economics and Computation (EC), 2018.
• J. Kleinberg, S. Oren, M. Raghavan. Planning with Multiple Biases. Proc. 18th ACM Conference on Economics and Computation (EC), 2017.
• J. Kleinberg, S. Mullainathan, J. Ugander. Comparison-Based Choices. Proc. 18th ACM Conference on Economics and Computation (EC), 2017.
• J. Kleinberg, S. Oren, M. Raghavan. Planning Problems for Sophisticated Agents with Present Bias. Proc. 17th ACM Conference on Economics and Computation (EC), 2016.
• J. Kleinberg, S. Oren. Dynamic Models of Reputation and Competition in Job-Market Matching. Proc. 6th Conference on Innovations in Theoretical Computer Science (ITCS), 2015.
• L. Blume, D. Easley, J. Kleinberg, R. Kleinberg, E. Tardos. Introduction to computer science and economic theory. Journal of Economic Theory 156(2015).
• J. Kleinberg, S. Oren. Time-Inconsistent Planning: A Computational Problem in Behavioral Economics. Proc. 15th ACM Conference on Economics and Computation (EC), 2014.
• P. Frazier, D. Kempe, J. Kleinberg, R. Kleinberg. Incentivizing Exploration. Proc. 15th ACM Conference on Economics and Computation (EC), 2014.
• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Steering User Behavior with Badges. Proc. 22nd International World Wide Web Conference, 2013.
• F. Chierichetti, J. Kleinberg. Voting with Limited Information and Many Alternatives. Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, 2012.
• 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.
• 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.

Opinion, Evaluation, and Polarization

• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Effects of User Similarity in Social Media. Proc. 5th ACM Conference on Web Search and Data Mining, 2012.
• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Discovering Value from Community Activity on Focused Question Answering Sites: A Case Study of Stack Overflow. Proc. 18th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2012.
• D. Bindel, J. Kleinberg, S. Oren. How Bad is Forming Your Own Opinion? Proc. 52nd IEEE Symposium on Foundations of Computer Science, 2011.
• S. Marvel, J. Kleinberg, R. Kleinberg, S. Strogatz. Continuous-Time Model of Structural Balance. Proc. National Academy of Sciences, 108(5) 1771-1776, 1 February 2011.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Governance in Social Media: A case study of the Wikipedia promotion process. Proc. 4th International AAAI Conference on Weblogs and Social Media, 2010.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Signed Networks in Social Media. Proc. 28th ACM SIGCHI Conference on Human Factors in Computing Systems (CHI), 2010.
• J. Leskovec, D. Huttenlocher, J. Kleinberg. Predicting Positive and Negative Links in Online Social Networks. Proc. 19th International World Wide Web Conference, 2010.
• S. Marvel, J. Kleinberg, S. Strogatz. The Energy Landscape of Social Balance. Physical Review Letters 103(19), 2009.
• C. Danescu-Niculescu-Mizil, G. Kossinets, J. Kleinberg, L. Lee. How Opinions are Received by Online Communities: A Case Study on Amazon.com Helpfulness Votes. Proc. 18th International World Wide Web Conference, 2009.

Temporal Analysis and Bursty Phenomena

• F. Chierichetti, J. Kleinberg, R. Kumar, M. Mahdian, S. Pandey. Event Detection via Communication Pattern Analysis. Proc. 8th International AAAI Conference on Weblogs and Social Media, 2014.
• J. Leskovec, L. Backstrom, J. Kleinberg. Meme-tracking and the dynamics of the news cycle. Proc. 15th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2009.
• L. Backstrom, J. Kleinberg, R. Kumar. Optimizing Web traffic via the Media Scheduling Problem. Proc. 15th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2009.
• 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, 2004.
• 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. 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.

Representations for Learning

• M. Raghu, A. Irpan, J. Andreas, R. Kleinberg, Q.V. Le, J. Kleinberg. Can Deep Reinforcement Learning Solve Erdos-Selfridge-Spencer Games? Proc. 35th Intl. Conf. on Machine Learning (ICML), 2018.
• M. Raghu, B. Poole, J. Kleinberg, S. Ganguli, J. Sohl-Dickstein. On the expressive power of deep neural networks. Proc. 34th Intl. Conf. on Machine Learning (ICML), 2017.

Language, Text Content, and Social Interaction

• C. Danescu-Niculescu-Mizil, J. Cheng, J. Kleinberg, L. Lee. You had me at hello: How phrasing affects memorability. Proc. 50th Annual Meeting of the Association for Computational Linguistics, 2012.
• C. Danescu-Niculescu-Mizil, L. Lee, B. Pang, J. Kleinberg. Echoes of power: Language effects and power differences in social interaction. Proc. 21st International World Wide Web Conference, 2012.

Team Formation and Dynamics

• I. Kloumann, C. Tan, J. Kleinberg, Lee. Internet Collaboration on Extremely Difficult Problems: Research versus Olympiad Questions on the Polymath Site. Proc. 25th International World Wide Web Conference, 2016.
• D. Romero, D. Huttenlocher, J. Kleinberg. Coordination and Efficiency in Decentralized Collaboration. Proc. 9th International AAAI Conference on Weblogs and Social Media, 2015.

Algorithms and Models for On-Line Education

• A. Anderson, D. Huttenlocher, J. Kleinberg, J. Leskovec. Engaging with Massive Online Courses. Proc. 23rd International World Wide Web Conference, 2014.
• A. Ghosh, J. Kleinberg. Incentivizing participation in online forums for education. Proc. 14th ACM Conference on Electronic Commerce, 2013.
• T. Novikoff, J. Kleinberg, S. Strogatz. Education of a Model Student. Proc. National Academy of Sciences, 109(6) 1868-1873, 7 February 2012.

Privacy in Network Analysis and Data Mining

• D. Crandall, L. Backstrom, D. Cosley, S. Suri, D. Huttenlocher, J. Kleinberg. Inferring Social Ties from Geographic Coincidences. Proc. National Academy of Sciences 107(52) 22436-22441, 28 December 2010.
• 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

• D. Crandall, L. Backstrom, D. Huttenlocher, J. Kleinberg. Mapping the World's Photos. Proc. 18th International World Wide Web Conference, 2009.
  • See also some maps of cities and continents constructed using the methods in this paper.

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

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.

General Articles on Web Information and On-Line Social Networks

• J. Kleinberg. How can we have this much data and still not understand collective human behavior? In What's the question about your field that you dread being asked? (S. Mullainathan and J. Brockman, editors) 2013.
• J. Kleinberg. E Pluribus Unum. In This Will Make You Smarter: New Scientific Concepts to Improve Your Thinking (J. Brockman, editor), Harper Perennial 2012.
• J. Kleinberg. The Human Texture of Information. In Is the Internet Changing the Way You Think? (J. Brockman, editor), Harper Perennial 2011.
• J. Kleinberg. What Can Huge Datasets Teach Us About Society and Ourselves? In Future Science (M. Brockman, editor), Vintage 2011.
• J. Kleinberg. The convergence of social and technological networks. Communications of the ACM, 51(11):66-72, 2008.
• 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, 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.

General Articles on Algorithms, Complexity, and Discrete Math

• J. Kleinberg. Digital Representation. In This Idea Is Brilliant: Lost, Overlooked, and Underappreciated Scientific Concepts Everyone Should Know (J. Brockman, editor), Harper Perennial 2018.
• J. Kleinberg. The Pigeonhole Principle. In This Explains Everything. (J. Brockman, editor), Harper Perennial 2013.
• J. Kleinberg. The Mathematics of Algorithm Design. In Princeton Companion to Mathematics, (T. Gowers and J. Barrow-Green, eds.), Princeton Univ. Press, 2008.
• 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 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 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.
• 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.

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.

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.

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.

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.

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.
• R. El-Yaniv, J. Kleinberg. Geometric two-server algorithms. Information Processing Letters 53(1995).
• 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).

Contact Information