Ses travaux les plus connus sont ceux portant sur l'algorithme HITS qu'il a développé en 1999 alors qu'il travaillait pour IBM. Cet algorithme permet, tout comme le PageRank de Google qui est apparu vers la même époque, de mesurer l'autorité d'une page Web par rapport à d'autres. L'idée de Jon Kleinberg est d'utiliser le fait que les réseaux d'information sont divisés en deux grandes entités : les autorités (qui fournissent l'information) et les hubs (qui pointent vers les autorités). Partant de là, l'algorithme HITS permet de trouver des communautés.
