Connectivity of random networks

Date
1976
Authors
Minai, Viqar Ahmed
Contributor
Advisor
Department
Instructor
Depositor
Speaker
Researcher
Consultant
Interviewer
Annotator
Journal Title
Journal ISSN
Volume Title
Publisher
Volume
Number/Issue
Starting Page
Ending Page
Alternative Title
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.
Description
Typescript.
Thesis (Ph. D.)--University of Hawaii at Manoa, 1976.
Bibliography: leaves 132-133.
Microfiche.
xi, 133 leaves ill
Keywords
Electric networks, Statistical communication theory, Telecommunication, Stochastic processes
Citation
Extent
Format
Geographic Location
Time Period
Related To
Theses for the degree of Doctor of Philosophy (University of Hawaii at Manoa). Electrical Engineering; no. 940
Table of Contents
Rights
All UHM dissertations and theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission from the copyright owner.
Rights Holder
Local Contexts
Email libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.