University of Twente Student Theses


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
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:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page