Tag Archives: asns

Learning a Lattice is Easier than Learning an Irregular Graph (Sometimes)

If you made a picture of your social network, what would it look like? Would it look like a regular structure, like a lattice? Or would there be strange detours and crazy long-range connections between your friends’ friends?

Jason's Friendship Network

Jason's Friendship Network

It would probably be something more like the irregular graph than the lattice. People don’t form friendships in a regular, orderly manner conforming to strict rules of structure. Instead, people form local clusters of friends (you can call them cliques) and some people act as bridges between cliques to connect them and form the small-world topography familiar to social networks.

Ring Lattice Network

Ring Lattice Network

This is one of the points Watts and Strogatz illustrated with their social network models. A ring lattice may be a poor analog for a real-life friendship network, but a ring lattice with a few perturbations of the edges does a good job of capturing two characteristics of social graphs: local structure and random edges that allow a small world.

Watts & Strogatz Perturbations of a Ring Lattice

Watts & Strogatz Perturbations of a Ring Lattice

What would happen if we asked people to learn “who is friends with whom” in a ring-lattice social network or a perturbed Watts & Strogatz network? Will the regularity of the lattice structure make it easier to learn, or will it be difficult to learn because it goes against one’s expectations of how friendship clusters work?

The answer depends on the mode of presentation of the network. If the network is presented visually, as a network diagram, subjects learn the perfect Ring Lattice more easily than the perturbed version. However, if the network is presented simply as a list of connected nodes, the two graphs are equally easy (or hard) to acquire.

Accuracy by Training Type and Graph Type

Accuracy by Training Type and Graph Type

Diagram training allows for simple strategies. Names that are close together spatially in a Ring Lattice diagram are necessarily friends. This is true to some degree for the perturbed lattice as well, but it is not as reliable a strategy.

Diagram Training is Better than Edge Training

Remember when I told you that Learning a Social Graph Does NOT Depend on Method of Training? Well, I just hadn’t found the right type of training yet.

In fact, the results of one of my recent experiments suggest that using a diagram to teach subjects “what is connected to what” is better than telling them explicitly what is connected to what. Below are two images based on the stimuli the subjects saw.

Diagram Training Stimulus

Diagram Training Stimulus

Edge Training Stimulus

Edge Training Stimulus

The experimental manipulation was within-subject, so I could compare subjects’ own performance across the two types of training. Given the same amount of training, subjects answer more questions about the structure of the graph correctly in the Diagram Training condition than they do in the Node-Centric Edge Training condition.

Accuracy by Training Type and Graph Type

Accuracy by Training Type and Graph Type

You may notice that subjects learned two types of graph in addition to enduring two types of training. Stay tuned for a post about Ring Lattice graphs versus RingWatts graphs. I will also link to the manuscript with all the gory details of design and method when that manuscript is finished.

Learning a Social Graph Does NOT Depend on Method of Training

Learning a social graph does NOT depend on method of training. So far, at least.

One of my initial hypotheses when I began to study the acquisition of social network structure was this:

Some forms of representation of the network will lead to faster acquisition than others.

What I meant was that there are many ways you can represent a social network. You can put people’s names in circles and draw lines between the circles to represent relationships. You could simply list all the dyads – pairs of people who are friends, for example. Formally, you might create an adjacency matrix. Some of these should make learning who is connected to whom easy and some should make it less easy, right?

Well, not so far. However, I’m just beginning to explore the space, and the manipulations I’ve implemented so far may be too subtly different. For instance, I first trained subjects by either Random Edge or Network Walk training.

In Random Edge training, subjects were told they would be shown one dyad at a time – two names representing a pair of people who were friends. The friendships shown to the subjects were randomly drawn from the set of existing friendships. (An “edge” in a graph is a connection between two nodes.)

In Network Walk training, subjects similarly saw pairs of friends’ names. However, one name in each pair was always the same as a name in the previous pair. For example, a subject would see the sequence Frank-Bob, Bob-Alice, Alice-Cindy. Unlike Random Edge training, this type of training emphasizes the larger structure of the graph by taking you on a “walk” through the “network.”

This does not seem to make much difference to learners, however. In the graph below, you will notice that the type of training (Edge = Random Edge and Walk = Network Walk) makes no difference in how quickly subjects acquire information.

Random Edge vs. Network Walk Training


The type of graph affects speed of acquisition as expected. Random graphs take longer to learn than scale-free graphs.

The similarity in the pace of acquisition can also be conveyed in the form of learning curves. Here we see the number of errors decline as subjects are given more and more of each type of training.

Learning Curves - Random Edge vs. Network Walk


The difference between the two curves is not statistically reliable. Most of the confidence intervals around the data points overlap.

What should we make of the very similar performance for these two types of training? Being presented the connections in a graph in a systematic way (walking from edge to edge) seems to present no advantage over being given the list of edges in a random order. Of course, there is the usual caution about not accepting the null hypothesis. It may be the effect is just very small, and the experiment lacked power. However, the same experiment was powerful enough to detect the difference between random graph and scale-free graph acquistion rates, so if nothing else we can assume any possible effect is smaller than the graph structure effect.

I am still convinced there must be better and worse ways to learn the structure of a graph, and I’ll be experimenting with various training methods over the coming months. Check the blog for new results!

Scale-Free Graphs are Easier to Learn than Random Graphs

The first of my three hypotheses about social network acquisition concerns the structure of the social network graph. The claim is that human subjects will acquire a network’s structure more quickly if it resembles a true human social network rather than an arbitrary network. To translate this into an experiment, I compared the learning rate for subjects learning a random graph to the learning rate for those learning a scale-free graph.

What is a random social network graph? A random social network graph is a graph in which people are nodes, and the friendship ties between them (edges in the graph) are placed at random. In other words, there is nothing special about the node that determines what edges it participates in. All the edges (friendships) are sprinkled at random within the graph. Below is an illustration of a random graph.

Random Social Network Graph. Produced using the Erdős-Rényi method.

What is a scale-free social network graph? A scale-free social network graph is a graph in which the more edges (friendships) a node (person) participates in, the more likely that node will be to form new edges. In other words, the rich get richer, or the more popular one is the easier it is to make new friends. Below is an illustration of a scale-free graph.

Scale-Free Graph

Scale-Free Social Network Graph. Produced using the Barabási–Albert method.

So which of these two types of social network graph is easier to learn? The scale-free graph. I’ll post the figures for a couple experiments below. This is a clear and reliable result that replicates across all of my studies so far.

scale free vs random graph results

Scale-free graphs are acquired more quickly than random graphs. The number of trials needed to reach criterion performance is lower.

scale free vs random graph learning curves

Scale-free graphs are acquired more quickly than random graphs. The number of errors made during training decreases more rapidly for the scale-free social network graph.

UPDATE 8/21/2012: I’ve replicated this result several times now. More details and a formal description of the experiment and the results are available in pre-prints of two papers on my SSRN author page:

Acquiring Social Network Structure – Results Soon

I have completed the analysis of the first three (three!) experiments. Currently I am putting these results together for a talk here at UCSD. I will also be submitting a paper to CogSci 2011.

That means very soon I’ll have something to talk about here on the blog. Until then, enjoy the introductory slide for Friday’s talk.

Coming Soon: Acquiring Social Network Structure

Coming Soon: Acquiring Social Network Structure

Acquiring Social Network Knowledge

The shotgun approach isn’t just the name of the blog. I live it. I have so many projects going that I buy file folders by the pallet.

The one I’m really excited about at the moment is an attempt to bring together the two worlds I’ve been living in for the past year – cognitive psychology and social networks – and keep myself working on my dissertation at the same time.

For this project, I’ll be running several online experiments. The main goal is to characterize exactly how humans acquire and retain social network information.

I’ll be posting links to experiments and results here as time allows. For now, I’ll list the first few hypotheses I’ll be testing:

  • Human subjects will acquire a network’s structure more quickly if it resembles a true human social network rather than an arbitrary network. To operationalize this, I will measure learning curves as subjects learn the structure of random or scale-free graphs.
  • Human subjects will acquire a network’s structure more quickly if it is framed as a social network as opposed to the same network framed in some other manner (e.g. a computer or transport network.)
  • Some forms of representation of the network will lead to faster acquisition than others. For example, you might represent a network as a series of edges between vertices (e.g. friendships between people) or you might represent a network as a traversal of the links within it (think of following links in the Kevin Bacon Game). Some forms will lead to faster acquisition than others, and this will allow us to draw conclusions about how graph information is represented in the brain.

Check back for updates on this project, and please leave feedback and questions.