Jang, Bum Soon (2007-08). Effect of varying the delay distribution in different classes of networks: random, scale-free, and small-world. Master's Thesis. Thesis uri icon

abstract

  • 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.
  • 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.

publication date

  • August 2007