ACM, Infosys Foundation Cite Network Pioneer for Revolutionary Advances in Web Search Techniques

acm
Association for Computing Machinery
Advancing Computing as a Science & Profession

Contacts:

 

Virginia Gold				Peter McLaughlin
ACM				Infosys Technologies, Ltd.
212-626-0505				213-268-9363
[email protected]				[email protected]

 

 

NEW YORK and BANGALORE, INDIA, April 28, 2009 – ACM (the Association for Computing Machinery) announced today 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 that underpin today’s social structure 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. 

             "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.  “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, 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.  His current research on meme-tracking and the news cycle employs a version of this approach, using words and phrases as quotes appearing in news articles and blog posts. This process automated efforts to spread ideas through word of mouth.  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, 2008, in San Diego, CA.  

 

About ACM

ACM, the Association for Computing Machinery www.acm.org, is the world’s largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field’s challenges. ACM strengthens the computing profession’s collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.  

 

About The Infosys Foundation

Established in 1996, the Infosys Foundation is the philanthropic arm of Infosys Technologies Ltd. and has the sole objective of fulfilling the social responsibility of the company by creating opportunities and working toward a more equitable society.  The Infosys Foundation has made effective strides in the areas of healthcare, education, social rehabilitation, and the arts.  The company contributes up to one percent of its profit to the foundation each year.

 

About Infosys Technologies

Infosys (NASDAQ: INFY) defines, designs and delivers IT-enabled business solutions that help Global 2000 companies win in a Flat World. These solutions focus on providing strategic differentiation and operational superiority to clients. With Infosys, clients are assured of a transparent business partner, world-class processes, speed of execution and the power to stretch their IT budget by leveraging the Global Delivery Model that Infosys pioneered. Infosys has over 104,000 employees in over 50 offices worldwide. Infosys is part of the NASDAQ-100 Index and The Global Dow. For more information, visit www.infosys.com