Communications of the ACM
Network Pioneer Cited For Revolutionary Advances in Web Search Techniques
Jon Kleinberg is Tisch University Professor in the Department of Computer Science at Cornell University.
Cornell University
ACM announced Tuesday (April 28) that Jon Kleinberg, a professor at Cornell University, is the recipient of the 2008 ACM-Infosys Foundation Award in the Computing Sciences for his contributions to improving Web search techniques that allow billions of Web users worldwide to find relevant, credible information on the ever-evolving Internet. Kleinberg, 37, developed models that document how information is organized on the Web, how it spreads through large social networks, and how these networks are structured to create the small world phenomenon known as "six degrees of separation."
Kleinberg's use of mathematical models to illuminate search and social networking tools has created interest in computing from people not formerly drawn to this field. The ACM-Infosys Foundation Award, established in August 2007, recognizes personal contributions by young scientists and system developers to a contemporary innovation that exemplifies the greatest recent achievements in the computing field. Financial support for the $150,000 award is provided by an endowment from the Infosys Foundation, the philanthropic arm of Infosys Technologies Ltd.
"Professor Kleinberg's achievements mark him as a founder and leader of social network analysis in computer science," said Dame Wendy Hall, President of ACM, the Association for Computing Machinery. "With his innovative models and algorithms, he has broadened the scope of computer science to extend its influence to the burgeoning world of the Web and the social connections it enables. We are fortunate to have the benefit of his profound insights into the link between computer network structure and information that has transformed the way information is retrieved and shared online."
Kleinberg was cited for his work on the use of link analysis, a search technique that ranks the absolute number as well as the most relevant, trusted sources of pages linked to a Web search query. Using this approach, Kleinberg authored an influential algorithm that rates Web pages for their links to other pages (known as Hubs) as well as the links they receive (known as Authorities). This Hubs and Authorities algorithm along with Google's PageRank algorithm appeared at a time when Web search techniques were based on keyword indexing. Together, this work revealed a basic relationship between network structure and information that fundamentally changed the direction of research and commercial activity on the Web.
Now in its second year, the ACM-Infosys Foundation Award recognizes young researchers who are currently making sizeable contributions to their fields and furthering computer science innovation. The goal is to identify scientifically sound breakthrough research with potentially broad implications, and encourage the recipients to further their research.
S. Gopalakrishnan, CEO and Managing Director of Infosys Technologies, said, "We are especially proud to honor Jon Kleinberg whose research in the relationship between networks and data has led to a revolution in the way all of us seek, retrieve and share information around the globe."
Six Degrees of Separation
The small-world experiment of social psychologist Stanley Milgram in the 1960s inspired Kleinberg to think about how social networks might be structured to enable people to find each other. Milgram's groundbreaking experiments had examined the average path length for social networks of people in the U.S., suggesting a small-world phenomenon in human society that is often associated with the phrase "six degrees of separation."
Kleinberg developed a model to predict an optimal way in which social connections could be distributed for the network to guide messages between distant pairs of people. This model was validated by subsequent research on large social-networking sites, revealing how virtual connections tend to link people who are close in geographic and other dimensions. Kleinberg's work has had a direct effect on the design of peer-to-peer systems and on Web crawling techniques that methodically browse the Web and index downloaded pages to provide faster searches.
As the Web grew, Kleinberg observed that it was developing a "time axis" — a dimension that reflected both a vast virtual library as well as a rapidly evolving repository of information. To determine how different topics and ideas evolve, Kleinberg created search techniques that track words and phrases that "burst" or jump in frequency over time, revealing when different topics are active. A technique called meme-tracking tracks the frequency with which quotes and phrases appear in news stories and blog posts over time. Kleinberg's current research on meme-tracking and the news cycle employs a version of this approach. Among its varied impacts is the ability to know how different stories compete for news coverage each day, and how certain stories persist while others fade quickly.
A Noted Professor
Kleinberg, dubbed the "Rebel King" by students at Cornell who noted that it was an anagram of his last name, has become a leader in both established areas of computer science and in the emerging areas of networks and information science. His undergraduate course at Cornell on Networks, co-taught with economist David Easley, illuminates the central role of computational ideas in modern society. Topics include how opinions, fads, and political movements spread through society; the robustness and fragility of food Webs and financial markets; and the technology, economics, and politics of Web information and online communities.
A highly successful class that is being adopted by other institutions in the U.S. and abroad, the Networks course drew 350 students representing 30 disciplines this semester, and has helped to redefine educational programs in the Information Sciences worldwide. A book based on this course is scheduled for publication in the spring of 2010 by Cambridge University Press. Kleinberg is also the co-author with Eva Tardos of "Algorithm Design," which is based on an undergraduate course he teaches. At both the graduate and undergraduate levels, he has also built a reputation as an engaging teacher with a creative ability to explain complex ideas in a clear and lucid manner.
In 2005, Kleinberg was named a MacArthur Fellow. He was awarded the Nevanlinna Mathematics Prize in 2006, and in 2008, he was named one of the "20 best brains under 40" by Discover Magazine. He is a member of the National Academy of Engineering and the American Academy of Arts and Sciences.
Kleinberg received an A.B. in computer science and mathematics from Cornell University and a Ph.D. in computer science from the Massachusetts Institute of Technology (MIT). Since 1996, he has been a professor of computer science at Cornell as well as a visiting scientist at IBM's Almaden Research Center.
ACM will present the ACM-Infosys Foundation Award at the annual ACM Awards Banquet on June 27, 2009, in San Diego, CA. For more information, click on http://awards.acm.org/2008/acm-infosys-award.cfm.
No entries found