DELAY OF SOCIAL SEARCH ON SMALL-WORLD GRAPHS

作者：Inaltekin Hazer^*; Chiang Mung; Poor H Vincent

来源：Journal of Mathematical Sociology, 2014, 38(1): 1-46.

DOI：10.1080/0022250X.2011.629062

• delay of social search
• scale-free networks
• small-world networks
• small-world phenomenon
• social networks
• social search

This article introduces an analytical framework for two small-world network models and studies the delay of targeted social search by considering messages traveling between source and target individuals in these networks. In particular, by considering graphs constructed on different network domains, such as rectangular, circular, and spherical network domains, analytical solutions for the average social search delay and the delay distribution are obtained as functions of source-target separation, distribution of the number of long-range connections and geometrical properties of network domains. Derived analytical formulas are first verified by agent-based simulations and then compared with empirical observations in small-world experiments. These formulas indicate that individuals tend to communicate with one another only through their short-range contacts and the average social search delay rises linearly, when the separation between the source and target is small. As this separation increases long-range connections are more commonly used, and the average social search delay rapidly saturates to a constant value and stays almost the same for all large values of the separation. These results do not require the dimensionality of the social space to be identical to the decay exponent of long-range social connections and are qualitatively consistent with experimental observations made by Travers and Milgram in 1969 as well as by others. Moreover, analytical distributions for the delay of social search predicted by the models introduced in this article are also compared with corresponding empirical distributions, and good statistical matches between them are observed. Other somewhat surprising conclusions of the article are that hubs have limited effect in reducing the delay of social search and variation in node degree distribution adversely affects this delay.

• 出版日期2014-1-2