Yesterday, I briefly summarized two key papers in the study of networks. Those two papers helped us understand the topology of networks. Now that we understand something about the topology of many networks, how can we exploit this information? Today, I’ll list a couple of papers that show how we can use information about a social network’s topology to search it in an efficient manner.

Decentralized Search

To begin, Jon Kleinberg’s “The Small-World Phenomenon: An Algorithmic Perspective” presents a simple network model and a corresponding greedy search strategy. Kleinberg’s model is a simple lattice of connected nodes, with additional “random” connections added between nodes. He gives a greedy algorithm that scales with the size of the network in logarithmic time.

Kleinberg’s key question was, how can we search a social network quickly making use of only local information? In “Identity and search in social networks,” Watts, Dodds and Newman attempt to answer the same question. They give methods to clump a social network into groups, then search the network with knowledge of these groups. They base their algorithm on the observation that individuals in a social network have an identity, such as their profession, and these identities break the world into a series of layers. An important point is that members in a given group will tend to make acquaintances with each other and members of similar groups. With this model, Watts et al. give a simple algorithm to efficiently pass a message through the network.

The search models of Kleinberg and Watts et al. are from a purely theoretical level. In “How to search a social network,”Lada Adamic and Eytan Adar apply these strategies to two real world social networks. These experiments help verify that the previous theoretical work has real world applications; the search strategies work on real social networks almost as well as on abstract, theoretical models. This paper is an excellent read for computer scientists since the work of Adamic and Adar furthers our understanding of real world social networks, possibly allowing us to develop better algorithms and theoretical models.