Geographic routing in social networks

TLDR

The small‑world property of social networks, where any two people are linked by short chains, has been experimentally verified and modeled theoretically. This study introduces a richer model linking geography and friendship, where befriending probability decreases with the number of closer people. The model defines friendship probability inversely proportional to the count of nearer individuals, and analytically proves that short chains can be found in any network satisfying this relationship. Empirical analysis shows that existing models fail to capture real‑world behavior; in a large network, one‑third of friendships are geography‑independent while the rest follow the proposed relationship.

Abstract

We live in a “small world,” where two arbitrary people are likely connected by a short chain of intermediate friends. With scant information about a target individual, people can successively forward a message along such a chain. Experimental studies have verified this property in real social networks, and theoretical models have been advanced to explain it. However, existing theoretical models have not been shown to capture behavior in real-world social networks. Here, we introduce a richer model relating geography and social-network friendship, in which the probability of befriending a particular person is inversely proportional to the number of closer people. In a large social network, we show that one-third of the friendships are independent of geography and the remainder exhibit the proposed relationship. Further, we prove analytically that short chains can be discovered in every network exhibiting the relationship.