University of Twente Student Theses

Login

Clustering properties of random shortest path metrics based on edge expansion

Linden, D.M. van der (2021) Clustering properties of random shortest path metrics based on edge expansion.

[img] PDF
873kB
Abstract:Probabilistic analysis for metric optimization problems has mostly been conducted on random Euclidean instances, but little is known about metric instances drawn from distributions other than the Euclidean. We consider the following model: take a connected graph where each edge has a weight that is independently drawn from an exponential distribution. The distance between two nodes is then the length of a shortest path (with respect to the weights drawn) that connects these nodes. Research on the clustering properties of complete graphs has been done by Bringmann et al., and their findings have been generalized for non-complete graphs by Klootwijk et al.. No research has been done however on the clustering properties of sparse graphs. This motivates our study of the clustering properties of expander graphs, which are sparse graphs a high connectivity. We have shown that if certain conditions apply, that the expected number of partitions required, for a clustering with clusters of at most diameter 4Δ, containing all vertices of a graph G, on n vertices, is O(1+n e^(h(G)Δ/2)), where h(G) is the edge expansion ratio.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:http://purl.utwente.nl/essays/87380
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page