ABSTRACT
Historically, Milgram’s experiment [M67] triggered interest in the discovery of how connected social beings are. A measure of the connectedness between two randomly chosen individuals is the length of the shortest chain of acquaintances between them, oen referred to as the distance or the degree of separation between them. As an example, consider Figure 21.1, where each node represents a person and an edge denotes that the nodes at the two endpoints are friends. us, the distance between B and H is 4, and the distance between E and C is 1.
