New global optima results for the Kauffman NK model: Handling dependency

Research output: Contribution to journalArticlepeer-review


The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. This paper presents new global optima results for the NK model by developing tools for handling dependency in the cases where K grows with N; this generalizes the previous work that focused on the analysis of the (independent) case K=N-1. A dependency graph is defined and studied to handle dependencies among underlying random variables in the NK model. Order statistics (with dependencies) and the expected value of the global optima, EN, K, are bounded using equitable coloring of the dependency graph. These bounds convert the problem of bounding order statistics of dependent random variables into that of independent random variables while incorporating quantitative information about the mutual dependencies between the underlying random variables. An alternative upper bound on E N, K using direct arguments is also proposed. A detailed analysis of E N, K for K close to N (K=N-α and K=β N, α Z +,β (0,1)) is given for underlying uniform and normal distributions. Finally, for bounded underlying distributions, the global optima is shown to be concentrated around its mean E N, K.

Original languageEnglish (US)
Pages (from-to)475-494
Number of pages20
JournalMathematical Programming
Issue number2-3
StatePublished - Jul 2006


  • Concentration of measure
  • Dependency graph
  • Equitable coloring of graphs
  • NK model
  • Order statistics
  • Stochastic combinatorial optimization

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'New global optima results for the Kauffman NK model: Handling dependency'. Together they form a unique fingerprint.

Cite this