Monthly Archives: April 2011

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: