View source for An Experimental Study of the Coloring Problem on Human Subject Networks

== Citation ==

@article{kearns2006,
  title={An experimental study of the coloring problem on human subject networks},
  author={Kearns, M. and Suri, S. and Montfort, N.},
  journal={Science},
  volume={313},
  number={5788},
  pages={824--827},
  year={2006},
  publisher={American Association for the Advancement of Science}
}

== Abstract from the paper ==

Theoretical work suggests that structural properties of naturally occurring networks are important in shaping behavior and dynamics. However, the relationships between structure and behavior are difficult to establish through empirical studies, because the networks in such studies are typically fixed. We studied networks of human subjects attempting to solve the graph or network coloring problem, which models settings in which it is desirable to distinguish one's behavior from that of one's network neighbors. Networks generated by preferential attachment made solving the coloring problem more difficult than did networks based on cyclical structures, and “small worlds” networks were easier still. We also showed that providing more information can have opposite effects on performance, depending on network structure.

== Online version ==

* [http://www.sciencemag.org/content/313/5788/824.full Science page]
* [http://www.cis.upenn.edu/~mkearns/papers/ScienceFinal.pdf Alternative link]

=== 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 randomly constructed according to existing empirical network formation theories, 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 until no conflict existed in the entire graph. Average experiment duration and fraction solved were counted, and differences among different configurations were analyzed. Moreover, interesting patterns have been discovered beyond the original objective.

== Objective ==

The authors were trying to discover how behavior patterns given simplest social communication problems abstracted realistic complex problems, e.g., coloring problem differ among different social networks.

== Background == 

Previous works have empirically studied relationships between network structure and behaviors, however, in these studies, the underlying network structure is fixed and given, which prevents the investigation of alternatives, as mentioned in the paper. In this paper, artificial social networks were randomly generated regardless the real social network among participants, and only limited information among their virtual friendship is given.

== Settings ==

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

== Results ==

* A major result is that cycle-based networks exhibit totally differently from preferential attachment based networks, and 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.
* When all information was available, the cyclic graphs were all rapidly solved.
* In contrast with cyclic graphs, in the preferential attachment graphs, the additional information was actually harmful, preventing a solution from being found entirely.
* Interesting phenomena were also discovered, e.g., participants were using color switching signals to inform their friends (neighbors) while solving the problem, and "thermal noise" was also intentionally preserved by participants to get rid of local minima.

== Further thoughts & Study Plan ==
Papers you may want to read to understand this paper. 

* P. Dodds, R. Muhamad, D.J. Watts, Science 301, 827 (2003)
# As suggested by the authors, it is indeed important to leverage the ideas of this paper and evaluate the correctiveness of the observation from the paper in a setting of Web scenario, we need to investigate how to design similar experiments in a data mining sense, i.e., without intentionally design an experiment and enlist participants, but Web users should unpurposively contribute to the data collection process. This is also related to crowd sourcing topic.
# More algorithms or suggestions should be proposed to analyze the users' intentions underlying users' behaviors. Generative models might also be considered in this case.