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.
|
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: | https://purl.utwente.nl/essays/87380 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page