Network Biology (Jun 2021)
Analyzing capacitated networks via Boolean-based coherent pseudo-Boolean functions
Abstract
This paper introduces a novel method for analyzing capacitated networks through the utilization of the concept of a "probability-ready expression" for a Boolean-based coherent pseudo-Boolean function. Our main concern is to assess the performance indexes of biology and ecology networks having fixed channel capacities. The technique introduced is based on constructing an exhaustive description (specifically, a value-entered Karnaugh map) for the pseudo-Boolean capacity function of the network via a generalization of the max-flow min-cut theorem. Then the function is expressed in a disjunctive-normal form (DNF) by obtaining the socalled 'contributions' of each entered value via standard Karnaugh maps. The technique heavily relies on the fact that the pertinent function is a coherent one, and it is self-checking since it must produce a DNF of solely uncomplemented Boolean literals. The notorious Inclusion-Exclusion (IE) Principle is ruled out as a practical means for converting the DNF of the capacity function into its probabilistic expectation (its expected value). Instead, a method is proposed for converting the DNF of the capacity function to a 'probability-ready expression' (PRE), which can be easily transformed, on a one-to-one basis into a probability function. Two tutorial examples demonstrate the afore-mentioned method and illustrate its computational advantages over the exhaustive state enumeration method and the IE method.