Lynn, C. , Papadopoulos, L. , Kahn, A. & Bassett, D.
University of Pennsylvania
Daily life is filled with sequences of items that obey an underlying network structure, from natural language and music to social networks and the World Wide Web. Although humans are adept at uncovering such structures from particular examples, it remains unclear how, if at all, real-world networks are organized to facilitate this inference. Here, we develop a quantitative framework to estimate the information complexity of a sequence of items as perceived by a human observer. Across 41 man-made networks, we find that randomly-generated sequences of nodes maintain a high degree of complexity while remaining close to human expectations, thereby promoting the efficient communication of information from the network to the observer. Notably, this combination of high complexity and low divergence from expectations is supported by networks that are simultaneously heavy-tailed and highly clustered, two hallmarks of hierarchical organization. Together, these results suggest that networks in the world around us are organized, at least in part, to optimize communication with and between humans, and that this optimization may preferentially select for specific structural features.