It is well known that naturally occuring networks can have different structures: for example, every node may be connected to a fixed number of neighbors, or additional connections to "distant" nodes may create a "small-world" structure, or some nodes may be connected to far more nodes than others, as in a "scale-free" or power-law structure (see figure).
Network structure is presumed to be important in determining behavior: for example, how fast information propagates and ability to evolve. But how do you do controlled experiments on the properties of different structures? The problem is that the networks like the Internet and ecological networks can't be easily changed.
In a beautiful series of experiments, Michael Kearns, Siddharth Suri, and Nick Montfort took a class of undergraduate students and asked them to solve various graph coloring problem. In each experiment, each of a set of students was connected (by computer) with other students in some network, and was then asked to select a color for his/her node that was different from those of his/her neighbors. This process continued until the graph coloring problem was "solved," meaning that a consistent set of colors was assigned.
The authors found that the time to solution varied greatly according to both the network structure and the amount of information provided about neighbors. The abstract:
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 [i.e., scale-free] 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.
Comments