Skip to main content
Skip to main content

Engineering

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

Matt Nicholson, et al.

Electrical Engineering & Computer Science
April, 2018
DOI: 10.21985/N21M5X
Download

Abstract

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.

Related

Human-derived content of dust microbiota in athletic facilities reflects building design and operation

Ryan Blaustein, et al., Civil and Environmental Engineering

Building design and operation impact the accumulation and survival of microorganisms in indoor spaces. These microorganisms, together referred to as the indoor microbiome, have implications for human health and well being. However, the relative importance of factors like architecture compared to, e.g., human occupancy, remains unclear. This study aimed to identify putative sources of microbes found in dust and determine building characteristics that most strongly correlate with the human-derived content. Dust samples were collected from...Read on

Comparison of transmission dynamics in different networks

Hyojun Lee, et al., Chemical and Biological Engineering

Contagion processes arise broadly in the social and biological sciences, manifested as, for example the spread of infectious and the diffusion of innovations. Depending on the network structure, the transmission dynamics can have different. However, when the structure is too complex (e.g. multipartite networks), understanding the properties of the network might not be sufficient to predict and compare the transmission dynamics between similar networks. We developed an algorithm that systematically compares the transmission dynamic trajectories...Read on