Algorithms for nonuniform networks

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Schaeffer, Satu Elisa
dc.date.accessioned 2012-02-17T07:38:23Z
dc.date.available 2012-02-17T07:38:23Z
dc.date.issued 2006-04-28
dc.identifier.isbn 951-22-8119-8
dc.identifier.issn 1457-7615
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/2688
dc.description.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 is 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. en
dc.format.extent 183
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Helsinki University of Technology en
dc.publisher Teknillinen korkeakoulu fi
dc.relation.ispartofseries Research reports / Helsinki University of Technology, Laboratory for Theoretical Computer Science. A en
dc.relation.ispartofseries 102 en
dc.subject.other Computer science en
dc.subject.other Electrical engineering en
dc.subject.other Mathematics en
dc.title Algorithms for nonuniform networks en
dc.type G4 Monografiaväitöskirja fi
dc.description.version reviewed en
dc.contributor.department Department of Computer Science and Engineering en
dc.contributor.department Tietotekniikan osasto fi
dc.subject.keyword community structure en
dc.subject.keyword graph algorithm en
dc.subject.keyword graph clustering en
dc.subject.keyword graph data mining en
dc.subject.keyword graph similarity en
dc.subject.keyword local search en
dc.subject.keyword minimum spanning tree en
dc.subject.keyword network model en
dc.subject.keyword nonuniform network en
dc.subject.keyword random graph en
dc.subject.keyword random sampling en
dc.subject.keyword routing en
dc.subject.keyword scale-free network en
dc.subject.keyword shortest path algorithm en
dc.subject.keyword small-world network en
dc.identifier.urn urn:nbn:fi:tkk-006755
dc.type.dcmitype text en
dc.type.ontasot Väitöskirja (monografia) fi
dc.type.ontasot Doctoral dissertation (monograph) en
dc.contributor.lab Laboratory for Theoretical Computer Science en
dc.contributor.lab Tietojenkäsittelyteorian laboratorio fi


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account