Six degrees

University of Massachusetts Amherst researchers have invented a new algorithm that solves a network-searching conundrum that has puzzled computer scientists and sociologists for years.

The scientists created an algorithm that helps explain the sociological findings that led to the theory of ‘six degrees of separation,’ and could have broad implications for how networks are navigated, from improving emergency response systems to preventing the spread of computer viruses.

Dubbed expected-value navigation, the algorithm describes an efficient way of searching a particular class of networks and was presented by doctoral student Ozgur Simsek, and David Jensen, professor of computer science, at the 19th International Joint Conference on Artificial Intelligence in Edinburgh, Scotland.

The algorithm is applicable to a number of networks say the researchers. Ad-hoc wireless networks, peer-to-peer file sharing networks and the World Wide Web are all systems that could benefit from more efficient message-passing. The algorithm could work especially well with dynamic systems such as ad-hoc wireless networks where the structure may change so quickly that a centralised hub becomes obsolete