How humans learn and represent networks

Abstract

Humans receive information from the world around them in sequences of discrete items—from words in language or notes in music to abstract concepts in books and websites on the Internet. To model their environment, from a young age people are tasked with learning the network structures formed by these items (nodes) and the connections between them (edges). But how do humans uncover the large-scale structures of networks when they experience only sequences of individual items? Moreover, what do people’s internal maps and models of these networks look like? Here, we introduce graph learning, a growing and interdisciplinary field studying how humans learn and represent networks in the world around them. Specifically, we review progress toward understanding how people uncover the complex webs of relationships underlying sequences of items. We begin by describing established results showing that humans can detect fine-scale network structure, such as variations in the probabilities of transitions between items. We next present recent experiments that directly control for differences in transition probabilities, demonstrating that human behavior depends critically on the mesoscale and macroscale properties of networks. Finally, we introduce computational models of human graph learning that make testable predictions about the impact of network structure on people’s behavior and cognition. Throughout, we highlight open questions in the study of graph learning that will require creative insights from cognitive scientists and network scientists alike.

Keywords: cognitive science; graph learning; knowledge networks; network science; statistical learning.

Conflict of interest statement

The authors declare no competing interest.

Figures

Fig. 1.

Transitions between syllables in the fabricated language of Saffran et al. (6). (A) A sequence containing four different pseudowords: tudaro (blue), bikuti (green), budopa (red), and pigola (yellow). When spoken, the sequence forms a continuous stream of syllables, without clear boundaries between words. The transition probability from one syllable to another is 1 if the transition occurs within a word and 1/3 if the transition occurs between words. This difference in transition probabilities allows infants to segment spoken language into distinct words (6, 31, 38). (B) The transitions between syllables form a network, with edge weights representing the syllable transition probabilities. A random walk in the transition network defines a sequence of syllables in the pseudolanguage. The four pseudowords form distinct communities (highlighted regions) that are easily identifiable by eye. Adapted from ref. , with permission from Elsevier.

Fig. 2.

Human behavior depends on network topology. (A) We consider a serial reaction time experiment in which subjects are shown sequences of stimuli and are asked to respond by performing an action. Here, each stimulus consists of five squares, one or two of which are highlighted in red (Left); the order of stimuli is determined by a random walk on an underlying network (Center); and for each stimulus, the subject presses the keys on the keyboard corresponding to the highlighted squares (Right). (B) Considering Erdös–Rényi random transition networks with 15 nodes and 30 edges (Left), subjects’ average reaction times to a transition i→j increase as the degree ki of the preceding node increases (Right). Equivalently, subjects’ reaction times increase as the transition probability Pij=1/ki decreases (43). (C) To control for variations in transition probabilities, we consider two networks with constant degree k=4: a modular network consisting of three communities of five nodes each (Left) and a lattice network representing a 3 × 5 grid with periodic boundary conditions (Right). (D) Experiments indicate two consistent effects of network structure. First, in the modular network, reaction times for between-cluster transitions are longer than for within-cluster transitions (39, 42, 43, 57). Second, reaction times are longer on average for the lattice network than for the modular network (42, 43).

Fig. 3.

Mesoscale and global network features emerge from long-distance associations. (A) Illustration of the weight function f(t) (Left) and the learned network representation P^ for learners that consider only transitions of length one. The estimated structure resembles the true modular network. (B) For learners that down-weight transitions of longer distances, higher-order features of the transition network, such as community structure, organically come into focus, yielding higher expected probabilities for within-cluster transitions than for between-cluster transitions. (C) For learners that equally weigh transitions of all distances, the internal representation becomes all to all, losing any resemblance to the true transition network. A–C correspond to learners that include progressively longer transitions in their network estimates. Adapted with permission from ref. .

Fig. 4.

Generalizations of the graph learning paradigm. (A) Transition networks often shift and change over time. Such nonstationary transition probabilities can be described using dynamical transition networks, which evolve from one network (for example, the modular network at Left) to another (for example, the ring network at Right) by iteratively rewiring edges. (B) Many real-world sequences have long-range dependencies, such that the next state depends not just on the current state, but also on a number of previous states (89, 90). For example, path 1 in the displayed network yields two possibilities for the next state (Left), while path 2 yields a different set of three possible states (Right). (C) Humans often actively seek out information by choosing their path through a transition network, rather than simply being presented with a prescribed sequence. Such information seeking yields a subnetwork containing the nodes and edges traversed by the walker.

Fig. 5.

Real transition networks exhibit hierarchical structure. (A) A language network constructed from the words (nodes) and transitions between them (edges) in the complete works of Shakespeare. (B) A knowledge network of hyperlinks between pages on Wikipedia. (C and D) Many real-world transition networks exhibit hierarchical organization (101), which is characterized by two topological features: (C) Heterogeneous structure, which is often associated with scale-free networks, is typically characterized by a power-law degree distribution and the presence of high-degree hub nodes (55). (D) Modular structure is defined by the presence of clusters of nodes with dense within-cluster connectivity and sparse between-cluster connectivity (21).