Algorithms for Nonuniform Networks

Reference:

Satu Elisa Schaeffer. Algorithms for nonuniform networks. Research Report A102, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, April 2006. Doctoral dissertation.

Abstract:

In this thesis, observations on structural properties of natural networks are taken as a starting point for developing efficient algorithms for natural instances of different graph problems. The key areas discussed are sampling, clustering, routing, and pattern mining for large, nonuniform graphs. The results include observations on structural effects together with algorithms that aim to reveal structural properties or exploit their presence in solving an interesting graph problem.

Traditionally networks were modeled with uniform random graphs, assuming that each vertex was equally important and each edge equally likely to be present. Within the last decade, the approach has drastically changed due to the numerous observations on structural complexity in natural networks, many of which proved the uniform model to be inadequate for some contexts.

This quickly lead to various models and measures that aim to characterize topological properties of different kinds of real-world networks also beyond the uniform networks. The goal of this thesis is to utilize such observations in algorithm design, in addition to empowering the process of network analysis. Knowing that a graph exhibits certain characteristics allows for more efficient storage, processing, analysis, and feature extraction.

Our emphasis in on local methods that avoid resorting to information of the graph structure that is not relevant to the answer sought. For example, when seeking for the cluster of a single vertex, we compute it without using any global knowledge of the graph, iteratively examining the vicinity of the seed vertex. Similarly we propose methods for sampling and spanning-tree construction according to certain criteria on the outcome without requiring knowledge of the graph as a whole.

Our motivation for concentrating on local methods is two-fold: one driving factor is the ever-increasing size of real-world problems, but an equally important fact is the nonuniformity present in many natural graph instances; properties that hold for the entire graph are often lost when only a small subgraph is examined.

Keywords:

community structure, graph algorithm, graph clustering, graph data mining, graph similarity, local search, minimum spanning tree, network model, nonuniform network, random graph, random sampling, routing, scale-free network, shortest path algorithm, small-world network

Suggested BibTeX entry:

@techreport{HUT-TCS-A102,
    address = {Espoo, Finland},
    author = {Satu Elisa Schaeffer},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {April},
    note = {Doctoral dissertation},
    number = {A102},
    pages = {xxii+183},
    title = {Algorithms for Nonuniform Networks},
    type = {Research Report},
    year = {2006},
}