An Experimental Study of the Coloring Problem on Human Subject Networks
Citation
Summary
This Paper presents a study in which the authors investigate the spread of information through networks of people and the ability of networked people to solve collective problems. The task the authors studied was that of graph coloring: assigning colors to a graphs such that no two adjacent nodes share a label. In each run of the study, one of several types of graphs was constructed, each participant was assigned to one node. Then, participants were able to adjust their color based on some subset of the information present in the graph. The number available colors was the chromatic number of the graph. The graphs used were:
- Cycle
- 5-chord cycle
- 20-chord cycle
- Leader cycle, a cycle with a few nodes in the center each connected to many others
- Preferential attachment, with 2 initial vertices for each node
- Preferential attachment, with 3 initial vertices for each node
The information visibility conditions were:
- Only colors of adjacent nodes visible
- Colors and degrees of adjacent nodes visible
- Entire graph visible
Overall, the preferential attachment graphs were much harder to solve. Of the cyclic graphs, the authors found that, with limited information, the simple cycle was the hardest problem to solve, and the leader cycle was the easiest, with the addition of chords systematically decreasing solving time. However, when all information was available, the cyclic graphs were all rapidly solved. This is in contrast with the preferential attachment graphs, where the additional information was actually harmful, preventing a solution from being found entirely.
