Connectivity of random networks

Abstract

The concept of message propagation over random networks is of fundamental importance in such diverse problem areas as spread of an epidemic in a closed population, design of survivable communication networks, connectivity of neural networks, etc. Major limitations of the approaches available in literature for dealing with the connectivity of random networks, are as follows: i) Exact methods have been developed for the analysis of specific models. These become un-wieldy for large networks. A simplified propagation model has been used by Solomonoff and Rapoport for determining an approximate value for the weak connectivity constant of a particular homogeneous random graph. However, a similar approach, when used with some other homogeneous random network models, leads to un-realistic results. ii) Most studies on the connectivity of random networks make use of homogeneous random graphs for modeling the network. However, a number of practical communication networks cannot be adequately modeled by homogeneous random graphs. In this thesis the problem of connectivity of random networks is considered from the standpoint of developing new approaches applicable to a broad category of homogeneous random graphs, and proposing and analyzing new random graphs models for practical communication networks. The following major results have been obtained: i) Anew propagation model has been developed for determining an approximate value of the weak connectivity constant of homogeneous random graphs. In contrast to the simplified propagation model of Solomonoff and Rapoport, the new model takes into consideration the possibility of termination of the message propagation process at any intermediate step. The new approach has been tested with a number of existing and new homogeneous random network models, and has been found to give consistently good results in all these cases. ii) An exact recursive approach has been developed for determining the weak connectivity constant of outbundle independent homogeneous random graphs. It is shown that the recursive approach can be used in an indirect manner to determine the weak connectivity constant of inbundle independent homogeneous random graphs. Upper bounds on the weak connectivity constant, which can be evaluated in a straightforward manner, have been obtained for outbundle as well as inbundle independent homogeneous random graphs. iii) A homogeneous cluster random graph model is proposed for communication networks with geographical distance bias. It is assumed that the vertex set of the random graph could be partitioned into smaller subsets (clusters) such that the distances between vertices in the same cluster are approximately equal. Under this assumption, direct connections between a pair of vertices in the same cluster exist with equal probability, while the edges connecting the vertices in different clusters could be assigned probabilities depending upon inter-cluster distances. A generalized recursive approach has been developed for determining the weak connectivity constant of outbundle independent, homogeneous cluster random graphs. In addition, a simplified recursive approach has been found for determining an approximate value of the weak connectivity constant of a special homogeneous cluster random graph.