Skip to main content
Skip to main content

Creating a Framework for Evaluating the Effectiveness of Various Search Strategies in the Small-World Phenomenon



Milgram’s small-world experiments provided evidence for six degrees of separation, only a chain of five contacts separates any two random people. In theory, this small-world phenomenon is prevalent from a network structure perspective. However, empirical evidence shows that successful message chains are occasional, and the length of message chains are longer than the expected shortest path length. In this project, we construct a “null model” in order to examine how participants’ search strategies impact both the rate at which messages are successful routed and the length of these resulting paths. Using an agent-based modeling approach, we simulate different message routing situations based on the implementation of four different search strategies (i.e., random, memory, identity, and social search) on a network derived from students in a Northwestern University course entitled Collaborative Leadership and Decision Making. We find that the average completion rate for any of the search strategies differs in a statistically significant way from every other search strategy. The social search actually performs worse than if the message had traversed the network in a random walk. Additionally, results show a wide spread in the observed path length for each search strategy. Identity and social searches seemed the most effective for finding short paths, though it is possible that this is an artifact of the relative lack of messages completed overall. As a result, we conclude that simple search strategies may not be sufficient in explaining the empirical result, and that there is likely a more complex interaction taking place. Further, we see a disconnect between completion rate and observed path length, which suggests that many messages may fail to reach their targets as a result of network congestion.

Matt Nicholson, et al.

Electrical Engineering and Computer Science

April, 2018

DOI: 10.21985/N21M5X