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

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume108
Issue number2-3
DOIs
StatePublished - Jul 1 2006

Keywords

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

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint 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