Complex network models and an algorithm for short path discovery

Complex systems have received a lot of research attention recently because data describing their topology has become available. The wide range of real world complex systems include the World Wide Web and the social interactions between people in society. Typically these systems are modeled with complex network graphs.; Two concepts that influence the topology of complex networks are spatial organization and preferential attachment. Complex networks can be modeled using group structures to capture the spatial organization present between nodes, and showed how a greedy algorithm could efficiently search such networks. Alternative network models that incorporate growth and preferential attachment, which lead to degree hierarchies, have been developed to model networks with a power-law degree distribution. Search algorithms that seek high degree nodes are effective on this type of network.; The ideas in this thesis have been motivated by two questions: (1) can a network model have both spatial organization and degree hierarchy characteristics, and (2) if a model has both of these characteristics, is there an effective search algorithm that takes advantage of both properties? The objectives of this thesis are to integrate both characteristics via a network construction process and propose a greedy algorithm that takes advantage of the spatial and degree organization for short path discovery.; A deterministic process is designed to iteratively construct complex networks that integrate growth, spatial organization and degree hierarchies into one model. An existing greedy decentralized search algorithm is augmented with a binary decision to selectively take advantage of the features in the network for short path discovery. We introduce a concept called visibility groups to help nodes make this decision. Empirical analysis of the algorithm on the deterministic networks reveals the algorithm achieves short paths, comparable to the shortest paths in the network.