Partitioning the intrinsic order graph for complex stochastic Boolean systems

Abstract

Many different problems in Engineering and Computer Science can be modeled by a complex system depending on a certain number n of stochastic Boolean variables: the so-called complex stochastic Boolean system (CSBS). The most useful graphical representation of a CSBS is the intrinsic order graph (IOG). This is a symmetric, self-dual diagram on 2(n) nodes (denoted by I-n) that displays all the binary n-tuples in decreasing order of their occurrence probabilities. In this paper, two different ways of partitioning the IOG -with applications to the analysis of CSBSs- are presented. The first one is based on the successive bisections of this graph into smaller and smaller equal-sized subgraphs. The second one consists of decomposing the graph I-n, into totally ordered subsets (chains) of the set {0,1}(n) of all binary n-tuples.