Acquisition of network graph structure

A network graph describes the web of connections between entities in a system. Network graphs are a flexible abstraction; they are equally useful in representing which neurons communicate in a flatworm's brain and which international terrorists collaborate. Understanding how humans learn the structure of network graphs will be useful both to maximize the efficiency of teaching natural networks and to minimize cognitive complexity when designing artificial networks. To this end, I conducted five experiments in which subjects learned which objects in a set were connected. For example, some learned "who is friends with whom" in a social network. These experiments yielded several results. Strong support was found for the hypothesis that the deep structure of a graph affects how quickly it will be learned. Scale-free graphs were acquired more readily than other graphs. Much less support was found for the hypothesis that the surface description given a graph affects learning. For example, learning a social network was no easier or harder than learning a transportation network. The manner in which the learning task was described also had no discernible effect on the rate of acquisition. Learning followed two patterns within each graph. First, if a node of strong salience was present (e.g. a person node labeled "You" in a social network), then edges involving that node were learned quickly. Second, learners responded to network centrality. They responded most accurately when queried on an edge that involved two central nodes. In the last experiment, I show that graphs of medium density are difficult to train, and care must be taken to match training technique to graph structure. I also demonstrate that visual depictions of graphs are generally better teaching material than verbal descriptions. Finally, I propose a general model for network graph acquisition. In this model, the learner initially relies on a frequency heuristic to identify which nodes have many connections and which have few. This allows for educated guessing regarding which edges are valid. Slowly, explicit knowledge is accrued until the subject has perfect knowledge and need no longer rely on a heuristi