Quarterly (winter, spring, summer, fall)
128 pp. per issue
7 x 10, illustrated
2014 Impact factor:

Artificial Life

Summer 2010, Vol. 16, No. 3, Pages 225-232
(doi: 10.1162/artl_a_00001)
© 2010 Massachusetts Institute of Technology
Concurrency and Network Disassortativity
Article PDF (295.47 KB)

The relationship between a network's degree-degree correlation and a loose version of graph coloring is studied on networks with broad degree distributions. We find that, given similar conditions on the number of nodes, number of links, and clustering levels, fewer colors are needed to color disassortative than assortative networks. Since fewer colors create fewer independent sets, our finding implies that disassortative networks may have higher concurrency potential than assortative networks. This in turn suggests another reason for the disassortative mixing pattern observed in biological networks such as those of protein-protein interaction and gene regulation. In addition to the functional specificity and stability suggested by Maslov and Sneppen, a disassortative network topology may also enhance the ability of cells to perform crucial tasks concurrently. Hence, increased concurrency may also be a driving force in the evolution of biological networks.