Networks, and associative properties, prevalent in natural and artificial systems have been investigated extensively. A common method for network analysis is based on graph theory because graphs naturally represent the relationship between objects in a network. In this context, three classes of networks are frequently investigated: random, scale-free, and small-world network. The three classes of networks have been studied extensively, to find properties and to analyze the structure of each network type using various measurements. Despite that all real networks have time delays, researchers relying on graph theory commonly disregarded delay or considered them only as being homogeneous. Delay cannot be ignored because delay has a critical role in many types of networks, such as the internet, business networks, and biological networks. The role and effect of delay, however, are still not clearly understood in the context of graph-based analysis. Furthermore, graph-based analysis of networks containing delay has not been attempted so far. In this thesis, I compared multiple network structures with delay in a graph context. I incorporated delay information into the network topology by a simple technique called temporal augmentation. Also, I investigated the effect of varying the delay distribution in these different network classes with added delay. In this thesis, several experiments were conducted based on two network construction methods (naive, and modified conventional method) and three types of delay distributions (peaked, uniform, and unimodal), with different network parameters. From the experiments, I found that the effect of the number of hubs in scale-free network was negligible, while the role of neighborhood size in small-world networks was significant. Also, neighborhood size affect smallworldness of networks. Effect of delay was expressed differently based on different patterns of delay distribution and network structures. Networks with uniformly randomly distributed delay had the best robustness in dealing with delay. Unimodal cases had larger increases in shortest path sum than uniform case. Peaked cases showed the worst increase in shortest path sum. Also, sparse networks with high smallworldness was less affected by delay while dense networks with high smallworldness more affected by delay. These results extended understanding of the relationship between network structures and delay.

Thesis (Ph.D.)--Xianggang Zhong wen da xue, 2003. / Zhi dao jiao shou: Li Peiliang jiao shou (Prof. Rance Pui-leung Lee) 880-03 Includes bibliographical references.