Skip the navigation

Shrinking Degrees of Separation

MacArthur prize winner connects people as well as disciplines.

By Gary Anthes
October 24, 2005 12:00 PM ET

Computerworld -

Jon Kleinberg, a professor of computer science at Cornell University
Jon Kleinberg, a professor of computer science at Cornell University
"Jon Kleinberg is a computer scientist with a reputation for tackling important, practical problems and, in the process, deriving deep mathematical insights," says the Web site of the John D. and Catherine T. MacArthur Foundation. Kleinberg, a professor of computer science at Cornell University, was a recent winner of a MacArthur Fellowship, often referred to as a "genius" grant.
Kleinberg's research covers a diverse range of topics, including computer and social networking, network routing and search, genomics and protein structure analysis. He has found surprising similarities in the underpinnings of these disciplines.
For example, he discovered how to build networks so that one node can connect to a faraway node efficiently and without knowledge of the overall network topology. The idea builds on the concept of "six degrees of separation," which holds that any two people can find connections to each other via shared relationships with others. Kleinberg's discoveries have influenced the design of decentralized peer-to-peer file-sharing services such as Freenet and social networks such as LiveJournal.com.
Kleinberg's research aims to transform Internet search. Above is a map of the Internet, with major connections color-coded by IP address.
Kleinberg's research aims to transform Internet search. Above is a map of the Internet, with major connections color-coded by IP address.
Image Credit: Lumeta Corp., Somerset, N.J.
When he worked at IBM, Kleinberg showed how search engines can be improved by considering not only a site's content, but also the number and quality of links to it. He developed the concept of "authorities" (a PC's manufacturer, for example) and connecting "hubs" (reviews of that PC), and he figured out how to recursively find the best hubs and authorities for a given search. His algorithms can also be used to define and explain social groups and their connections. In a recent interview, he told Computerworld where some of those ideas could lead.

Are the major public search engines today using your network search principles? Yes, but exactly what they do is a closely guarded secret. They all have very extensively tuned methods that combine link information with content information. The search engine that most directly incorporates hubs and authorities is Teoma, used by Ask Jeeves.

Is search a mature technology? It's still in its early stages. The more that's done, the more it becomes clear it's a very hard problem. What you'd like a search engine to do is simulate the experience of talking with someone very knowledgeable about a topic. Instead, you type a few words into a box, and it gives you some links. What's impressive is how far you can get with that.


What's an example of a question you'd like to ask the search engine of the future?


Additional Resources
Forrester Consulting - Optimizing Users and Applications in a Mobile World
WHITE PAPER
Solving application issues over the WAN requires careful consideration. Based on their independent research, Forrester Consulting offers recommendations on how to tackle application performance issues, insufficient bandwidth and the inability to quickly restore users in a disaster.

Read now.

Security KnowledgeVault
WHITE PAPER
Security is not an option. This KnowledgeVault Series offers professional advice how to be proactive in the fight against cybercrimes and multi-layered security threats; how to adopt a holistic approach to protecting and managing data; and how to hire a qualified security assessor. Make security your Number 1 priority.

Read now.

Cut Communications Costs Once and for All
WHITE PAPER
New IP-based communications systems are being deployed by small and midsized businesses at a rapid rate. Learn how these organizations are enabling faster responsiveness, creating better customer experiences, speeding office or mobile interactions, and dramatically reducing existing communications costs.

Read now.

Networking White Papers
Digital Transformation: Creating New Business Models Where Digital Meets Physical
Individuals and businesses alike are embracing the digital revolution. Social networks and digital devices are being used to engage government, businesses and civil...
Make the Connection: Better Network Connectivity Drives Transformation
Network connectivity is more than just plumbing. Leading organizations today see high-performance network connectivity as a critical enabler of competitive advantage, and not...
Virtualizing Government Infrastructure
All server virtualization solutions are not created equal. The more-with-less agenda for government agencies is tailor-made for server virtualization, which is evolving into...
Moving Service Management to SaaS
Today, organizations can enjoy similarly substantial benefi ts by migrating their IT service management functions to a software-as-a-service model. This paper shows how...
Achieving 360 Degree Network Visibility with Nimsoft
360° network visibility is critical for ensuring continuous availability of networks, servers, and applications-anything less could
have costly bottom-line implications.
All Networking White Papers
Networking Webcasts
Optimizing Networks for the Cloud
Join guest speaker, Rohit Mehra, IDC Director of Enterprise Communications Infrastructure, to explore current trends, discuss best practices for optimizing Data Center and...
Unified Communications 101
What's the best way to implement a unified communications solution for your organization?
Try the OptiView® XG on your network - FREE
The OptiView® XG is the first dedicated tablet with automated network and application analysis -- fastest way to root cause. XG raises the...
Apps QuickStart Series Part 2: Designing and Deploying SQL Server on VMware vSphere
Download this webcast to learn about the design considerations for virtualizing SQL workloads, performance and scalability information and high-availability options, as well as...
Apps QuickStart Series Part 1: Designing and Deploying Exchange 2010 on VMware vSphere
Download this webcast to learn the virtual hardware design considerations for Exchange 2010, deployment using the building block approach, options for high-availability and...
All Networking Webcasts
Newsletter Sign-Up

Receive the latest news test, reviews and trends on your favorite technology topics

Choose a newsletter
  1. View all newsletters | Privacy Policy
IT Jobs