Expected-value Navigation

Researchers at UMass-Amherst

this week that they’ve derived an algorithm useful for explaining
the "six degrees" phenomenon in social networks (and related activity
systems) (via). 

The social network exploited by Travers and Milgram isn’t a
straightforward, evenly patterned web. For one thing, network topology is only
known locally—individuals starting with the letter did not know the target
individual—and the network is decentralized—it didn’t use a formal hub such as
the post office. If navigating such a network is to succeed—and tasks such as
searching peer-to-peer file sharing systems or the navigating the Web by
jumping from link to link do just that—there must be parts of the underlying
structure that successfully guide the search, argue Jensen and Şimşek.

What guides the search?  The press release briefly touches
on issues of homophily and "degree disparity." Previous research has
tended to treat these qualities discretely, Jensen and Şimşek’s algorithm merges or blends
them. Perhaps most noteworthy from the release is the question of how network topologies are known. This hooks into a few of the talks from CCR Community Day ’05 and also at least a couple of the motivations behind CCC Online: how is disciplinarity known?