Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Science 11 August 2006:
Vol. 313. no. 5788, pp. 824 - 827
DOI: 10.1126/science.1127207
Prev | Table of Contents | Next

Reports

An Experimental Study of the Coloring Problem on Human Subject Networks

Michael Kearns,* Siddharth Suri, Nick Montfort

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.

University of Pennsylvania, Department of Computer and Information Science, 3330 Walnut Street, Philadelphia, PA 19104, USA.

* To whom correspondence should be addressed. E-mail: mkearns{at}cis.upenn.edu

Read the Full Text


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
Connected Coordination: Network Structure and Group Coordination.
M. D. McCubbins, R. Paturi, and N. Weller (2009)
American Politics Research 37, 899-920
   Abstract »    PDF »
Behavioral experiments on biased voting in networks.
M. Kearns, S. Judd, J. Tan, and J. Wortman (2009)
PNAS 106, 1347-1352
   Abstract »    Full Text »    PDF »
Tracing information flow on a global scale using Internet chain-letter data.
D. Liben-Nowell and J. Kleinberg (2008)
PNAS 105, 4633-4638
   Abstract »    Full Text »    PDF »


To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)