Jon Kleinberg

• 1. Introduction

  ›

  Jon Kleinberg grew up in a household where mathematics and computing were simply the texture of daily life. His father Eugene was a mathematics professor at SUNY Buffalo. His mother Evelyn was a computer science researcher. Even his grandfather Samuel had graduated from Cornell in 1934 and spent his career teaching mathematics and physics at a Brooklyn high school. By the time Jon Kleinberg arrived at Cornell himself, he was walking a path that had, in some sense, been laid before him.

  What Kleinberg would build on that path, though, was entirely his own. He would devise an algorithm that quietly shaped how the early web organized itself. He would take Stanley Milgram's famous letter-passing experiment and ask a question no one had quite asked before: not just whether short paths exist in social networks, but why ordinary people seem so good at finding them. He would win one of the most prestigious prizes in computational mathematics, and he would teach generations of students through a textbook that became a standard in the field.

  To understand Kleinberg's work is to understand something fundamental about networks, whether those networks are pages on the web, people passing letters across a country, or the hidden geometry connecting any two points in a complex system.

• 2. The HITS Algorithm

  ›

  While working as a visiting scientist at IBM's Almaden Research Center, Kleinberg developed an algorithm that would reshape thinking about how web pages earn importance. The algorithm is called HITS, and its central insight is deceptively simple: a page is valuable not only because others link to it, but also because it links valuably outward.

  The dominant model at the time treated incoming links as the measure of importance. Kleinberg recognized that this picture was incomplete. Search engines themselves, he observed, are important precisely because they link to vast numbers of other pages. An entity that sends you to good places is itself a good place. This observation led him to distinguish two different classes of important pages. He named them "hubs" and "authorities." Authorities are pages that many hubs point to. Hubs are pages that point to many good authorities. The two categories reinforce each other in a self-organizing loop.

  Kleinberg built the HITS algorithm to automatically identify the leading hubs and authorities within any network of hyperlinked pages. The algorithm draws on eigenvector-based methods, the same mathematical machinery that also underpins PageRank. HITS served as a full-scale model for the PageRank approach, and the relationship between the two represents one of the foundational intellectual exchanges in the early architecture of web search.

• 3. Six Degrees and Hidden Geometry

  ›

  Stanley Milgram's small-world experiment from the 1960s showed that letters could travel between strangers in the United States via a surprisingly short chain of personal acquaintances. Most people took from this the comforting fact that we are all, in some sense, close neighbors. Kleinberg took something different from it.

  His question was more precise and more unsettling. Short paths may exist, but how does anyone actually find one? When you pass a letter to a friend who seems likely to know your target, you are navigating a network with only local information. You cannot see the whole graph. Yet people did navigate it successfully. That navigation, Kleinberg realized, carries profound implications for the underlying structure of social networks.

  To study this formally, Kleinberg constructed a model using a two-dimensional grid. Each node in the grid has short-range connections to its immediate neighbors and long-range connections to nodes further away. The probability of a long-range edge forming between any two nodes decays as the second power of the distance between them. Kleinberg then generalized this to a d-dimensional grid, where the probability decays as the d-th power of the distance. This mathematical structure is not arbitrary. It is the specific geometry that makes decentralized navigation possible: the precise condition under which local knowledge is enough to find a short path. His work on algorithmic aspects of the small-world experiment placed him among the first researchers to treat navigation itself, not just connectivity, as the phenomenon that demands explanation.

• 4. Honors and Recognition

  ›

  In 2005, the MacArthur Foundation awarded Kleinberg one of its fellowships, a grant widely known as the "genius grant." The following year, in 2006, the International Mathematical Union gave him the Nevanlinna Prize. That prize is awarded once every four years, on the same occasion as the Fields Medal, and it stands as the premier distinction in computational mathematics.

  Cornell's Association of Computer Science Undergraduates had already recognized him closer to home, naming him Faculty of the Year in 2002. The professional societies followed in later years: he became a member of the National Academy of Engineering and the American Academy of Arts and Sciences, was elected to the United States National Academy of Sciences in 2011, and became a fellow of the Association for Computing Machinery in 2013.

  The funding behind his research came from an equally wide range of sources. An NSF Career Award, an ONR Young Investigator Award, a Packard Foundation Fellowship, a Sloan Foundation Fellowship, and grants from Google, Yahoo!, and the NSF all supported his work at different points in his career. His textbook on algorithms, Algorithm Design, was co-authored with Éva Tardos and became a standard teaching tool in the field. In 2010, Cambridge University Press published his book Networks, Crowds, and Markets: Reasoning About a Highly Connected World, which brought his ideas about interconnected systems to a broader audience.