Applications of Topological Methods to Probabilistic Communication Networks

The reliability of a probabilistic communication network is considered. A probabilistic communication network is a network in which each branch is given a probability that the specific branch can perform its purpose successfully. This probability is called the reliability of this branch. The idea of the overall reliability of the simultaneous communication among all (or part of) the stations of a given network is introduced, rather than the pairwise reliability between any two stations as was discussed in previous works along this line. The overall reliability of a communication network is defined as the probability that simultaneous communication can be secured among all the stations; two formulas are given to enumerate it in terms of the branch reliabilities. An approximation is developed to calculate the overall reliability through the incidence matrix of the network when all the branch reliabilities are very small. Also, a criterion to compare relative importance of the roles played by all the branches is established by defining a quantity "load" for each branch. Two efficient algorithms are derived to find a most reliable subnetwork with no redundant branches. In addition, an exhausting method is furnished for the case of seeking simultaneous communication among only part of the terminals of the network.