18 - Searching in networks

Summary

Introduction

One of the most important tasks in networks is searching for nodes when partial or no knowledge of their location is available. This task may be carried out in several different settings and may have many different applications. An example of searching in social networks was demonstrated in Stanley Milgram's famous experiment [Mil67], where individuals were requested to search for a path to other individuals chosen randomly from a phone book. The surprising conclusion of the experiment was that, on average, these random pairs of individuals were only separated by six nodes. However, another surprising result of the experiment was that the tested individuals were actually able to find such a short path easily in the complex network. A random walk on a network is expected to visit a large fraction of the nodes in the network before reaching the destination node. Nevertheless, the subjects of Milgram's experiment were able to locate the destination individuals with a number of steps near the actual network diameter. In this chapter we will discuss some aspects and techniques for searching nodes in complex networks.

Searching using degrees

In [ALPH01] a method is suggested for searching scale-free networks with exponent γ ≈ 2. More specifically, the following was suggested. Each node contains information not only on its neighbors, but also on its next nearest neighbors, the rationale being that the average number of next nearest neighbors diverges in networks with γ < 3, whereas the average number of nearest neighbors is a constant. The search itself is performed in two stages.